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 (0, 0) is at the upper left corner; the x-axis extends rightward and the y-axis extends downward.

A prisoner (designated by a small circle) is originally at the corner square (0, 0). (The grid squares are being assigned the coordinates of their upper left corner.)

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?

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

What if applet does not run?

Discussion.

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 (i, j) receives the label 2^{-(i + j)}. This labeling has a nice feature:

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 1 + 2·1/2 + 3·1/4 = 11/4, leaving 5/4 > 1 for the outside the prison squares. This is not quite sufficient to draw a conclusion. However, the following observation does the trick: after the first split, there is always exactly one clone in the first row and exactly one other in the first column. The labels for these two, add up to at most 2·1/8 = 1/4 out of the outside the prison labels of 2(1/8 + 1/16 + ...) = 1/2, implying that outside the prison the clones could at most cover the squares whose labels 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.

References

A Decade of the Berkeley Mathematical Circle, The American Experience, Volume I, Z. Stankova, Tom Rike (eds), AMS/MSRI, 2008

Pegs on a Board

71536082