El problema del ángel de Conway

Primero un ejemplo práctico (aunque no completamente preciso) del problema: Chat Noir. Es un juego en flash en el que hay un gato en una rejilla (hexagonal; en el problema original es cuadrada). Cada turno el jugador hace click en una celda (removiéndola), y el gato salta. El objetivo es rodear al gato. El juego es “posible”; eso es, se puede ganar.

La especulación. Supongamos que la rejilla es cuadrada (el gato puede saltar en ocho direcciones: arriba, abajo, izquierda, derecha, o en diagonal) y no hay posiciones marcadas previamente. Hay demostración (incluída en el artículo de Conway) de que ese juego es siempre “posible” en un tablero lo suficientemente grande (Berlekamp). ¿Pero qué sucede si el gato puede saltar mas de una casilla por turno?

En 2006 se demostró (por al menos tres investigadores desde el 2006: Kloster, Máthé, Gács) que un gato lo suficientemente agil (puede saltar dos veces por turno) puede ganar siempre, dada la estrategia apropiada, en la rejilla cuadrada (i.e. existe una estrategia ganadora para el gato).

The Angel Problem (PDF)