Fun With Towers of Hanoi
This article is completely pointless, and has no real goal or conclusion.
One of my preferred ways of killing time at restaurants and such entails solving Towers of Hanoi in my head. A Tower of Hanoi (if you cannot pronounce this, just go with "Tower of Brahma") is a mathematical game in which you have a number of rods, and a number of disks of different size which can slide onto any rod, and at the beginning of the game, they're all arranged in ascending order of size one of the rods to make a conical shape. Describing a Tower of Hanoi puzzle takes the form of T(x,y) where x = the number of disks and y = the number of pegs. The standard example seems to be T(4,3).
- The goal is to move all the disks from one peg to a specific other peg, i.e. if the pegs are all in a row, and they start on the peg on the left, the goal might be to get them to the far right.
- You can only move one disk at a time.
- No disk may be placed on top of a smaller disk.
- For any T(x,y) where x is greater than 1, a Tower of Hanoi puzzle is only solvable if y is greater than 2.
Some Interesting Things I've Noticed
Solving T(x,3) towers in my head, I noticed some patterns. For the purposes of this discussion, the rods shall be labelled A (the one you start on), B (the middle one), and C (the one you want to put them all on), and the disks are numbered in increasing order of size (1 = smallest, infinity = largest).
- Quickest solution to T(3,3): disk 1 to rod C, disk 2 to B, disk 1 to B (on top of 2 — assume this sort of thing hereinafter), disk 3 to C, disk 1 to A, 2 to C, 1 to C. Seven moves.
- With about six disks, it starts to become fairly easy to lose mental track. Hey, I get to kill more time that way!
- I quickly hit on what Wikipedia refers to as the "recursive method" of solving Towers of Hanoi: recursively subdivide it Tower of Hanois with one fewer disks, where you're trying to put them onto the other non-starting rod. Um ... example: for T(6,3) ...
- Solve for T(5,3) where you're trying to get to rod B instead of C, put disk 6 on rod C, then solve for T(5,3) where you're starting on rod B instead of A.
- Solve for T(4,3) where you're trying to get to rod C, then put disk 5 on rod B, then solve for T(4,3) where you're trying to get to B instead of C and starting on C.
- ... and so forth.
- To solve T(x,3) in the least possible moves, if you have an odd number of disks, start by putting disk 1 on rod C, and if you have an even, start by putting disk 1 on B.
- I noticed a pattern for the number of moves based on the number of disks:
- Name: Function of Hanoi (for T(x,3))
- For x = 0, F(x) = 0
- For x > 0 (or any value of x for which F(a lesser value of x) is known), F(x) = (2 * F(x-1)) + 1
- For x < 0, which is silly (or any value of x for which F(a greater value of x) is known), F(x) = (F(x+1) - 1)/2
- I began to write down the solutions:
- F(1) = 1
- F(2) = 3
- F(3) = 7
- F(4) = 15
- F(5) = 31
- F(6) = 63
- At which point I saw a much more fun pattern, forcing me to revise the function:
- For any value of x, F(x) = 2x-1.
- The puzzle was invented by mathematician Édouard Lucas in 1883, based on a legend about a Vietnamese temple which was in the process of solving a puzzle for T(64,3); the priests of the temple had been working on it according to an ancient prophecy, which said that once the last move was made, the world would end.
- The solution to T(64,3) would optimally take 18446744073709551615 moves. At a rate of one move for second, this would take about 585 billion years. (For the record, the sun is expected to last only 5 billion more years, and Earth isn't expected to survive.)
- Adding more pegs makes the process more complicated. T(1,4) still takes 1 move and T(2,4) still takes 3 moves. Solving T(3,4) takes 5 moves; T(4,4) takes 9 moves. I think T(5,4) takes 13 moves, and T(6,4) probably takes 17. I'm not sure how accurate this is or if I'm doing something wrong, but that's point where I gave up.
Previous: Bot Versus Bot
Next: Muffin's Quick-And-Dirty Guide To Pronouncing Romaji
Back to Miscellaneous
Back to Main Page