Bicolour Towers of Hanoi 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?
 A: 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.
