Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!lll-crg!nike!ucbcad!ucbvax!hplabs!sdcrdcf!burdvax!psuvax1!berman
From: berman@psuvax1.UUCP (Piotr Berman)
Newsgroups: sci.math
Subject: Re: angels and devils
Message-ID: <2323@psuvax1.UUCP>
Date: Sun, 9-Nov-86 20:53:53 EST
Article-I.D.: psuvax1.2323
Posted: Sun Nov  9 20:53:53 1986
Date-Received: Mon, 10-Nov-86 05:44:16 EST
References: <2056@princeton.UUCP> <514@aurora.UUCP> <126@fortune.UUCP> <188@mck-csc.UUCP> <255@BMS-AT.UUCP> <742@ukecc.UUCP>
Reply-To: berman@psuvax1.UUCP (Piotr Berman)
Distribution: net
Organization: Pennsylvania State Univ.
Lines: 57
Keywords: keep it simple

>Ok, lets look at the simplest case. [...] the devil destroy 1 planet [per day
>while] the angel can move 1 planet per day. If we assume that the devil and 
>angel know nothing about each others actions (except we will let the devil 
>know the angels starting position) then the question boils down to this: 
>at what distance must the devil begin destroying planets so that the angel 
>will be unable to get around the devils barrier?
>	The formula for the number of planets that the devil must destroy to
>successfully trap the angel is simply the equation for the circumference of
>a circle. This follows from the principle that the devil wants to destroy the 
>minimum number of planets to achieve his task ( to big an assumption? ). If
>this is true then we have 2piR planets to be destroyed before the angel
>is trapped with a finite number of planets to live on. 
>[However during this time angels makes 2piR moves and is outside the circle.]
>Give them each total knowledge of each others actions and the answer remains 
>the same....
>
To the contrary.  First, we shall define what does it mean to 'move 1 planet
per day'.  Assume that the angel can move to planets in the distance 1 or
sqrt(2).  Select a large R.  Assume the angel starts at (0,0).
During first R/2 moves the devil destroys planets with coordinates of the
form (R,16k) (-R,16k) (16k,R) (16k,R) where k is integer between -R/16
and R/16.  Then it destroys some constant number of planets on each corner
of the resulting square:

  ***   *   *   *   *   *   *   *   *   *   *   *   ***
  *                                                   *
  *                                                   *
                                                           This is the
  *                                                   *    rough pattern

  *                                                   *

  *                                                   *

  *                                                   *

  *                                                   *

  *                                                   *
  *                                                   *
  ***   *   *   *   *   *   *   *   *   *   *   *   ***

Now the devil starts to watch carefully the angel.  If the angel follows
a diagonal toward a corner, the devil destroys more planets on both sides
of the corner.  If the angel is closer to one of the sides of the square
than to the other sides, the devil destroys the planet which is the closest 
on the square perimeter to the angel, but is not destroyed yet.  Draws are
solved randomly.  Now the angel cannot avoid the following: by the time
it will approach the square perimeter, the situation will be like that:

	 ***
          A

Now the angel can move along the perimeter, but it will never catch up
with the destruction, until it will be cornered.  I am sure that this 
strategy is not optimal.  However, I do not see any way to improve it
so that twice faster angel can be trapped as well.