Read the puzzle here first.
About the first puzzle. You can solve it by trial and error. There are 13 mice in a circle. The cat starts counting at one of the mice, eating every 13th mouse. The first mouse it eats will be the one just before the one it started at. That leaves 12. In the second round, the cat happens to start counting at the same mouse again, but since there are only 12, it reaches 13 at the same mouse, so it eats it. Then it starts counting again, and so forth. After 12 mice, only one mouse remains. With a lot of luck, the last mouse will be white, but probably not. One way to find the solution is to try starting the count at each of the 13 mice. One will work, and that's the answer.
But is there a better way? Of course. There are several. Here's a solution that depends on "false position." Start counting at one of the mice (remember which one). See which mouse turns out to be the last one. How far is that away from the white mouse? Adjust the starting mouse by that much. For instance, suppose you start at mouse x. If that leads to the last mouse being the one right in front of the white mouse, then you can conclude that if you start at the mouse right in front of mouse x, then the last mouse will be the white mouse.
A formula? Is there even a better way? That is, can you come up with a formula for f(n,k), which says which mouse to start with? The formula should be general where the number of mice is n, the number to count before eating a mouse is k, and f(n,k) indicates how many mice past the white mouse the count should start. (In the puzzle, both n and k are 13.)
Here's a table for values of f(n,k) for n and k up through 13. For instance, f(8,5) is 6 as shown in row 8 and column 5. That means if the cat starts counting with the 6th mouse after the white mouse in a circle of 8 mice, and then counts by 5s, then the last mouse will be the white mouse (which is numbered 0).
| n\k | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 3 | 1 | 1 | 2 | 2 | 0 | 0 | 1 | 1 | 2 | 2 | 0 | 0 | 1 |
| 4 | 1 | 0 | 0 | 3 | 3 | 2 | 3 | 2 | 2 | 1 | 1 | 0 | 1 |
| 5 | 1 | 3 | 2 | 0 | 4 | 2 | 2 | 0 | 4 | 2 | 1 | 3 | 4 |
| 6 | 1 | 2 | 0 | 2 | 0 | 3 | 2 | 4 | 2 | 5 | 3 | 4 | 4 |
| 7 | 1 | 1 | 4 | 6 | 2 | 5 | 3 | 4 | 1 | 3 | 0 | 0 | 6 |
| 8 | 1 | 0 | 2 | 3 | 6 | 0 | 5 | 5 | 1 | 2 | 5 | 4 | 2 |
| 9 | 1 | 7 | 0 | 0 | 2 | 3 | 8 | 7 | 2 | 2 | 4 | 2 | 8 |
| 10 | 1 | 6 | 7 | 6 | 8 | 8 | 2 | 0 | 4 | 3 | 4 | 1 | 6 |
| 11 | 1 | 5 | 5 | 3 | 4 | 3 | 7 | 3 | 7 | 5 | 5 | 1 | 5 |
| 12 | 1 | 4 | 3 | 0 | 0 | 10 | 1 | 8 | 11 | 8 | 7 | 2 | 5 |
| 13 | 1 | 3 | 1 | 9 | 8 | 5 | 8 | 1 | 3 | 12 | 10 | 4 | 6 |
You can see a pattern of going down each column. For instance, in column k = 3, after a while the numbers decrease by 2 until they reach 0, then they jump up: 4, 2, 0, 7, 5, 3, 1. That corresponds somehow to eating every third mouse. You'll have to work to see just what that correspondence is, to determine what number the sequence goes to when it jumps up, and what happens in the first few rows where n is less than k.
It doesn't appear that there's much of a pattern along a row. But, at least, each row does eventually repeat. The second row has period 2, the third row period 6, the fourth row period 12, and so forth. See if you can figure out an upper bound for the period of the nth row.
The second puzzle. What is the smallest number that the cat can count round and round the circle, if it must start at the white mouse (calling that "one" in the count) and still eat the white mouse last of all? In terms of the function f(n,k) described above, this puzzle asks for the smallest number k such that f(n,k) = 0. You can see by the table displayed above that the answer has to be greater than 13 since there are no 0s so far in the 13th row. Even though the 13th row repeats with a very long period, you'll find an entry in it that's 0 long before it begins to repeat.
The Josephus Problem. Although Dudeney phrased the problem in terms of cats and rats, the original problem was phrased in terms of people. The problem is named for the Jewish historian Josephus of the 1st century who supposedly found the solution to this problem to escape with his life. According to legend has it that he was one of 41 Jewish rebels trapped by the Romans. His companions decided to die rather than be captured, so they formed a circle and killed every third person until all were dead. Josephus placed himself in the one position that allowed himself to be the last one to die, and he survived rather than kill himself. The problem has also been found elsewhere including Japan.
You can find pages on the web that describe the problem. There are even Java applets that illustate it. Just do a web search on the phrase "Josephus Problem" to find them.
There are lots of printed references, too, including the book by W.W.R. Ball and H.S.M Coxeter entitled Mathematical Recreations and Essays.
Sept 2003
D. Joyce
Department of Mathematics and Computer Science
Clark University
This file is located at http://aleph0.clarku.edu/~djoyce/puzzles/mice.html