Monday, August 08, 2005

The Towers of Hanoi - Amaze your Friends!

Remember the old 'Towers of Hanoi' puzzle?

Legend has it that Bhuddist Monks in a temple in the ancient city of Hanoi set themselves the task of moving 64 sacred rings from one ivory spike to another. They could never move more than one ring at a time, and they could never put a bigger ring on top of a smaller one. In order to acheive the task the Monks were allowed to use a third, wooden spike - the only other place that the sacred rings could be laid.

According to the legend, before the monks make the final move to complete the new pile in the new location, the temple will turn to dust and the world will end.


Of course, some people claim that the whole Monk Legend is a load of old tosh, and that the Towers of Hanoi was invented by the French mathematician Edouard Lucas in 1883!

Whatever the truth of the matter it remains a fascinating puzzle, and is often used in Computer Science courses as an example of a problem best solved through recursion.

The trouble with recursion though is it's hard to do in your head. You want to demonstrate to your friends at the pub how, because of your great brain and mathematical genius, you can solve the Towers of Hanoi using nothing more than a pile of differently sized coins and three matches for marker posts. Maybe you want to win the next pint as a side bet. But the last thing you want to do is to mess up. Imagine the humiliation!

So here's a foolproof way. I don't claim to have invented it, but I did discover it independantly - way back when I was a young undergraduate existing on beer and pies in the smoky Cardiff pubs.

And not only does it work, it guarantees you make the lowest possible of rings to move the pile.

  • If you've got an odd number of coins, remember the sequence 4,3,5,4,3,5,4,3,5.... If you've got an even number of coins, remember 3,4,5,3,4,5,3,4,5...


  • Imagine that each matchstick is numbered: 1, 2 and 3.


  • For each move, find the two matchsticks whose numbers add up to the next number in the sequence, and move a ring from one to the other - always ensuring you're moving a smaller ring onto a larger one.

And that's it. You can't go wrong!

For example if you have 4 coins, you do 3,4,5,3,4,5,3,4,5...

  1. Move a coin from match 1 to match 2 - because 1 + 2 = 3
  2. Move a coin from match 1 to match 3 - because 1 + 3 = 4
  3. Move a coin from match 2 to match 3 - because 2 + 3 = 5
  4. Move a coin from match 1 to match 2 - because 1 + 2 = 3
  5. Move a coin from match 3 to match 1 - because 1 + 3 = 4*
  6. Move a coin from match 3 to match 2 - because 3 + 2 = 5*
  7. Move a coin from match 1 to match 2 - because 1 + 2 = 3
  8. Move a coin from match 1 to match 3 - because 1 + 3 = 4
  9. Move a coin from match 2 to match 3 - because 2 + 3 = 5
  10. Move a coin from match 2 to match 1 - because 2 + 1 = 3*
  11. Move a coin from match 3 to match 1 - because 3 + 1 = 4*
  12. Move a coin from match 2 to match 3 - because 2 + 3 = 5
  13. Move a coin from match 1 to match 2 - because 1 + 2 = 3
  14. Move a coin from match 1 to match 3 - because 1 + 3 = 4
  15. Move a coin from match 2 to match 3 - because 2 + 3 = 5

* With these ones you have to move backwards because you can't move a bigger coin onto a smaller one. Trust me. It always works out OK.

0 Comments:

Post a Comment

<< Home