Contents

The problem        
Solutions
    Kloster
    Bowditch
    Máthé
    Gács
Variations
Demo

Variations

As well as solving the main Angel Problem, the new solutions also yield some results for other variations of the game:

  • The King of power 2 can win. Even though the Angel can jump over an eaten square, he does not need to; it suffices that he is able to squeeze diagonally between two eaten squares. This is shown in my paper and also claimed in Máthé's.
  • A Rook of power 9 can win, if it is allowed to jump over eaten squares.
  • In 3D, the Angel of power 1 can win.

Rooks

The Rook is a chess piece that can only move to squares in the same row or column as its current position. We can define several flavours of rooks.

The Rook of infinite power. This Rook can move any number of squares either horizontally or vertically in each turn, but may not leap over eaten squares. It is easy to see that this Rook cannot be caught, as in every move it can reach a square that is either in a row or in a column that contains no eaten squares.

The Rook of power n. The Rook of power n can move up to n squares horizontally or vertically, but cannot leap eaten squares. This Rook can be caught for any n, in much the same way as the Angel of power 1. First, the Devil eats the corners of a sufficiently large box. Then, at any time the Rook is near one edge of the box, it can escape through only one of the edge's squares, and the Devil can prevent it from escaping by eating just that square.

So far, nothing new. But let us define the Jumping Rook of power n, which is allowed to jump over eaten squares while moving up to n squares horizontally or vertically. This Rook is somewhat weaker than an Angel of power n. It turns out that at least for power 9 or larger, the Jumping Rook can win. This follows from a straightforward adaptation of Bowditch's strategy, in which we divide the board into tiles of 5x5 squares. A legal move in Game 1 can always be tranformed into a legal move for the Rook, as at least one of the five squares that the Rook can reach in the new tile must be uneaten.

Tiles Game 1

It seems likely that one can also adapt Máthé's proof for the Angel, to prove that there are winning strategies for Jumping Rooks of powers lower than 9.

The Angel in 3D

While the Angel Problem in 2D was long unsolved, the analogous game where the Angel is allowed to move in 3D, has been known for some time to be a win for the Angel. This has been proven independently by Bollobás and Leader ("The Angel and Devil in three dimensions", Journal of Combinatorial Theory, Series A 113 (2006) 176 – 184), and by Martin Kutz. The previously best known bound on the Angel's required power seems to be that of Kutz, 13.

Of course, now that we know that the Angel of power 2 can win in 2D, it is obvious that only power 2 is required in 3D as well. But we can do better! My 2D strategy can be adapted to yield a winning strategy for the Angel of power 1 in 3D.

As presented in the paper, the 2D strategy works in a game where the Angel has power 2 and the Devil eats one whole square in each turn. But let us look at the game on a twice as fine time scale. Then the Angel has power 1, and the Devil eats only half a square in each turn. Of course, the Devil must eat both halves of a square to make it inaccessible to the Angel, but we do not require him to eat both in consecutive turns. To win this game, the Angel can use the exact same strategy as in the original game, and the proof of this fact is completely analogous to that given in the paper (note that ni(j) now can take half-integer values).

Then to 3D. Let us restrict the Angel of power 1 in 3D to stay within the planes z = 0 and z = 1. The Angel can essentially move like the Angel of power 1 in 2D, but for every square in the x/y-plane, he has two corresponding cubes to choose between. So the Devil must eat both cubes in order to block a square. But this is equivalent to the fine-scale game above, which the Angel can win.

Top