By John H. Conway
Abstract: Can the Devil, who removes one square per move from an infinite chessboard, strand the Angel, who can jump up to 1000 squares per move?
The Angel and the Devil play their game on an infinite chessboard, with one square for each ordered pair of integers (x,y). On his turn, the Devil may eat any square of the board whatsoever; this square is then no longer available to the Angel. The Angel is a “chess piece” that can move to any uneaten square (X,Y) that is at most 1000 king’s moves away from its present position (x,y) – in other words, for which |X - x| and |Y - y| are at most 1000. Angels have wings, so that it does not matter if any intervening squares have already been eaten.
The Devil wins if he can strand the Angel, that is, surround him by a moat of eaten squares of width at least 1000. The Angel wins just if he can continue to move forever.
Can the Angel defeat the Devil?
A first guess may be to just have the Angel keep running *away*. This is called the FOOL’s Angel.
..
(by Andreas Blass and John Conway)
DEFINITION: A Fool is an Angel who is required always strictly to increase his y coordinate. So a Fool can make precisely those Angel moves from (x,y) to (X,Y) for which Y > y.
THEORM: The Devil can catch a Fool.
PROOF: If the Fool is ever at some point P, he will be at all subsequent times in the “upward cone” from P, whose boundary is defined by the two upward rays of slope +1/1000 or -1/1000. Then we counsel the Devil to act as follows (Figure 1): he should truncate this cone by a horizontal line AB at a very large height H above the Fool’s starting position, and use his first few moves to eat one out of every M squares along AB, where M is chosen so that this task will be comfortably finished when the Angel reaches a point Q on the halfway line that’s distant 1/2H below AB (we’ll arrange H to be exactly divisible by a large power of two).
A_________C___E_____F______D____B
\\\///
\\\///
\\\///
\\R//
\\//
\\//
\\//
\\//
\\//
\Q/
\/
\/
\/
\/
\/
\/
\P/
*
***
Figure 1: A Fool traveling north with the Devil eating along AB.
At subsequent times, the Devil knows that the Fool will be safely ensconced in the smaller cone QCD, where CD is a subinterval of AB of exactly half its length, and for the next few of his moves, he should eat the second one of every M squares along segment CD. He will have finished this by the time the Fool reaches a point R on the horizontal line 1/4H below AB. At later times, the Fool will be trapped inside a still smaller cone REF, with EF = 1/2CD = 1/2AB, and the Devil should proceed to eat the third one of every M squares along the segment EF of AB.
If he proceeds in this way, then by the time the Fool reaches this horizontal line a distance H’ = 2^(-M)H below AB, the Devil will have eaten every square of the subsegment of AB that might still be reached by the Fool. The Devil should then continue, by eating the first out of every M squares on the segment A’B’ just below this one, a task which will be finished before the Fool reaches the horizontal line distant 1/2H’ below A’B’, when he should start eating the second of every M squares on the portion C’D’ of A’B’ that is still accessible, and so on. We see that if we take H of the form 1000x2^N, where N > 1000M, then before the Fool crosses the horizontal line that is 1000 units below AB, the Devil will have eaten all squares between this line and AB that the Fool might reach, and so the Fool will be unable to move.
Too... much... math...
Talking... like... Shatner...
AH...but...do..you..get...the...sexy...green..chicks?
I heard a rumor that somebody may have solved this. Does anyone know anything?
I heard a rumor that somebody may have solved this. Does anyone know anything?
I think I heard the same thing.
THEORM: The Devil can catch a Fool.
Does that assume the angel continues towards the 'cone'?
The Devil could also win if the angel continued to hop back and forth between only two squares.
A few years ago I gamed with a math professor but then I moved to Florida, so I have to rely on you guys.
I play Hero. Apparently, that qualifies me. :P
But does being from Texas disqualify you?
Go suck on a British Petroleum tar ball. :P
Does that assume the angel continues towards the 'cone'?
In that scenario, the Angel keeps 'running away'. Where 'running away'
means always increasing his y coordinate. Specifically, moves from (x,y) to (X,Y) for which Y > y.
|
The only way for the Devil to win is to create an area where there is a single square that is completely surrounded by eaten squares for 1001 squares around it. He has to leave one square open to reach that square and trick the Angel to moving to the square before eating the only exit.
The only other way for the Devil to strand the Angel is if the Angel moves a certain way and only that way with no deviation or change. Hence, the Angel is not making informed decisions, nor changing his route at all.
Either way, the Devil has to be smarter than the Angel. The first example has a better chance of working since the Devil [u]is[/u] the great manipulator, but he still has to rely on the Angel trusting that the trap isn't a trap.
Does that assume the angel continues towards the 'cone'?In that scenario, the Angel keeps 'running away'. Where 'running away'
means always increasing his y coordinate. Specifically, moves from (x,y) to (X,Y) for which Y > y.
I still do not think I am fully understanding, because if the Angel increases his x coordinate as well, it seems your theory falls apart.
I still do not think I am fully understanding, because if the Angel increases his x coordinate as well, it seems your theory falls apart.Does that assume the angel continues towards the 'cone'?In that scenario, the Angel keeps 'running away'. Where 'running away'
means always increasing his y coordinate. Specifically, moves from (x,y) to (X,Y) for which Y > y.
Y has to change such that Y>y. (For each move the new y coordinate has to be greater than the old y coordinate.)
X can remain the same, or x can change: if x remains the same he moves straight "up"; if x changes, then he moves off at an "angle", but still "upward".
So the angel is confined to a cone-shape area. If the angel zig-zags back and forth, he is 'inside' the cone-shape area, and even if he always makes the maximum x increase in one direction only he is still 'inside' the cone-shape area (riding along one of the edges).
This is just an example of one strategy the Angel can use, and is called The Fool's Angel. Because the devil can always catch a fool.
…but the angle can change and I think that makes a big difference. The only restriction I understand is that Y>y. X can be anywhere between X-1000 and X+1000 and change from turn to turn. Sure, the Devil could set the trap at some point above Y, but the angel could veer around it at any point.
…but the angle can change and I think that makes a big difference. The only restriction I understand is that Y>y. X can be anywhere between X-1000 and X+1000 and change from turn to turn. Sure, the Devil could set the trap at some point above Y, but the angel could veer around it at any point.
You're right on it. Exactly. But if the devil starts eating far enough out, he will always trap the Angel; there will be no place for the angel to veer around.
O.k. I think I understand better, but I am still not convinced. The Devil would have to know where the Angel is going to be to know how far out to start…wouldn't he?
Ah! I think I have it now. There is a limit to how wide of an angle the angel can take. The Devil only has to anticipate within the most extreme ends.
Note that the 1000 variable is adjustable, to change the challenge significantly simply reduce that.
One day I should actually do this?
This would be far simpler if the angel suspected trickery.
Create the trap area first, then try to lure the angel away from the entrance as much as possible.
Textbook Kansas City Shuffle.
Assuming the angel is aware of the devil, and that the angel is sufficiently clever to evade the devil, I wonder if there is a minimum N the angel needs, where N is the number of moves it can make (N in the original problem is 1000). If the angel can only make a single move, does it have any hope? What about 2 moves? At what point can an intelligent angel evade the devil forever?
This is what I think:
o The angel and the devil are fully aware of each other.
o The devil can eat in sequence any two squares even if they are infinitely far apart.
So,
If they duel for an infinite number of moves, then the devil can eat every square. Thus, the angel can never win.
EDIT: > HERE < is the original statement of the question.
.
Devil is locked in position only able to eliminate one square at a time? Angel should win in 3 to 5 moves.