Divisibility Problem: How many switches remain in their initial position?

Question

I have been working on this problem:

There is a set of $1000$ switches, which are ordered in a row so that each switch is given a distinct rank from $1$ to $1000$. For example, the $i$-th switch refers to the switch given rank $i$. Each switch has four 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 from $D$ to $A$. Initially each switch is in position $A$. The switches are labeled arbitrarily with the $1000$ different integers $(2^x)(3^y)(5^z)$, where $x, y$, and $z$ take on the values $0, 1, \ldots, 9$. At step $i$ of a $1000$-step process, the $i$-th switch is advanced one step, and so are all the other switches whose labels divide the label on the $i$-th switch. After step $1000$ has been completed, how many switches will be in position $A$?

My work so far:

• For a switch labelled $2^{x}3^{y}5^{z}$, that switch will get flipped $(x+1)(y+1)(z+1)$ times.
• The switches remaining in position $A$ after step $1000$ are the switches that have been flipped $4k$ times, so we want $(x+1)(y+1)(z+1) = 4k$

I am not sure how to continue from this? Any hints/help on how to do so would be greatly appreciated!

Answer 1

If I am not mistaken here, we have label $2^x3^y5^z$ dividing the label $2^a3^b5^c$ if and only if $$ (x,y,z)\leq(a,b,c) $$ by coordinatwise comparison, that is $x\leq a,y\leq b,z\leq c$. Thus the switch labelled $2^x3^y5^z$ will get flipped whenever we get to label $2^a3^b5^c$ with $$ (x,y,z)\leq(a,b,c)\leq(9,9,9) $$ so exactly $(10-x)(10-y)(10-z)$ times. So your question becomes:

For how many values of $(x,y,z)$ is $(10-x)(10-y)(10-z)$ a multiple of $4$?

Those can be constructed by dividing into three cases:

1. $x,y,z$ are all even
2. exactly two of $x,y,z$ are even
3. exactly one of $x,y,z$ is even and that one has $10-t$ divisible by $4$

The first one gives you $5^3$ cases. The second gives you another $\binom{3}2\cdot 5^3$ cases. The last one gives you $\binom31\cdot 2\cdot 5^2$ cases. The total number of switches in position $A$ must therefore be $$ 5^3+\binom{3}2\cdot 5^3+\binom31\cdot 2\cdot 5^2=650 $$ Unless I have made an error.

---

Here is a little program written in Python confirming this. If you follow the link and click on the play button, the program prints $650$ as the number of switches in position $0$ corresponding to $A$.