The $k$th move of the Tower of Hanoi

Question

In the tower of Hanoi $x,y,z$ are the positions and we are to move 10 disks from $x$ to $y$. What are the 128th and 768th moves?

(A) $x\to y$ and $x\to z$

(B) $x\to z$ and $z\to x$

(C) $x\to z$ and $z\to y$

(D) $x\to y$ and $z\to y$

I know the total number of moves is $2^{10}-1=1023$. For move 128 I did $128\bmod3=2$, which gave me nothing at all… please help me out!

Answer 1

Try listing out the moves for one, two and three discs:

1  2  3  4  5  6  7
XY
xz XY zy
xy xz yz XY zx zy xy

There is a pattern here that allows us to get the sequence of moves for the next number of discs:

1. We copy the whole sequence for the previous number of discs, but replace y with z and vice versa.
2. We append xy.
3. We append the previous sequence again, but replace x with z and vice versa.

This allows us to find the source and destination pegs of the $k$th move of the $n$-disc sequence:

1. Initialise the source and destination pegs as x and y respectively. Write out $k$ as an $n$-bit binary word (zero-padded on the left) and place a pointer on the least significant 1.
2. Stop and return the source and destination pegs if the pointer is on the most significant bit. Otherwise, move the pointer one place left. If it lands on a 0, replace y with z and vice versa; if it lands on a 1, replace x with z and vice versa. Repeat step 2.

---

Here, $n=10$, so the set-ups for finding the 128th and 768th moves are as follows:

0010000000 = 128
  ^ xy
 ^ xz
^ xy -> 128th move is x -> y
1100000000 = 768
 ^ xy
^ zy -> 768th move is z -> y

Hence the correct answer is (d).

By the way, here's the algorithm for the 72nd move:

0001001000 = 72
   |  ^ xy
   | ^ xz
   |^ xy
   ^ zy
  ^ yz
 ^ zy
^ yz -> 72nd move is y -> z