Escape of the Clones
The applet below implements a variant of a famous puzzle attributed to Maxim Kontsevich. The puzzle appeared in the Tournament of Towns and in the Russian magazine Kvant in 1981, almost immediately followed by a solution due to A. Khodulev [Kvant, 1982, pp 28-31, 55.] Subsequently, the puzzle was generalized by Chung, Graham, Morrison, and Odlyzko in an 1995 American Mathematical Monthly article. I am yet to see the latter.
The setup of the puzzle consists of a quarter plane (infinite, of course) with the integer grid lines drawn. The origin
A prisoner (designated by a small circle) is originally at the corner square
The prisoner can't move but can split into two clones - one immediately to the right and another immediate below its present location. If one of the clone designations is already occupied, the split does not take place. The clones behave in exactly the same manner.
A part of the corner near the origin is designated as a prison and is fenced in by an orange border.
The question is, for what prison configuration, the prison can be emptied of the prisoner and the subsequent generations of the clones in a finite number of moves?
|What if applet does not run?|
By now, you have probably figured out that the prison can be fully emptied for a single square configuration, for 3 squares 1×1 and for the 2×2 square but not for 6- and 10-squares triangle configurations. If you found an explanation of why this is so, I'd like to hear from you. Please see the contact instructions.
The solution is reminiscent of John Conway's solution for a checker jumping problem.
We assign a number label to each of the grid squares. The square
At any time, the sum of the labels of all the squares occupied by either prisoner or the clones is always 1!.
This is clearly true for the initial position and no split interferes with that fact.
|What if applet does not run?|
The applet displays only a finite portion of the board. But do think of it as infinite. The labels in the very first row form a geometric sequence 1, 1/2, 1/4, ... whose sum is 2.
The labels in the second row form a geometric sequence 1/2, 1/4, 1/8, ..., with the sum of 1. The subsequent rows have sums 1/2, 1/4, ... so that the sum of the labels in the entire board is
2 + 1 + 1/2 + 1/4 + ... = 4.
The clones' labels always add up to 1. How much is taken up by the 10-square triangle? It is easy:
1 + 2·1/2 + 3·1/4 + 4·1/8 = 15/4,
leaving for the clones outside the prison only 3/4 which is being less than 1 can't hold all the clones. Thus the 10-square triangle prison is inescapable. What about the 6-square triangular configuration?
The labels of the 6 corner squares add up to
(4 - 11/4) + (1/2 - 1/4) = 1.
But the prison has to be emptied in a finite number of splits, meaning that at any time there is only a finite number of clones so that the remaining quantity of 1 is never met (because it's the sum over an infinite portion of the board). So that there is always a clone inside the prison.
Actually, the outside the prison portion of the board could not be filled with the clones even after an infinite number of splits. This is because filling entirely the second row and column would require the clones in the first row and column to move away from the origin leaving the most valuable outside labels of 1/8, which together add up to the requisite 1/4.
- A Decade of the Berkeley Mathematical Circle, The American Experience, Volume I, Z. Stankova, Tom Rike (eds), AMS/MSRI, 2008