Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!clyde!cbatt!ihnp4!ihlpg!tan
From: tan@ihlpg.UUCP (Bill Tanenbaum)
Newsgroups: sci.math
Subject: Re: angels and devils
Message-ID: <2636@ihlpg.UUCP>
Date: Tue, 4-Nov-86 13:17:40 EST
Article-I.D.: ihlpg.2636
Posted: Tue Nov  4 13:17:40 1986
Date-Received: Thu, 6-Nov-86 01:01:39 EST
References: <1056@navajo.STANFORD.EDU>
Organization: AT&T Bell Labs, Naperville, IL
Lines: 32

< Now a theorem:
< If the devil can always force the angel to move to a planet in 2 or more
< moves that she was already on or could have reached in 1 move,
< then the angel can be trapped.
< Proof:
< If the angel has an escaping strategy, then assume that she uses an
< optimal escaping strategy.
< Suppose the angel travels from P1 to P2 in 2 or more moves, and could
< have arrived there in 1 move; then the strategy is not optimal because
< the devil has gotten at least 1 "free" move.  Similarly, if P1=P2,
< then the devil has gotten at least 2 free moves.  Thus, if the devil
< can always force this to occur, then the angel has no escaping strategy.
< QED
< That isn't supposed to be rigorous; it's just supposed to convince you.
------
Your theorem may be correct, but your "proof" is far from convincing.
------
< This theorem at least reduces the search space; an angel strategy can be
< considered to fail as soon as a non-optimal move occurs;  you don't
< have to grind it out to the bitter end.
< To formalize this a little more, say the angel can "see" a planet if
< she can move to it in one turn.  Keep track of planets the angel has seen
< and when they were FIRST seen.  At each turn the angel must move to
< a planet she sees but has never seen before.
------
Even if your theorem is correct, I do not understand how it justifies your
conclusion.  The theorem says that if the devil can ALWAYS force a 
"suboptimal" move, the angel can be trapped.  You then conclude that if
the devil can force a suboptimal move ONCE, the angel can be trapped.
That may be true, but it certainly doesn't follow from your theorem.
-- 
Bill Tanenbaum - AT&T Bell Labs - Naperville IL  ihnp4!ihlpg!tan