I am trying to solve Bicolour Towers of Hanoi problem. It is a variation of classical Towers of Hanoi problem. There are $3$ pegs (let's call them $A$, $B$, $C$) and $N$ disks on peg $A$. Disks have colours (black/white) and they are alternating, so the first one is white, the second is black, the third is white etc. Task is to divide those disks into 2 pegs – one consisting of black disks, second consisting of white disks. I'd like to find minimal number of moves to solve this. For example, if $N = 6$, then the right answer should be $45$ moves. How to do this?
[Math] Bicolour Towers of Hanoi
algorithmscombinatorics
Best Answer
Let the disks be numbered $1, \ldots, N$ from smallest to largest. Without loss of generality (WLOG), suppose they are all on peg $A$ at the start.
Disks $N$ and $N - 1$ are different colors, so at a minimum you must move disk $N - 1$ off of disk $N$ and onto another peg. WLOG, suppose you decide to move disk $N - 1$ to peg $B$. In order to do that, you must first move disks $1, \ldots, N - 2$ to peg $C$.
So now you have disk $N$ on peg $A$, disk $N - 1$ on peg $B$, and all the other disks on peg $C$. You have to get disk $N - 2$ onto peg $A$. But in order to do this you have to move all the smaller disks from peg $C$ to peg $B$. Do all of this, so now you have disks $N$ and $N - 2$ on peg $A$ and all the other disks on peg $B$.
Fortunately, you do not have to move disk $N - 3$ again, because it is already exactly where you want it (on top of disk $N - 1$). In fact, you now have the same problem you started out with, but with $N - 2$ disks on peg $B$ instead of $N$ disks on peg $A$, and you need to move disk $N - 3$ to peg $A$.
You can make a recursive algorithm out of this, with the recursion occurring each time the number of disks to move is reduced by $2$. Likewise, you can make a recursive formula to compute how many moves the algorithm will require.