In this episode there is unfortunately little mathematics. However, the "Angel and Devil" problem is mentioned (and is also the basis for the name of this episode). The Angel and Devil problem seems to originally been posed in a book by Berlekemp, Conway, and Guy in 1982, but only recently (2006 and later) has a solution appeared. We'll discuss the problem and some solutions and partial solutions to it.

There are actually infinitely many versions of this game, one for each integer
*k*. The game has 2 players, an Angel and a Devil, and is played on an
infinite chess board. The Angel starts on one particular square and in one
move is able to move to any square that a chess king could move to
in *k* moves. Angels have wings, of course, so the Angel can "hop" from
a square to the next one, and it doesn't matter if there are removed squares
between the initial and final positions.
The Devil, on its turn, is able to remove any square it
wants to from the board, which means that on future turns, the Angel is
not able to move to that square. The Angel wins the game if it has a strategy
that will enable it to continue moving forever, and the Devil wins if it has
a strategy that lets it "trap" the Angel, so that the Angel eventually doesn't
have any legal moves. There is also a generalization of this game where the
board that is used is 3-dimensional. To avoid convoluted grammatical
constructions, we'll always use the female gender for the Angel (or other
names for the player with the same role) and the male gender for the Devil
(this was chosen by a flip of a coin).

This type of problem is dealt with in a field of
mathematics called *combinatorial game theory*, which deals with
the applications of the field of combinatorics to various types of
games. Another problem that you might have heard of that is of the type
that is dealt with in this field is the prisoner's dilemma.

One might think that since the board is infinite,
it would be impossible for the Devil to trap the Angel
even if the Angel can only move one square at a time. However, this intuition
is incorrect, because in 1982 Conway showed that if *k* is 1 (i.e. the
Angel can only move one square at a time), then the Devil has a winning
strategy. Here is a list of some other partial results that were the best
results
known until recently (in the first 4, the value of *k* is arbitrary):

- If the Angel always increases its y-coordinate, then the Devil can win.
- If the Angel always increases its distance from the origin, then the Devil can win.
- The Devil can force the Angel to follow a path that moves arbitrarily far in some particular direction.
- The Devil can force the Angel to wind around a particular point an arbitrarily large number of times.
- In the 3-dimensional version of the game, the Angel can win if
*k*is sufficiently large.

First, since the Fool is restricted to increasing her y-coordinate, the set
of all possible positions the Fool can ever reach are contained in a cone
whose point is at the Fool's initial position and whose sides have slope
1/*k*. The Devil's strategy will be to draw a horizontal wall at height
H (which will be determined later) above the Fool's initial position
and to remove squares along this wall in such a way that the Fool will
eventually run into a solid, unpassable block of the wall. (This means that
the Devil must eventually force the Fool to be right below a block of removed
squares that is *k* blocks tall and wide.) Initially, the Devil will
remove every Mth square along this top line (where we'll choose the
constant M later).

The next observation is that when the Fool has travelled halfway up the
cone (i.e. her height is H/2), then her possible positions are reduced to
a smaller cone whose point is at her current position and whose sides have
slope 1/*k*. Using basic geometry, we see that the base of this cone
has half the length as the base of the original cone (in our view, the
base is at the top). At this point, the Devil can restrict himself to this
shorter segment of the wall that he is trying to build. We'll choose M in
such a way that the Devil will finish removing every Mth square of the wall
before the Fool can travel half the vertical distance up the original cone.
The wall the Devil is trying to construct has width 2*H**k* and
height *k*, so the total number of blocks he has to remove is at most
2*H**k*k*. It will
take the Fool at least H/*2k* turns to reach the halfway point, so we
must have 2*H**k*k*/M less than H/*2k*, so we'll take M to be at
least
4**k*k*k*. Notice that M is indepedent of H, and that after the
Fool reaches the halfway height, at least 1/M of the squares in the
wall the Devil is trying to build that the Fool is still able to reach
have already been removed. Now we can
repeat this argument, so by the time the Fool reaches 3/4 of the height of
the original cone, the Devil will have removed at least 2/M of the blocks
that the Fool can still reach in the wall that he is trying to build.
Now we just have to choose H to be large enough so that 2^H is greater than
M.

Can you modify this argument to show that the Devil can always win against an Angel who never decreases her y-coordinate? (Hint: How long will it take the Devil to build walls on the horizontal line that Angel starts on in such a way that the Angel must eventually increase her y-coordinate?)

The statement that the Devil can win against an Angel who always increases
her distance from the origin was also proved by Conway in the same
paper. We won't go through the proof here, but the basic idea is as follows.
The Devil splits up the plane into N cones, all with the same angle
and basepoint the origin. Then if the Angel is at any particular spot in one
of these cones, the Devil pretends that the Angel is at that same spot
in every one of the cones. He positions one Demon in each cone, and splits
his moves evenly between all the Demons. Then a Demon thinks that he is
trying to trap an Angel with power N**k* who is always staying inside
his cone, and he plays as the Devil does in the scenario above.

There are 4 recent proofs that an Angel of sufficiently high power can win, and one of them gives an explicit strategy for an Angel of power 2 to win. This paper is here, and we'll give a brief summary of the strategy. The actual argument is pretty detailed, but we'll skip the details.

If you're in a maze, one way to guarantee that you get out is to put your left hand on a wall and keep walking. If the maze has an exit, you will eventually find it. The strategy for the Angel is somewhat similar. She divides the board into Forbidden squares, Free squares, and Removed squares. At the beginning, she declares that the left half of the board is Forbidden and the right half is Free, and starts moving up the boundary between the Forbidden and Free halves. The boundary between the Free and Forbidden areas is the Angels path, which has a forwards and backwards direction. As the game progresses, the Angel will add squares to the Forbidden zone based on the actions of the Devil, and each of her moves will be along the boundary between the Free and Forbidden squares (so she's keeping her left hand on the wall and going forwards). After each move, she will change as many squares from Free to Forbidden as possible, subject to the following constraints:

- The Forbidden area stays connected (i.e. there's just one "piece" of the Forbidden area, or any two points in the Forbidden area can be connected by a path that stays entirely in the Forbidden area).
- The path behind the Angel is unchanged.
- The length of the path increases by no more than 2 for each eaten square that is added to the Forbidden zone.

References:

Wikipedia

The page of the author of one of the proofs.