Conference rusure::math

    does this need a spoiler? probably not, but I will anyway...
    
    
    Clearly, if you limit the range of the angel to 1, it will become
    trapped.
    
    Clearly, if you do NOT limit the angel, it can NEVER be trapped.
    
    So, between those two limits, where does the answer change from
    NO to YES.
    
    I think that for any finite limit to the angel's range, the devil
    can generate a "fence" enclosing the angel, since the field is infinite
    and the devil can destroy ANY planet.
    
    I won't even try to prove it, but that is my argument.
                                                   
                  /
                 (  ___
                  ) ///
                 /
    

    What if the angel's range is limited to 2?  That is, the angel
    (A) can move to any of the stars (*s) below that have not been
    destroyed by the devil.

			*
		      * * *
		    * * A * *
		      * * *
			*

    Is the devil able to trap the angel?

I need some clarification.

>Every day, the angel can fly off to another planet, but the angel's
>range is limited to a distance of (say) 100.

Does this mean that the A can travel to any planet within a spherical
radius of 100, or that the A can make up to 100 trips to orthogonally
adjacent planets per day? 

>    Clearly, if you limit the range of the angel to 1, it will become
>    trapped.

Not clear at all. In order to confine the A to a region of radius 1, the D 
must destroy 4 planets, which requires 4 days, by which time the A is 
long gone. If the A can skip over destroyed planets, the D must destroy
r**2 planets where r is the A's travel radius. The best the D can do in 
this situation is to restrict the A to a 'ladder' pattern (which is a 
winning ploy in GO because the board has a finite edge.)

The question is then whether the D can devise a strategy for limiting the
A's options over a very large area. His chances look poor to me.

re: clarification

>Does this mean that the A can travel to any planet within a spherical
>radius of 100, or that the A can make up to 100 trips to orthogonally
>adjacent planets per day? 

	The angel 'flies' to another planet -- some or all of the
	intermediate planets might have already been destroyed by
	the devil.

	The problem has the planets arranged in a 2-dimensional grid
	(so 'spherical radius' is misleading).

	How is the distance measured?  By sqrt(dx�+dy�) or by |dx|+|dy|?
	In .2, I've assumed it's measured by |dx|+|dy|.  This makes the
	problem simpler, and this problem needs all the simplification
	it can get.

re .4:
>                                               The best the D can do in 
>this situation is to restrict the A to a 'ladder' pattern (which is a 
>winning ploy in GO because the board has a finite edge.)

	Surely D can do better than that if r=1; it looks like D can
	prevent A from getting further than distance 3 away from the
	starting planet.  Another strategy from GO (other than a ladder)
	would create some sparse defenses 'back' a few squares; if A
	heads toward this 'wall', D makes it less sparse.

re .3: (What are the rules?)

Not really sure, since the original author never clarified it.  That hasn't
slowed down the anarchist USENETters, however.  They have been posting their
own solutions making their own additional restrictions (like stating in their
solution the angel's move is sqrt(x^2+y^2)  For the sake of this discussion,
I'll define the angel's move as only along an X or a Y axis, and there must be
a continuous line of planets from A to B for the angel to move from A to B.
This makes life rough for the angel, and if someone can show a method of
trapping the angel with a move of N ( >=2 ) I'll change the rules a little
to make life easier on the angel (such as diagonal moves, and planet jumping)

re .1:  It isn't "obvious" that an angel that can move only one square along
an axis can be trapped, but 2 such methods have already been shown, which
I'll post later.

-Mike

    Re .6:
    
    > For the sake of this discussion, I'll define the angel's move as only
    > along an X or a Y axis, and there must be a continuous line of planets
    > from A to B for the angel to move from A to B. This makes life rough
    > for the angel, and if someone can show a method of trapping the angel
    > with a move of N ( >=2 ) I'll change the rules a little to make life
    > easier on the angel (such as diagonal moves, and planet jumping) 
    
    I believe one person has shown that if the angel can be trapped when
    she can move up to N planets per turn but cannot jump planets, then the
    angel can be trapped when she can move no more than [sqrt(N)] planets
    and can jump planets, and that if the angel can be trapped when she can
    move up to N planets per turn, in any direction, and can jump planets,
    then she can be trapped when she can move no more than (2N)^2 planets
    per move.
    
    So solving one problem gives us a handle on the variations.  My
    impression of the original posing of the problem agrees with another
    Usenet poster -- since the angel _flies_ from one planet to another, we
    should use the normal Euclidean distance without worrying about
    intervening planets.
    
    
    				-- edp 

    If the devil can destroy ANY planet on any day, then there is the
    possibility that he can destroy the planet on which the angel is
    sitting.  Of course, the angel could fly away as the planet is
    destroyed, so synchronicity is important here.  Or the angel might
    be a little late and be destroyed, too.
    
    I would like to have the problem stated in clearer terms.  Since
    I'm not a mathematician, I may not be making the assumptions that
    are usually made in a puzzle of this sort.  I'm sure that these
    possibilities have occurred to others, so I await the deserved
    castigation.
    
    			Philip

re .8:  The devil can't destroy the planet the angel is on.  Or rather, the
requirement should be the angel and devil alternate "turns", and the angel
only need be on a planet at the end of its turn, so destroying the planet the
angel is currently on has no effect. (beyond removing a return path)

Following are some solutions to trap an angel that may only one vertical/
horizontal move per turn.

Newsgroups: sci.math
Path: decwrl!hplabs!sdcrdcf!trwrb!trwspp!spp2!stassen
Subject: Re: angels and devils
Posted: 10 Nov 86 21:33:12 GMT
Organization: TRW, Redondo Beach  CA
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

Newsgroups: sci.math
Path: decwrl!labrea!navajo!avg
Subject: Re: angels and devils
Posted: 3 Nov 86 03:58:58 GMT
Organization: Stanford University
 
References:
 
This problem seems to center on the issue of connectivity and separators.
For the angel, any two planets within a certain distance are connected
by an edge.  So far, no one has clarified "distance".
Three possible definitions are
(1) Euclidean distance, sqrt(dx^2 + dy^2);
(2) Manhattan distance, |dx| + |dy|, in which a diagonal move has length 2;
(3) "max" distance, max(|dx|, |dy|), in which a diagonal move has length 1.
 
Let's consider some small-distance cases first.  Say the angel can move
distance 1.  In Euclidean and "max" this means only rectilinear moves.
The connectivity is 4.  The devil can trap the angel in about 10 moves
by the well-known go tactic of playing a diagonal away.  Here is an example.
Let a be the angel's initial position, 1 be the devil's first move;
let b be the angel's 2nd position, 2 be the devil's 2nd move; etc.
		. . . . . . . . .
		. . . 1 . . . . .
		. 6 . . a . . . .
		. . f . b . . . .
		. 5 e d c 2 . . .
		. . 4 . 3 . . . .
		. . . . . . . . .
The rest is clear, and it is easy to try the other alternatives for the
angel and see that they are fruitless.
 
The situation is not so clear with manhattan distance; now the connectivity
is 8.  Going to distance 2, the connectivity jumps to 12 or 24,
depending on which "distance" you use.  I suspect that if you find a
way to trap the angel when it can go manhattan distance 2, it will
generalize to 100.
 
Now a theorem:
If the devil can always force the angel to move to a planet in 2 or more
moves that she was already on or could have reached in 1 move,
then the angel can be trapped.
Proof:
If the angel has an escaping strategy, then assume that she uses an
optimal escaping strategy.
Suppose the angel travels from P1 to P2 in 2 or more moves, and could
have arrived there in 1 move; then the strategy is not optimal because
the devil has gotten at least 1 "free" move.  Similarly, if P1=P2,
then the devil has gotten at least 2 free moves.  Thus, if the devil
can always force this to occur, then the angel has no escaping strategy.
QED
That isn't supposed to be rigorous; it's just supposed to convince you.
 
This theorem at least reduces the search space; an angel strategy can be
considered to fail as soon as a non-optimal move occurs;  you don't
have to grind it out to the bitter end.
 
To formalize this a little more, say the angel can "see" a planet if
she can move to it in one turn.  Keep track of planets the angel has seen
and when they were FIRST seen.  At each turn the angel must move to
a planet she sees but has never seen before.