Sole Survivor: Proof
Introduction
Here we will show that every m × n block of stones for 1 < m ≤ n can be reduced to a sole survivor such that one stone ends in its initial position. We will do this by first showing that every m × n block can be reduced to an m × (n – 3) block. That is our Stage 1. By repeating this reduction we can reduce every m × n block to either an m × 2 or an m × 3 or an m × 4 block. (Of course we can get every block down to an m × 1 or m × 2 or m × 3 block. However, we can’t reduce an m × 1 block to a sole survivor so we stop at the stage before the m × 1 i.e. at the m × 4 block.)
Stages 2, 3 and 4 involve us reducing m × 2, m × 3 and m × 4 blocks, respectively.
Stage 1: m x n always goes to m x (n – 3) for n ≥ 5
(Note that the cases n = 2, 3 or 4 are dealt with in Stages 2, 3 and 4, respectively. So we are able to assume that n ≥ 5 here.)
In the diagram below, the m x (n – 3) block is shown in blue, while the part of the block to be removed is shown in white. The top three stones can be removed from the white block as shown in the diagram below. First the red stone jumps diagonally up to the left, then the green stone jumps to the right, then the red stone jumps back down diagonally to it’s original position.
This can be repeated as many times as required until there is only one row of three stones remaining in the white block to be removed. Then the same three moves flipped horizontally are used to remove those three as shown below. This time the red stone jumps down diagonally instead of up diagonally.
Stage 2: 2 x m for m ≥ 2
If the starting block has been reduced to a 2 x m block then this block can be reduced to a sole survivor by the following process. First the red stone in the diagram below jumps to the left then up diagonally to the right, removing the two left hand stones.
This leaves you with a block with one stone out of place as shown in the diagram below. The red stone shown can jump diagonally up to the left and then right to remove the two left hand stones, leaving the same ‘shape’ at the end of the block.
Repeat these two jumps until there are only four stones left as shown below. This time the red stone makes three jumps instead of two, finishing by removing the last stone and returning to the square on which it started.
So every 2 × m block can be reduced to a sole survivor with the surviving stone in its original position.
Stage 3: 3 x m, for m ≥ 3
The diagram below shows how any 3 x m block can be reduced to a 3 x (m – 1) block. The red stone jumps to the left, then the green stone jumps down, then the red stone jumps back to the right, into it’s original position.
This step can be repeated until the 3 x m block is reduced to a 3 x 2 block, which can then be reduced to a sole survivor as shown in stage 2 above. So we can reduce any 3 x m block to a legitimate sole survivor.
Stage 4: 4 x m for m ≥ 4
We can reduce a 4 x m block to a 4 x (m – 3) block by the method in Stage 1. We then only have to worry about 4 x 2, 4 x 3 and 4 x 4 blocks. The first two of these have already been done in stages 2 and 3. The last one is done below.
Here we can successively remove the three yellow, three red, three blue and three green stones using the method of Stage 1. We are then left with a 2 x 2 block that follows from Stage 2.
So we can reduce any 4 x m block to a legitimate sole survivor.
This means that for any block of any size we can reduce the block to a sole survivor.
