Hanoi Tower

Hanoi Tower is one of the most popular puzzles of XIX century. There are three rods, one of which nanizany a few rings, the rings are different in size and are smaller for larger. The challenge is to move a pyramid of eight rings for the smallest number of moves. For once allowed to move only one ring, and you can not put a larger ring for less.

This famous game invented the French mathematician Edouard Lucas in 1883 [1] it was sold as a funny toy. Originally it was called «Professor Klaus (Claus) from the College Li-Su-Styan (Li-Sou-Stian)» but soon discovered that a mysterious professor from a non-existent college - no more than the names of the inventor anagram game - Professor Lucas (Lucas) from college Saint Louis (Saint Louis).

Fairy tale-legend

In one of the Buddhist monasteries of the monks a thousand years of dealing with a shifting of the rings. They have three pyramids, where wearing a ring of different sizes. In the initial state of 64 rings were put on the first pyramid and sorted by size. The monks have to pass all the rings from the first pyramid to the second, fulfilling the only condition - you can not put a ring on the ring of smaller size. When shifting, you can use all three pyramids. Monks shift one ring for one second. Once they complete their work, the end of the world.

Number of shift depending on the number of rings is computed by the formula 2n - 1. For 64-bit ring is 18 446 744 073 709 551 615 shifting and, if the speed of "a shift in the second \ ', to get around 584 942 417 355 years, the apocalypse has come neskoro.

 Back