Which disc on the ten-thousandth move

Text

In the optimal solution of the Tower of Hanoi, with the discs numbered from $1$ (the smallest) upward, on move number $k$ you move the disc whose number is $\nu_2(k)+1$, where $\nu_2(k)$ is the exponent of the largest power of $2$ dividing $k$. Which disc is moved on move $10000$?

Solution

Factor the power of $2$ in $10000$: $10000 = 2^4\cdot 625,$ so $\nu_2(10000)=4$. The disc moved is $\nu_2(10000)+1 = 4+1 = \boxed{5}.$ (Disc $1$, the smallest, moves on every odd move; the larger discs move ever more rarely.)