Read an Excerpt
Another Fine Math You've Got Me Into ...
By Ian Stewart
Dover Publications, Inc.Copyright © 1992 Ian Stewart
All rights reserved.
The Lion, the Llama, and the Lettuce
A long one of the dusty country roads that are typical of the county of Weffolk came a farmer. In his right hand he clutched a gigantic lettuce. His left hand grasped two rope halters. Ahead, on one halter, ambled a llama. Behind, on the other, prowled a lion. A curious procession, you may think, but such sights are commonplace in the rugged Weffolk countryside, a region noted—especially on Fridays—for its idiosyncratic agriculture. Friday is market day, and Algernon Quinn was taking his produce to market.
And Quinn had a problem. The bridge across Rising Gorge had collapsed and had been temporarily replaced by a breeches buoy. It was strong enough to carry only Quinn, together with one item of produce —lion, llama, or lettuce. (As I said, it was a gigantic lettuce. And a fairly hefty llama, if the truth be known.)
Trivial, I hear your scathing dismissal. Take the lion across, return for the llama, and finally transport the lettuce. Obviously you're no farmer. Any true son of the soil knows, intuitively and without logical thought, what such a plan will lead to. On returning from transporting the lion, Al Quinn will find a fat and happy llama, but no lettuce. A llama will guzzle an entire lettuce, however gigantic, at a single sitting. Indeed the plan has a second fatal flaw, for when a lion is left alone with a llama it tends to see the creature more as llamaburger. On the other hand, you don't expect to see a hungry lion prowling through the vegetable patch in search of a fat, juicy lettuce, so the vegetable may safely be left with the carnivore.
By now you have recognized Algernon Quinn's dilemma as the hoary wolf—goat— cabbage puzzle in disguise; and perhaps you also observed that Al Quinn is the reincarnation of the medieval mathematician Alcuin (735—804), to whom that puzzle is usually attributed. It is certainly quite ancient and appears in Ozanam's Récréations Mathématiques et Physiques of 1694. In one respect at least you are correct, for Algernon Quinn has the precise logical mind of a born mathematician. Not for him the trial-and-error approach, but systematic reasoning only. And Al reasons as follows:
"First I must simplify the problem and find its essential features. The important thing is which side of the gorge each of my three marketable items is on. It's irrelevant where I am, or where the breeches buoy is, because those are free to move at will. Subject only to the aforementioned gastronomical constraints, that the lion should not be left alone with the llama, nor the llama with the lettuce.
"I can represent the position of a single item by the digits 0 and 1, using 0 to represent this side of the gorge and 1 to represent the far side. Thus the configuration of all three items is represented by a triple (L, λ, l) in three-dimensional lion—llama—lettuce space. For example (L, λ, l) = (1,0,1) represents L = 1, λ = 0, l = 1; that is, the lion on the far side, the llama on this side, and the lettuce on the far side.
"How many configurations are there? Well, each coordinate L, λ, or l can take one of the two values 0 or 1. Thus there are 2 × 2 × 2 = 8 possibilities. What's more, they have a beautiful geometric structure: they are the eight vertices of a unit cube in lion—llama—lettuce space (Figure 1A).
"I may move only a single item at a time; that is, I may traverse only the edges of the cube. But some edges are forbidden. For example, the edge from (0,0,0) to (1,0,0) corresponds to taking the lion across the gorge on its own. But this leaves llama and lettuce unchaperoned, so I would shortly be greeted by a fat llama and no lettuce. In fact these gastronomic constraints rule out exactly four edges, which I will draw as dashed lines. The rest, representing permissible moves, I will make solid.
"The problem thus geometrized becomes: can I start at (0,0,0)—all items on this side—and get to (1,1,1)—all items on the other side—passing only along edges of the cube that are solid lines? And of course the answer is 'yes.' Indeed, from a topological viewpoint, I can lay the edges out flat (Figure 1B) and the solution stares me in the face. Two solutions, in fact, and only two if I avoid unnecessary repetitions [see the box below]. They differ only by a lion/lettuce symmetry operation."
Al Quinn's geometric method applies to a huge range of puzzles, in which objects must be rearranged according to certain rules, and the object is to get from some given starting position to some given finishing position. The idea is to form a graph consisting of vertices (dots) joined by edges (lines). Each vertex corresponds to a position in the puzzle, and each edge corresponds to a legal move. The solution of the puzzle is then a path through the graph, joining the starting vertex to the finishing one. Such a path is usually obvious to the eye—provided the puzzle is sufficiently simple that the entire graph can be drawn. Puzzles of this type are really disguised mazes, for a maze is just a graph drawn in a slightly different fashion.
The following week, Al Quinn took to market a lettuce, a llama, a lion, and a leviathan. The bridge was still down. Unsupervised leviathans, as you know, eat lions—unless a lettuce is also present, for leviathans become docile when subjected to the smell of fresh lettuce. Draw up the graph (it may or may not be helpful to observe that it is a unit hypercube in leviathan—lion—llama—lettuce space, with coordinates (L, L, λ, l) all 0 or 1, and some edges deleted) and see whether or not a solution exists.
Although Quinn's graphical approach is applicable in principle to many puzzles, there is often a practical snag: if the number of positions or moves is too large, then the graph cannot be drawn. For example, in principle the Rubik cube could be solved by drawing its graph—but the graph would need 43,252,003,274,489,856,000 vertices! The next problem is somewhere toward the limits of what is possible in practice, and also illustrates that a bit of extra thought may lead to a simpler solution.
Use Al Quinn's graphical method to find a way to slide the three blocks (Figure 2), without turning them, so that they all occupy the right-hand side of the region shown.
Does the block puzzle remind you of anything simpler? How does this help?
Another traditional puzzle leads to a graph of considerable beauty. The Tower of Hanoi was marketed in 1883 by the great French recreational mathematician Edouard Lucas (under the pseudonym M. Claus). In 1884, in La Nature, M. De Parville described it in romantic terms:
In the great temple at Benares, beneath the dome which marks the centre of the world, rests a brass plate in which are fixed three diamond needles, each a cubit high and as thick as the body of a bee.
On one of these needles, at the creation, God placed sixty-four discs of pure gold, the largest disc resting on the brass plate, and the others getting smaller and smaller up to the top one. This is the Tower of Bramah. Day and night unceasingly the priests transfer the discs from one diamond needle to another according to the fixed and immutable laws of Bramah, which require that the priest on duty must not move more than one disc at a time and that he must place this disc on a needle so that there is no smaller disc below it. When the sixty-four discs shall have been thus transferred from the needle on which at the creation God placed them to one of the other needles, tower, temple, and Brahmins alike will crumble into dust, and with a thunderclap the world will vanish.
The Tower of Hanoi is similar to the Tower of Brahma but with eight (or sometimes fewer) discs. It is an old friend of recreational mathematicians, and it may seem that little new can be said about it. But, as we shall see, Al Quinn's graphical approach leads to a delightful surprise, fully in tune with the modern era.
For definiteness, consider 3-disc Hanoi, that is, the Tower of Hanoi with just three discs. Sample positions and legal moves are shown in Figure 3. To construct the graph, we must first find a way to represent all possible positions, then work out the legal moves between them, and finally draw up the graph. I'll describe what I actually did, because to begin with it's not obvious how to proceed—and then we'll observe, with twenty-twenty hindsight, that there is a much cleverer method.
How can we represent a position? Number the three discs 1,2,3, with 1 being the smallest and 3 the largest. Number the needles 1,2,3 from left to right. Suppose that we know on which of the three needles each disc is: for example, disc 1 is on needle 2, disc 2 on needle 1, and disc 3 on needle 2. Then we have completely determined the position, because the rules imply that disc 3 must be underneath disc 1. We can encode this information in the sequence 212, the three digits in turn representing the needles for discs 1, 2, and 3. Therefore each position in 3-disc Hanoi corresponds to a sequence of three digits, each being 1, 2, or 3. To make this clear, Figure 3 includes these codes.
It follows that there are precisely 3 × 3 × 3 = 27 different positions in 3-disc Hanoi. But what are the permitted moves?
The smallest disc on a given needle must be at the top. It thus corresponds to the first appearance of the number of that needle in the sequence. If we move that disc, we must move it to the top of the pile on some other needle, that is, we change the number so that it becomes the first appearance of some other number.
For example, in the position 212 above, suppose we wish to move disc 1. This is on needle 2, and corresponds to the first occurrence of 2 in the sequence. Suppose we change this first 2 to 1. Then this is (trivially!) the first occurrence of the digit 1; so the move from 212 to 112 is legal. So is 212 to 312 because the first occurrence of 3 is in the first place in the sequence.
We may also move disc 2, because the first occurrence of the symbol 1 is in the second place in the sequence. But we cannot change it to 2, because 2 already appears earlier, in the first place. A change to 3 is, however, legal. So we may change 212 to 232 (but not to 222).
Finally, disc 3 cannot be moved, because the third digit in the sequence is a 2, and this is not the first occurrence of a 2.
To sum up: from position 212 we can make legal moves to 112, 312, and 232, and only these.
We can list all 27 positions and all possible moves by following the above rules; the result is shown in the box on page 8.
All but three positions give exactly three legal moves, but the other three positions give only two legal moves. Why?
The next task requires care and accuracy, but little thought. Draw 27 dots on a piece of paper, label them with the 27 positions, and draw lines to represent the legal moves. My first attempt at this ground to a halt in a mess of spaghetti. But after a bit of thought, rearranging the vertices and edges to avoid overlaps led to Figure 4.
Something that pretty can't be coincidence!
But before we investigate why the graph has such a regular form, let's observe that it answers the original question. To transfer all three discs from needle 1 (position 111) to needle 2 (position 222) we merely run down the left-hand edge, making the moves
111 -> 211 -> 231 -> 331 -> 332 -> 132 -> 122 -> 222.
Indeed, by consulting the graph it is clear that we can get from any position to any other—and it is also clear what the quickest route is.
a. What is the quickest route from 211 to 212?
b. What is the quickest route from 211 to 213?
On to a deeper question: what is the explanation for the remarkable structure of Figure 4?
The graph consists of three copies of a smaller graph, linked by three single edges to form a triangle. But each smaller graph in turn has a similar triple structure. Why does everything appear in threes, and why are the pieces linked in this manner?
If you work out the graph for 2-disc Hanoi you will find that it looks exactly like the top third of Figure 4. Even the labels on the vertices are the same, except that the final 1 is deleted. In fact it is easy to see this, without working out the graph again. You can play 2-disc Hanoi with three discs: just ignore disc 3. Suppose disc 3 stays on needle 1. Then we are playing 3-disc Hanoi but restricting our attention to those 3-digit sequences that end in 1, such as 131 or 221. But these are precisely the sequences in the top third of the figure. Similarly, 3-disc Hanoi with disc 3 fixed on needle 2—that is, disguised 2-disc Hanoi—corresponds to the lower left third, and 3-disc Hanoi with disc 3 fixed on needle 3 corresponds to the lower right third.
This explains why we see three copies of the 2-disc Hanoi graph in the 3-disc graph. And a little further thought shows that these three subgraphs are joined by just three single edges in the full puzzle. To join up the subgraphs, we must move disc 3. When can we do this? Only when one needle is empty, one contains disc 3, and the other contains all the remaining discs! Then we can move disc 3 to the empty needle, creating an empty needle (the one it came from), and leaving the other discs untouched. There are six such positions, and the possible moves join them in pairs.
The same argument works for any number of discs. The graph for 4-disc Hanoi, for example, consists of three copies of the 3-disc graph, linked at the corners like a triangle. Each subgraph describes 4-disc Hanoi with disc 4 fixed on one of the three needles; but such a game is just 3-disc Hanoi in disguise. And so on (Figure 5). We say that the Tower of Hanoi puzzle has a recursive structure; the solution to (n + 1)-disc Hanoi is determined by that for n-disc Hanoi according to a fixed rule. The recursive structure explains why the graph for (n + 1)-disc Hanoi can be built from that for n-disc Hanoi. The triangular symmetry arises because the rules treat needles 1, 2, and 3 in exactly the same way. You can deduce the graph for 64-disc Bramah, or for any other number of discs, by repeatedly applying this rule to the graph for 0-disc Hanoi—which is a single dot! For example, Figure 6 shows the graph for 5-disc Hanoi, drawn by applying this recursive structure. Brains instead of brawn! It would take hours to work 5-disc Hanoi by listing all 243 possible positions and finding all the moves between them—and you'd probably make several mistakes along the way.
What is the minimum number of moves needed to move all n discs from one needle to another in n-disc Hanoi?
How many distinct moves (i.e., edges of the graph) are there in n-disc Hanoi?
I haven't labeled the vertices in Figure 6. No, I don't want you to do it! But I'd like you to show that it can be done in principle. Work out a rule for labeling the graph for (n + 1)-disc Hanoi on the assumption that you know how to label the one for n-disc Hanoi.
A final observation. As the number of discs becomes larger and larger, the graph becomes more and more intricate, looking more and more like the Sierpiski gasket. This shape is a fractal, a geometrical object having detailed structure on all scales. This is a striking and surprising result, because the puzzle was invented almost a century before fractals were discovered. It is yet another demonstration of the remarkable unity of mathematics. Moreover, it has a curious application. Not long after this chapter's original appearance in the August 1989 issue of Pour la Science, I went to the International Congress of Mathematicians in Kyoto, and a German mathematician named Andreas Hinz introduced himself. He had been trying to calculate the average distance between two points in a Sierpiski gasket of unit side. One expert he had asked said it was "very difficult." Another said it was "trivial, and equal to 8/15," but on closer analysis the proof didn't hold up. Hinz had already found a formula for the average number of moves between positions in the Tower of Hanoi puzzle.
Excerpted from Another Fine Math You've Got Me Into ... by Ian Stewart. Copyright © 1992 Ian Stewart. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.