Re: compactness in angels/devil problem

Gerry Myerson <gerry@xxxxxxxxxxxxxxxxxxxxxxxxx> writes:
In article <Pine.BSI.4.58.0802012323330.25231@xxxxxxxxxxxxxxxxx>,
William Elliot <marsh@xxxxxxxxxxxxxxxxxx> wrote:

On Fri, 1 Feb 2008 pauldepstein@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.

Presumably 4 devils can trap a 2-Angel? But can 3 or 2?

Phil
--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration
.

Relevant Pages

  • Re: compactness in angels/devil problem
    ... For each square of the chessboard, there is a finite set of squares ... 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. ... 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
    ... boards to conclusions about the infinite case. ... "compactness argument" and which topology is the compactness concept ...  Thedeviland the angel take alternate moves. ... by eating one non-occupied square and therefore preventing the angel ...
    (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
    ... 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)