Combinatorics, Probability and Computing

Table of Contents - 2007 - Volume 16, Issue 03  

Paper

The Angel of Power 2 Wins

ANDRÁS MÁTHɆ

a1 Department of Analysis, Eötvös Loránd University, Pázmány Péter sétány 1/c, 1117 Budapest, Hungary (e-mail: amathe@cs.elte.hu http://amathe.web.elte.hu)

Abstract

We solve Conway's Angel Problem by showing that the Angel of power 2 has a winning strategy.

An old observation of Conway is that we may suppose without loss of generality that the Angel never jumps to a square where he could have already landed at a previous time. We turn this observation around and prove that we may suppose without loss of generality that the Devil never eats a square where the Angel could have already jumped. Then we give a simple winning strategy for the Angel.

(Received August 02 2006)

(Revised October 18 2006)

Footnotes

† Partially supported by the Hungarian Scientific Research Fund grant no. T 49786.