Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!cbatt!cbuxc!cbuxb!cbrma!aka
From: aka@cbrma.UUCP (Andy Kashyap)
Newsgroups: sci.math
Subject: Re: angels and devils
Message-ID: <5349@cbrma.UUCP>
Date: Tue, 4-Nov-86 14:52:56 EST
Article-I.D.: cbrma.5349
Posted: Tue Nov  4 14:52:56 1986
Date-Received: Wed, 5-Nov-86 05:31:05 EST
Reply-To: aka@cbrma.UUCP (Andy Kashyap)
Organization: AT&T-BL, RMAS, Columbus
Lines: 50

References:

>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.
[...]
>Bernie Gunther
>
>UUCP: {ihnp4, harvard, genrad, ...}!mit-eddie!mck-csc!bmg
>ARPA: bmg@mit-xx

Although the angel can travel 100 planets a day, it is not clear
to me from the problem that it takes a hundred destroyed planets
in a row to block the angel. I'll assume that it takes a single
destroyed planet to block the angel.

With that assumption, the single dimension case is too trivial.

The 2D plane:

Given the angel somewhere, it is clear that the devil must move far enough
away from the angel to have time to build a wall (of destroyed planets)
around in a circle to trap the angel before the angel can escape.

Keeping the angel at the center, the number of planets on the wall grows
linearly with the distance from the center and faster. That is the devil
must destroy about 628(*) planets for every 100 planets he moves away
from the angel. Since he can only destroy one planet a day he can never
trap the angel. The devil is 1/629 times slower than he needs to be.

(*) for perfectionists: the exact value is 2 * pi * r, where r=100.

Other conclusions:
Had the devil been able to destroy 628 planets a day, the problem would
be non-deterministic. For greater 629 planets a day, he would for sure
be able to trap the angel and for less than 628 planets a day, he can not.
-- 

+---------------------------------------------------------------------------+
: What is reality anyway but a collective hunch.       : Andy Kashyap       :
: Reality is fine in small doses ...                   : AT&T Bell Labs     :
:     ... but as a life style, it's too confining.     : Columbus OH        :
:                              -- The Tonight Show     : ..!cbosgd!cbrma!aka:
+---------------------------------------------------------------------------+