The Tower of Hanoi is a popular puzzle devised by French mathematician Édouard Lucas at the end of the 19th century.
It consists of three vertical axes, on one of which a certain number of perforated discs of decreasing sizes are stacked, from largest to smallest starting from the bottom.
The challenge is to move all the discs from the axis they are on to one of the other two, following these simple rules:
Only one disc can be moved at a time and to move it all the others have to be threaded on some axle.
A disk cannot be on top of a smaller disk.
Only a disk that is on top of an axis can be moved.
Obviously, the more discs there are, the more complicated the transfer is (in commercialized versions of the puzzle there are usually five to eight).
Given a trivial Tower of Hanoi, with a single disk, it is evident that one movement is enough to move that disk to another axis.
A tower with two discs is also trivial: we transfer the smaller one to one of the two free axes, the larger one to the other free axis, and finally we put the smaller one on the larger one.
Let us now consider a tower of three disks, which we will call, from smallest to largest, A, B and C. For the first movement there is only one option: transfer disk A to one of the two free axes.
For the second movement there is only one non-repetitive option: move disc B to the free axis.
The following movements are not unique, but they are quite obvious: 3) A on B, 4) C on the free axis, 5) A on the free axis, 6) B on C, 7) A on B. The sequence is, then, ABACABA.
More information
Along the paths of Euler and Hamilton
The cube
As we saw last week, Hamilton studied the paths that bear his name in the Platonic solids, which consist of passing through all the vertices once and only once.
In the case of a cube, if we call A the vertical direction, B the horizontal direction and C the anteroposterior direction, starting, for example, from the upper left vertex of the cube and going first down, then to the right, then up , then backwards and so on until completing the simple Hamiltonian path, we will see that the directional (and dimensional) sequence is ABACABA, the same as in a three-disc Tower of Hanoi.
Mere coincidence?
I invite my sagacious readers to check it, finding the sequence of transfers for a tower of four disks, and then looking for a Hamiltonian path that runs through the vertices of a hypercube (for those who do not have direct access to the fourth dimension, a three-dimensional projection like the one in the attached figure).
Is there any similarity between both routes?
Representation of a hypercube.Carlo Frabetti
The board
According to a well-known legend, the mythical inventor of chess asked the king of India for one grain of wheat for the first square of the board, two for the second, four for the third, eight for the fourth, and so on up to square 64. , doubling in each the number of wheat grains of the previous one.
Well, this number (18,446,744,073,709,551,615) is equal to the number of transfers necessary to move from one axis to another all the discs of a tower of Hanoi with 64 discs, as many as there are squares on the chess board.
Another coincidence?
By the way, if the 64 discs are made of gold and the axes are diamond needles, we are faced with the (apocryphal) legend of the tower of Brahma, according to which the world will end when the priests of the Benares temple finish moving all the discs to another axis.
But don't panic: even if the diligent monks moved one disk per second without resting for a moment, the apocalypse would not be imminent.
You can follow
MATERIA
on
,
X
and
, or sign up here to receive
our weekly newsletter
.
Subscribe to continue reading
Read without limits
Keep reading
I am already a subscriber
_