Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!vrdxhq!bms-at!stuart
From: stuart@bms-at.UUCP (Stuart D. Gathman)
Newsgroups: sci.math
Subject: Re: angels and devils
Message-ID: <264@bms-at.UUCP>
Date: Sun, 9-Nov-86 16:55:29 EST
Article-I.D.: bms-at.264
Posted: Sun Nov  9 16:55:29 1986
Date-Received: Mon, 10-Nov-86 05:32:47 EST
References: <1056@navajo.STANFORD.EDU> <244@sjuvax.UUCP>
Organization: Business Management Systems, Inc., Fairfax, VA
Lines: 134
Summary: Some results.


Theorem 1:

	If the devil can trap the angel when she can move up to N^2
	planets per turn but cannot move through any destroyed
	planets

		then

	the devil can trap the angel when she can move up to N planets
	per turn and only the last planet in the move need be
	undestroyed.

"Proof":

	In the latter case, the devil can regard the universe as
	consisting of N x N squares.  He can completly obliterate
	an N x N square in N^2 turns.  During this time the angel
	can move N^3 planets, or N^2 N x N squares.  The angel
	cannot move through an obliterated N x N square.

This resolves the question of whether the angel can 'hop' planets.

Corollary:

	If the angel can move diagonally, as well as horizontally
	and vertically, N squares per turn, (and can perhaps hop planets)

		and

	the devil has a strategy that will trap the angel when
	she can move (2N)^2 square per turn, (but can't hop planets)

		then

	the devil can trap the angel.

"Proof":

	The devil regards the angel as moving 2N planets per turn
	with ability to hop.  A diagonal move consists of two moves:
	one horizontal and one vertical.  The result follows from the
	above theorem.


Now we need only worry about horizontal and vertical moves (in any
combination per turn) that cannot move through a destroyed planet.


Theorem 2: (From an assertion due to Allen van Gelder)

	Any angel move that puts the angel nearer to an earlier move
	than she was in her previous move will at worst allow the
	devil to win.  If the angel can escape, she can do so without
	making any such moves.

"Proof":

	Trapping the angel means that the devil has (among other things)
	destroyed planets in a "shell" (of some unspecified shape)
	surrounding the angel.  Any backtracking by the angel simply
	gives the devil more time to complete his shell.


The general character of the devil's strategy is now apparent:

	Imagine a "shell" of suitable size surrounding the angel.
	Proceed to destroy planets to complete this shell in a
	sequence determined by the angel's subsequent moves.  The
	portions of the shell nearest to the angel should be 
	completed first.

This is in fact easily accomplished for N=1 (no diagonal moves).
(This is left as an excercize for the reader.)  What we would like
to have now is a theorem showing that if the devil can trap the
angel in N moves, then he can trap the angel in N + 1 (or 2N, or
N^2, etc.) moves.  (Assuming we are rooting for the devil.)  
We need only deal with the "standard" game 
(no diagonal moves, no planet hopping).

My suspicion is that the angel cannot be trapped when N>1.  At least
I cannot come up with a general strategy.  (N=1 with diagonals is like
N=4 without.)  Although I can't prove this,
I think the proof would be something like this:


Conjecture 3:

	If and only if the devil can partition (confine the angel
	to one side of) the universe, then he can trap the angel.  
	The partition is an imaginary one and is enforced only
	when the angel approaches.

"Proof":

	The devil can trap the angel with four such partitions.
	The converse is clear.  If the devil cannot even partition the
	universe, he cannot trap the angel.

Caveat:

	What is not clear is whether the devil can adequately 
	"defend" more than one partition at once.



Conjecture 4:

	The devil can partition the universe if and only if he can
	destroy as many planets in distinct horizontal (vertical)
	positions as the angel can move in one turn.

"Proof":

	The devil can always secure the point of the partition nearest
	the angel.  Therefore, we need only consider the case where
	the angel and devil are adjacent within N squares.  
	Since backtracking is fatal to the angel (by theorem 2),
	we can assume they are moving in the same direction.

	* = devil  . = angel

N=1:	*   *		the devil wins.
	. . *

N=2:	*   *   *   and so on, stalemate, the angel wins ?!?! (see the
	.   .   .   caveat in proof of 3.  (Other cases similar.)

N=3:	* . *		the angel crosses the partition.
	. 

and so on.  (This does not exactly cover all cases. :-)
-- 
Stuart D. Gathman	<..!seismo!{vrdxhq|dgis}!BMS-AT!stuart>