I noticed yesterday that the number 264 - 1 appears at least twice in the mathematical folklore.
The first place is in the Tower of Hanoi puzzle. This puzzle is as follows: you are given n disks, all of different sizes, with holes on them, and three posts. The disks are originally stacked on one of the posts in order of size, with the small disks on the top and the large disks on the bottom. Your job is to move the disks to one of the other posts, subject to the following constraints:
1. you can only move one disk at a time;
2. the disks on any post, at any time, must be in order of size.
This can be solved in 2n-1 moves. The solution is given by a nice recursion. To move n disks from post A to post B, first move the smallest n-1 disks from post A to post C. Then move the largest disk from post A to post B. Then move the smallest n-1 disks from post C to post B. Thus moving n disks takes twice as many moves as moving n-1 disks, plus 1. Moving a stack consisting of one disk of course takes one move; solving the recursion gives the answer.
There's a story that goes along with this. It involves some monks in some temple somewhere whose job is, basically, to do this for n = 64. When they finish the universe will end. If they can make one move per second, this takes 264 - 1 seconds, about six hundred billion years, which is suspiciously close to the actual expected lifespan of the universe for such a crude model...
The other place that 264 - 1 occurs is in the story about the invention of chess. Supposedly the ruler of the land where the inventor of chess lived really liked chess, and he offered the inventor a reward. The inventor of chess said that he wanted one grain of wheat placed on the first square of the chessboard, two on the second square, four on the third square, and so on, each square having double the number of grains of the square before. The total number of grains works out to be 264 - 1, which is a lot. Wikipedia has an article on this. A grain of wheat is about 50 milligrams; this works out to about 15,000 kilograms of wheat for every person who has ever lived. (I'm assuming sixty billion people have ever lived, which I have no evidence for but it's a number I've heard.) If we assume an average historical lifespan of 40 years, that's one kilogram per day per person. In other words, you could approximately feed everyone ever for their whole lives with this amount of wheat. It's a lot.
Subscribe to:
Post Comments (Atom)
4 comments:
An interesting relationship between the two occurrences of 2^64 - 1:
If you solve the Towers of Hanoi with 64 layers (using the recursive algorithm you mentioned), and call the bottom layer "layer 1", then the number of times any given layer will move is equal to the number of grains of rice on its square on the chess board.
Now that I'm a grumpy old man, I know more about how the world works. Playing mathematical jokes on the "ruler of the land" is how you get summarily executed.
So this is essentially a coincidence that 64 shows up in each case. The formula $2^n - 1$ isn't exactly rare.
Though this reminds me of a thought I had recently. First some background: if every puzzle is a hidden algorithm, and an algorithm is a theorem, then we can talk about morphisms of puzzles, like John Baez has spoken about explicitly with "rewrite rules" and Tim Gowers has implicitly discussed about "when two proofs are the same".
Most of these proof-morphisms are isomorphisms (or equivalences, to weaken it a little) but I ran into one that seems to be non-invertible. Find a "morphism" from the Towers of Hanoi to the Chinese Rings.
John,
of course you're right -- but it sounds more impressive when it's stated the way I did. And 64 is itself a power of 2. (I don't think that particularly explains anything, though; the chessboard just has to be square, and the Hanoi puzzle would work with any number.)
Post a Comment