Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!cbatt!ihnp4!fortune!stirling
From: stirling@fortune.UUCP (Patrick Stirling)
Newsgroups: sci.math
Subject: Re: angels and devils
Message-ID: <126@fortune.UUCP>
Date: Fri, 24-Oct-86 19:35:28 EST
Article-I.D.: fortune.126
Posted: Fri Oct 24 19:35:28 1986
Date-Received: Sun, 26-Oct-86 02:12:33 EST
References: <2056@princeton.UUCP> <514@aurora.UUCP>
Reply-To: stirling@fortune.UUCP (Patrick stirling)
Organization: Fortune Systems, Belmont, CA
Lines: 32


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?

>     The one-dimensional case is easy; the devil picks a sufficiently large
>distance from the angel at the initial point, methodically destroys 
>100 planets in a line, watches the angel hop wherever she pleases, repeats
>the same on the other side, then entraps her with a random squeeze between
>the barriers.
>     -- James A. Woods (ames!jaw)

Surely this wouldn't work? The angel could travel parallel to the devil's
destruction line faster than the devil can destroy planets, and thus
escape out of the ends of the barriers.

Picture:

    line of destruction:   ---------------->
    line of escape:          ================>
    line of destruction    ---------------->

I think the devil can only win if the angel doesn't know where he is,
and if he can destroy enough planets to trap the angel before the
angel realizes the situation (e.g by destroying a circle of planets
around the angel). An analogous problem would be: Two people on an infinite 
flat plane, one with bricks and mortar. Can the builder build a wall around 
the other before the other can run away? I don't think so.
patrick
{ihnp4, hplabs, amdcad, ucbvax!dual}!fortune!stirling