The Reve's Puzzle
(
CANTERBURY PUZZLES)
The Reve was a wily man and something of a scholar. As Chaucer tells us, "There was no auditor could of him win," and "there could no man bring him in arrear." The poet also noticed that "ever he rode the hindermost of the route." This he did that he might the better, without interruption, work out the fanciful problems and ideas that passed through his active brain. When the pilgrims were stopping at a wayside tavern, a number of cheeses of varying sizes caught his alert eye; and calling for four stools, he told the company that he would show them a puzzle of his own that would keep them amused during their rest. He then placed eight cheeses of graduating sizes on one of the end stools, the smallest cheese being at the top, as clearly shown in the illustration. "This is a riddle," quoth he, "that I did once set before my fellow townsmen at Baldeswell, that is in Norfolk, and, by Saint Joce, there was no man among them that could rede it aright. And yet it is withal full easy, for all that I do desire is that, by the moving of one cheese at a time from one stool unto another, ye shall remove all the cheeses to the stool at the other end without ever putting any cheese on one that is smaller than itself. To him that will perform this feat in the least number of moves that be possible will I give a draught of the best that our good host can provide." To solve this puzzle in the fewest possible moves, first with 8, then with 10, and afterwards with 21 cheeses, is an interesting recreation.
Answer:
The 8 cheeses can be removed in 33 moves, 10 cheeses in 49 moves, and 21 cheeses in 321 moves. I will give my general method of solution in the cases of 3, 4, and 5 stools.
Write out the following table to any required length:—
Stools. |
Number of Cheeses. |
3 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
Natural Numbers. |
4 |
1 |
3 |
6 |
10 |
15 |
21 |
28 |
Triangular Numbers. |
5 |
1 |
4 |
10 |
20 |
35 |
56 |
84 |
Triangular Pyramids. |
|
Number of Moves. |
3 |
1 |
3 |
7 |
15 |
31 |
63 |
127 |
4 |
1 |
5 |
17 |
49 |
129 |
321 |
769 |
5 |
1 |
7 |
31 |
111 |
351 |
1023 |
2815 |
The first row contains the natural numbers. The second row is found by adding the natural numbers together from the beginning. The numbers in the third row are obtained by adding together the numbers in the second row from the beginning. The fourth row contains the successive powers of 2, less 1. The next series is found by doubling in turn each number of that series and adding the number that stands above the place where you write the result. The last row is obtained in the same way. This table will at once give solutions for any number of cheeses with three stools, for triangular numbers with four stools, and for pyramidal numbers with five stools. In these cases there is always only one method of solution—that is, of piling the cheeses.
In the case of three stools, the first and fourth rows tell us that 4 cheeses may be removed in 15 moves, 5 in 31, 7 in 127. The second and fifth rows show that, with four stools, 10 may be removed in 49, and 21 in 321 moves. Also, with five stools, we find from the third and sixth rows that 20 cheeses require 111 moves, and 35 cheeses 351 moves. But we also learn from the table the necessary method of piling. Thus, with four stools and 10 cheeses, the previous column shows that we must make piles of 6 and 3, which will take 17 and 7 moves respectively—that is, we first pile the six smallest cheeses in 17 moves on one stool; then we pile the next 3 cheeses on another stool in 7 moves; then remove the largest cheese in 1 move; then replace the 3 in 7 moves; and finally replace the 6 in 17: making in all the necessary 49 moves. Similarly we are told that with five stools 35 cheeses must form piles of 20, 10, and 4, which will respectively take 111, 49, and 15 moves.
If the number of cheeses in the case of four stools is not triangular, and in the case of five stools pyramidal, then there will be more than one way of making the piles, and subsidiary tables will be required. This is the case with the Reve's 8 cheeses. But I will leave the reader to work out for himself the extension of the problem.
Informational
