Position of switches based on divisibility

Question

There is a set of $1000$ switches. Each has four different positions, called $A$, $B$, $C$, and $D$. When the position of any switch changes, it is only from $A$ to $B$, from $B$ to $C$, from $C$ to $D$, or $D$ to $A$. Initially, each switch is in position $A$. The switches are labelled with the $1000$ integers $(2^x)(3^y)(5^z)$, where $x$, $y$, and $z$ take on a value from the set ${0, 1, 2, 3, 4, 5, 6, 7, 8, 9}$. At step $i$ of a $1000$-step process, the $i$-th switch is advanced $1$ step, and so are all of the other switches whose labels divide the $i$th switch. After all $1000$ steps have been completed, how many switches will be in position $A$?

Answer 1

It's easier to count the number of switches that will not be in positin A. The switch with label $2^x3^y5^z$ will be switched $(10-x)(10-y)(10-z)$ times. The switch will end up in position A iff the number of time it is switched is divisible by 4.

A product will be divisible by 4 if one of its factors is itself divisible by 4 or at least two of its factors are each divisible by 2.

Let $A = \{ 2, 6 \}$ (an exponent resulting in a factor divisible by 4), $ B = \{ 0, 4, 8 \}$ (an exponent resulting in a factor being divisible by 2), and $ C = \{ 1,3,5,7,9 \}$ (an exponent resulting in an odd factor).

If one or more of the label's exponents are from set A, then the switch will be flipped a multiple of 4 times, so it will end on A.

If none of the exponents are from A but two or more of the label's exponents are from set B, then the switch will also end on A.

If all of the exponents are from C, then the switch will be flipped an odd number of times, ending on position B or D. There are $|C|^3 = 5^3 = 125$ switches like this.

If 2 of the exponents are from C and 1 is from B then the switch will be flipped $2 \mod 4$ times, ending on position C. There are $\binom{3}{1}|C|^2| |B| = 3 \cdot 5^2 \cdot 3 = 150$ switches in this case.

So there are $125+150=275$ switches left in positions other than A, leaving $1000-275=725$ switches on A.