This puzzle is immediately understandable, solves quickly with just a few disks (the advice is to start with 3 disks), but it gets quite complicated as the number of disks increases: the number of moves needed to solve it increases very quickly. The minimum number of moves, errors excluded, is perfectly predictable: if n is the number of disks you play with, you will need at least 2^n-1 moves to solve it.

For example:
With 1 disc, 2^1-1=2-1=1 move will be needed.
With 2 discs, 2^2-1=4-1=3 moves will be needed.
With 3 discs, 2^3-1=8-1=7 moves will be needed.
And so on…
Put another way, every time you add a floor, you need twice as many moves plus one. This second relationship is more obvious than the first as you play: each time you add a disk (below the others) you will first have to repeat the same operations as in the previous round to clear it, then move the added disk, then repeat the moves in reverse to cover it.

Teaching links: Exponentials – Hidden in the solution of the game are the well-known powers of 2, recalling among other things the binary notation of numbers (in fact, there is an interpretation of the game in this key, see link below).

Teaching links:  Mathematical successions – To prove (by induction) that the minimum number of moves to solve the game with n planes is 2^n-1 we use a result from succession theory: 

Teaching links:  Programming – The triangle arrangement of the Hanoi tower also highlights the algorithm of moves that can be found as a solution (in a nutshell: even-numbered discs always move in one direction, odd-numbered discs move in the opposite direction). Following this procedure, a computer can solve the problem without knowing the rules of the game, while a human could move the tower correctly while thinking about the shopping list, whistling.

Other external resources:
Exhaustive Wikipedia page on the game (link)

This game has an ancient flavor, but it was invented in 1883 by mathematician Edouard Lucas, as was the story that accompanied the toy version:

The Legend of the Tower of Hanoi

In the great temple of Benares, under the vault that marks the center of the world, there is a brass plate on which are fixed three diamond pins, each one cubit high and the same thickness as the body of a bee. On one of these pins, at the time of creation, God placed sixty-four disks of pure gold, the largest resting on the brass disk and gradually the others smaller and smaller. It is the tower of Brahma. Day and night, ceaselessly, the priests transfer the disks from one diamond pin to another according to the fixed and unchanging laws of Brahma, which require that the priest at work move no more than one disk at a time and that he must place this disk on a pin so that there is no smaller disk beneath it. When the sixty-four discs are transferred in this way from the pivot on which God had placed them at the time of creation to one of the other pivots, tower, temple and Brahmins will be reduced to dust and the world will vanish in a clap of thunder.

This would happen-it is mathematical-in as many as 2^64-1= 18,446,744,073,709,551,615 moves. If they were one per second (without errors!) that would be more than 5 billion centuries.