Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!sri-spam!sri-unix!hplabs!sdcrdcf!trwrb!trwspp!spp2!stassen
From: stassen@spp2.UUCP (Chris Stassen)
Newsgroups: sci.math
Subject: Re: angels and devils
Message-ID: <1178@spp2.UUCP>
Date: Mon, 10-Nov-86 16:33:12 EST
Article-I.D.: spp2.1178
Posted: Mon Nov 10 16:33:12 1986
Date-Received: Tue, 11-Nov-86 02:13:30 EST
Reply-To: stassen@spp2.UUCP (Chris Stassen)
Distribution: net
Organization: TRW, Redondo Beach  CA
Lines: 85
Keywords: How to catch 2-D 1-move Angel, some ideas on containment.
Bcc: stassen


Note:  nothing rigorous here; just some random thoughts.  Hit 'n' or 'j'
now if you're only interested in proofs.

Contents:    1) 2-dimensional, 1-move Angel can always be caught.
	     2) Looking at the "end run" concept.
	     3) Forcing the Angel to 'turn'
	     4) More than two dimensions.

The Devil CAN always trap the Angel, in two dimensions, when the Angel's
move is 1.  Here's the strategy (condensed vertically to fit in one screen):


+-----------------------------------------+
|       X*....................*X          | The Angel cannot get to the 'X'
|       * ++++++++++++++++++++ *          | planets from inside the square,
|       .+                    +.          | as long as the '*' planets get
|       .+          A         +.          | destroyed first.
|       .+                    +.          |
|       * ++++++++++++++++++++ *          |
|       X*....................*X          |
+-----------------------------------------+


The Devil simply destroys the 8 '*' planets, on a 19x19 square, with the
Angel starting at the center of the square.  Then, whenever the Angel reaches
a planet marked '+', the Devil simply destroys the planet marked '.' right
beside it.  The Angel can never get out of the square.  (a 19x19 square was
selected so that the Angel cannot reach the '+' planets before the Devil
finishes with the corners).  (btw, I'll show later that it only takes one
extra '*' to turn the Angel around the corner, so this could have been
accomplished on a 11x11 square, only taking half of the '*' planets first).

Note that this works by destroying planets so that there is no planet that
the Angel can get to which permits two possible escapes from the area.  Any
planet ('+') that the Angel can get to has only one associated exit ('.'),
which the Devil can cut off as soon as the Angel reaches the '+' planet.

I've been thinking about the "end run" concept; the 1-planet-per-move Angel
is the ONLY case where the Angel cannot run around a line that the Devil is
building:

+-----------------------------------------+
| Area that the Angel must be kept out of |
|************                             |
|          A->                            |
+-----------------------------------------+

The Devil can keep the Angel out of that area, because he can destroy one
more planet in the line for every one planet that the Angel can move -- the
Angel cannot "run around" the line if the Devil does not "want" him to.

As soon as the Angel's move is bumped to 2, the Devil must destroy FOUR
planets for every step that the Angel may take, and the Devil can no longer
keep the Angel on one side of the line.

+-----------------------------------------+
| Area that the Angel must be kept out of | The Devil must destroy the four
|************++                           | '+' planets to keep the Angel from
|************++                           | getting to the other side of the
|          A->                            | line in two moves.
+-----------------------------------------+

Back to 1-move Angels in two dimensions: If the Devil has one "spare" move
(i.e. destroyed planet ahead of the line), then he can force the Angel to
take a right turn.  ($ = extra planet in line, 1-5 = Devil's moves, and
a-e = Angel's moves).

+-----------------------------------------+
| Area that the Angel must be kept out of | The Angel cannot escape to the
|************123$.                        | '.' planet unless his move is
|           abcde4                        | at least SQRT(2).
|                5                        |
+-----------------------------------------+

In the above diagram, the Devil now has the Angel "walled off" on the right,
and the Angel cannot "run around" the Devil's vertical line.

This algorithm fails in three dimensions.  The Devil can still keep the
Angel on a particular side of a plane, but it requires an infinite amount
of 'spare moves' ('$') for the Devil to force the Angel to turn and be
contained by two intersecting planes.  The issue of "being able to force
the Angel to turn" is more critical to containing the Angel than the issue
of keeping it on one side of a line/plane.

				-- Chris