Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!think!mck-csc!bmg
From: bmg@mck-csc.UUCP (Bernard M. Gunther)
Newsgroups: sci.math
Subject: re: angels and devils
Message-ID: <188@mck-csc.UUCP>
Date: Wed, 29-Oct-86 01:04:13 EST
Article-I.D.: mck-csc.188
Posted: Wed Oct 29 01:04:13 1986
Date-Received: Wed, 29-Oct-86 08:54:34 EST
References: <2056@princeton.UUCP> <514@aurora.UUCP> <126@fortune.UUCP>
Organization: McKinsey & Company, Cambridge Systems Center
Lines: 56

> 
> As a reminder, the problem is:
> Planets arranged at the grid points on an infinite plane. An angel
> is on a planet, and can travel up to 100 planets' distance in a day.
> There is a devil who can destroy one planet anywhere each day. Can
> the devil trap the angel?
>

 
I know this probably isn't a total solution to the Angel and Devil problem
and I'm not being rigorous, but this is a possible way of approaching the
solution...  

Assumption:

The problem is solvable in a one dimensional case.  This is effectively a
case where there is only a single row of planets stretching on to
infinity.  ie.:

     <--............A..................-->

In this case, is is provable that the devil can trap the angel by building
a single block of 100 anywhere and then building another block of 100 at
least 100*100*2 spaces away and then slowly closing in on the angel.


From this follows:

In the case of a space consisting of 2 rows of planets, it is also
possible for the devil to trap the angel.

   <--- ...............A.................... --->
        ....................................

This is done by building a block 100 unit wide and 2 deep and then
building another block (100*100*2)*2 away from the first block and then
slowly closing in.  


For a set of arbitrary number of rows, the two stopping blocks must be
located (100*100*2)*N units away from each other.


Therefore: since a two dimensional field is in reality just equivalent to
the case where the number of rows (N) goes to infinity, the blocks must
be built an infinite distance from each other and therefore, the angel
cannot be trapped.  


I would be very interested to hear anyone else's comments on this
solution.

Bernie Gunther

UUCP: {ihnp4, harvard, genrad, ...}!mit-eddie!mck-csc!bmg
ARPA: bmg@mit-xx