Towers of Hanoi

Many partnerships can achieve the same goal

This Towers of Hanoi animation uses the <canvas> element and may not run in older versions of Internet Explorer.

Some Android (eg default) browsers can't render the site properly. We'll let you know if they fix the problem (41312). Or try another browser, eg Firefox.

Example showing different partitions for moving 'off' and 'on'.

Initially discs 1 and 2 are grouped, moving the top four discs off the base.

Then, as the top four discs move onto the base, discs 2 and 3 are grouped.

Disc 1 moves 4 times in the off phase and 2 times in the on phase. In the terminology of the proof, disc 1 is a height 3 disc on a base of disc 2 (moving off); it is a height 2 disc on a base of disc 4 (moving on).

The total number of moves is conserved, off and on, since disc 2 moves 2 times, as a height 2 disc (moving off) and 4 times as a height 3 disc (moving on).

For completeness, disc 3 is a height 2 disc and moves 2 times, off and on. However it has 1 free peg moving off, and 2 moving on (but uses 1).