Re: compactness in angels/devil problem

On Feb 4, 10:23 am, Gerry Myerson <ge...@xxxxxxxxxxxxxxxxxxxxxxxxx>
wrote:
In article <Pine.BSI.4.58.0802012323330.25...@xxxxxxxxxxxxxxxxx>,
 William Elliot <ma...@xxxxxxxxxxxxxxxxxx> wrote:





On Fri, 1 Feb 2008 pauldepst...@xxxxxxx wrote:
On Feb 1, 10:06 pm, David C. Ullrich <dullr...@xxxxxxxxxxx> wrote:

What's the angels-and-devils problem?

Informal version of angels/devil theory:  The angel is on a square
chessboard which is infinite in all directions (Z x Z in other words).
For each square of the chessboard, there is a finite set of squares
which the angel can visit on the next move (you get a different problem
or question for each rule determining the finite set).  The devil and
the angel take alternate moves.  The devil moves by eating one
non-occupied square and therefore preventing the angel landing on it.
Can the devil run the angel out of moves?  (As stands, not a meaningful
problem because I haven't given a rule determining the angel's possible
moves.)

Concrete example:  Suppose the angel moves like a king in the version of
chess played in the US, England, Eastern Europe and elsewhere (in fact,
the most globally widespread version of chess.)  Then the devil can trap
the angel.

I don't believe it.

I (mostly) quote from p. 129 of Peter Winkler, Mathematical
Mind-Benders:

"An Angel flies over an infinite checkerboard, and every now and then
she must alight on a square. She can travel no more than N King-moves
in the air before she lands.

"While she's in the air, however, the Devil, who lives below the board,
can destroy any one square of his choice.

"Can the Devil trap the Angel?"

It seems it has been known for years that if N = 1 the Devil can win.
It has recently been proved that if N > 1 then the Angel can win.

The references are O Kloster, A solution to the angel problem,
http:// home.broadpark.no/~oddvark/angel/Angel.pdf
and A Mathe, The angel of power 2 wins, Comb. Prob. Comput.
16 (2007) 363-374.

--
Gerry Myerson (ge...@xxxxxxxxxxxxxxx) (i -> u for email)- Hide quoted text -

- Show quoted text -

Gerry,

I don't think any of these are references for the theorem that the
devil wins when N = 1. Any other ideas for countering William
Elliot's scepticism? Also, both the papers you cite are online. The
pdf for Mathe's paper is readily found via this link: http://amathe.dyn.elte..hu/

Paul Epstein

.

Relevant Pages

  • Re: compactness in angels/devil problem
    ... chessboard which is infinite in all directions. ... the angel take alternate moves. ... The devil moves by eating one ... non-occupied square and therefore preventing the angel landing on it. ...
    (sci.math)
  • Re: compactness in angels/devil problem
    ... chessboard which is infinite in all directions. ... For each square of the chessboard, there is a finite set of squares ... the angel take alternate moves. ... non-occupied square and therefore preventing the angel landing on it. ...
    (sci.math)
  • Re: compactness in angels/devil problem
    ... Informal version of angels/devil theory: The angel is on a square ... chessboard which is infinite in all directions. ... For each square of the chessboard, there is a finite set of squares ... The devil moves by eating one ...
    (sci.math)
  • Re: compactness in angels/devil problem
    ... Informal version of angels/devil theory: The angel is on a square ... chessboard which is infinite in all directions. ... For each square of the chessboard, there is a finite set of squares ... The devil moves by eating one ...
    (sci.math)
  • Re: compactness in angels/devil problem
    ... Informal version of angels/devil theory: The angel is on a square ... chessboard which is infinite in all directions. ... For each square of the chessboard, there is a finite set of squares ... The devil moves by eating one ...
    (sci.math)
Loading