# The Tower of Hanoi

Concrete Mathematics begins with the well-known — at least among the teachers
and students of computer science and programming — a neat little
puzzle

**Tower of Hanoi**. And it is cool since I hope the text would
finalize curing me of an aversion I used to feel towards this puzzle (and a
couple of others ๐ค). But before that, I'd like to think over the puzzle
solution myself.

For that, let's *imagine* we're children ๐ง๐ง๐ฆ. Our mommies and daddies gave us
a game to play: three sticks on the stands and a bunch of disks, each of a
different size. How nice of them indeed ๐คจ.

The goal of this game is to move a "tower" — a group of disks ordered from the
largest to the smallest bottom to top — from the initial stick (**A**) to
another stick (**Z**) one by one. There's a restrictive rule in this game: it is
forbidden to put a large disk atop a smaller one. Any stick can be utilized
along the way as long as the restrictive rule is not broken. And — since we're
just *imagining* that we're playful children, in reality trying to **compute**
something — we're going to count the least number of moves we have to make.

First, we imagine being **really** small children ๐ถ. Not to spook us away, we are
given only a few disks. We joyfully launch those disks for a flight from one
stick to another:

- One disk
- We just move it from the stick
**A**to the stick**Z**. Boom! Done!

**This is just 1 move.**

- Two disks
- 1. Move disk
**D**to the stick_{1}**M**.

2. Move disk**D**to the final destination: stick_{2}**Z**.

3. Move disk**D**to the stick_{1}**Z**.

**In total, 3 moves.**

- Three disks
- 1. Disk
**D**to_{1}**Z**.

2. Disk**D**to_{2}**M**.

3. Disk**D**to_{1}**M**(atop the disk**D**)._{2}

4. Disk**D**goes to the final stick_{3}**Z**and rests there.

5. Disk**D**moves back to_{1}**A**.

6. Disk**D**to_{2}**Z**.

7. Disk**D**to_{1}**Z**too.

**In total, 7 moves.**

Now stop and think. Translocating those disks around in our imagination (or
doing it in reality, even with the pieces of paper, if it's difficult to play
imaginary games *yet*), try to find any patterns: repeated moves for instance.
Try to find a criterion to break up scattered moves of random disks into groups.

*Pause… Think… Breath…*

Well, I'll try to formulate what I have found playing this imaginary game.

After moving a tower consisting of one disk to the final position (1 move), we
had *learned* how to solve the puzzle for one disk. This means, that from now
on, whenever a one-disk tower will have to be moved, we'd know how to do it and
how many moves it would require. Of course, a one-disk tower requiring just one
move is trivial knowledge by itself. But we're going to base more and more
complex understanding by combining pieces of triviality. Isn't it what math and
programming are about? ๐

Now consider the tower built of two disks. First, we need to open up a way for
the larger disk. And that we can do by moving the smaller disk (a one-disk
tower) to the helper stick **M** (1 move as we already know). Then we need to move
the larger disk (a one-disk tower) to the final position on the stick **Z** (1
move again). And then we need to move a tower consisting of the smaller disk to
the stick **Z** too (1 move once again).

The same is for the 3 disks tower. We already know that we need 3 moves to
relocate the smaller two disks (a.k.a. a two-disks tower). And we need to do it
twice: the first time to open a way for the largest disk; the second time to
move them to the final position. And in between, we make 1 move with the largest
disk: from the stick **A** to the stick **Z**.

To summarize, we had identified the following types of moves:

- Open the way for the largest disk by moving the rest of the tower to the stick
**M**. - Move the largest disk to the stick
**Z**. - Move the rest of the tower atop the largest disk on the stick
**Z**.

And they can be combined into just two groups:

- Move the largest disk.
- Move the rest of the tower twice.

Let's pause here, contemplating the beauty of the pattern…

Next step. Look at the numbers we have. For clarity, the following table lists cases up to the 8-disks tower.

Number of Disks | Number of Moves Grouped | Number of Moves |
---|---|---|

1 | 0 + 1 + 0 | 1 |

2 | 1 + 1 + 1 | 3 |

3 | 3 + 1 + 3 | 7 |

4 | 7 + 1 + 7 | 15 |

5 | 15 + 1 + 15 | 31 |

6 | 31 + 1 + 31 | 63 |

7 | 63 + 1 + 63 | 127 |

8 | 127 + 1 + 127 | 255 |

Do the numbers in the last column remind you of something? Try to find a pattern, and then a formula to calculate a number of moves given the number of disks.

*Pause… Think… Breath…*

A tip: now I understand why all the programming/computer science instructors seem to adore this puzzle.

*Pause… Think… Verify.*

Yeah, those are the powers of two minus one.

Hence, a tower of 64 disks should require an impressive number of
`18446744073709551616`

moves (if my calculator didn't lie of course).

Well, **now**, after resolving the years-long aversion to **The Tower of Hanoi**
puzzle (what a *Gestalt* it was!), and after hacking into its internals by
myself, I'm ready to continue reading the book and comprehending whatever the
authors have to tell about it.

#### After a Break

I'm back to reading the book.

It's nice to see I utilized the methods similar to the methods suggested by the
authors. (I'm glad I had learned those methods quite well contemplating
*discrete mathematics* a couple of years ago.) Though, I expressed them by the
less abstract means; it was interesting for me to reflect more on the
*problem-solving* process.

It feels great to dive into the world of mathematical induction again. This method may be hard to get, but once you get it: then you get it.

But it's only the beginning of the book, so we'll see how it goes when we get deeper into the text.