Problema dell'angelo

Il problema dell'angelo è un problema matematico della teoria dei giochi proposto da John Horton Conway.

Formulazione

Il problema si ispira al cosiddetto "gioco dell'angelo e del diavolo"; esso consiste in una partita di scacchi tra un angelo e un diavolo, che utilizza una scacchiera infinita. Al giocatore angelo all'inizio del gioco viene assegnato un potere $k\geq 1,k\in N$ che indica che a partire dalla posizione attuale può posizionarsi su una casella vuota a cui è possibile arrivare combinando $k$ mosse tipiche del re degli scacchi. Il giocatore diavolo non si muove sulla scacchiera ma vi posiziona un "blocco" che impedisce al giocatore angelo di occupare tale casella. L'angelo può saltare una casella contenente un blocco ma non può sostare su di essa. Il gioco prevede l'alternanza tra uno spostamento dell'angelo e il posizionamento di un blocco da parte del diavolo. Lo scopo del diavolo è sistemare i blocchi in modo tale che l'angelo non possa più spostarsi per assenza di caselle di arrivo libere.

Il "problema dell'angelo" è: esiste un valore di potere $k$ sufficiente perché l'angelo possa vincere la partita, trovando sempre una casella libera?

Conway offrì una ricompensa per una soluzione generale a questo problema (100 dollari per una strategia vincente per un angelo di potere sufficiente e 1000 dollari per la dimostrazione che il diavolo può sempre vincere qualsiasi sia il potere dell'angelo).

Soluzione

Dato che il diavolo può vincere solo in un numero finito di mosse, l'unica possibilità per l'angelo di vincere è trovare sempre una mossa valida su una combinazione infinita di blocchi quindi $k$ deve essere tale da permettere questa situazione.

Verso la fine del 2006, il problema originale fu risolto quando furono pubblicate le dimostrazioni di Brian Bowditch, che provò la soluzione per un angelo con $k=4$ e di Máthé e Kloster, che trovarono la soluzione per un angelo con $k=2$.

Voci correlate

• John Horton Conway

Collegamenti esterni

• (EN) Eric W. Weisstein, Problema dell'angelo, su MathWorld, Wolfram Research.