Immaginiamo due giocatori, Alice e Bob, che si sfidano su una griglia quadrata di n righe e n colonne. Ogni casella della griglia contiene una lampadina elettrica, che può essere spenta oppure accesa.
Alice gioca per prima. Il suo compito è scegliere la configurazione iniziale della griglia, cioè il numero delle lampadine accese e la loro posizione. Bob, dal canto suo, ha a disposizione interruttori posti all’estremità di ogni riga e di ogni colonna (in tutto, dunque, 2n interruttori); azionandoli, si invertono gli stati delle lampadine della riga o della colonna corrispondente: le lampadine accese si spengono e quelle spente si accendono. Bob può azionare tutti questi interruttori nell’ordine che preferisce e per tutto il tempo che desidera.
L’obiettivo di Bob è fare in modo che, alla fine della partita, rimangano accese meno lampadine possibile: in altre parole, cerca di minimizzare il numero di lampadine accese nella configurazione finale. Alice, al contrario, cerca di fare in modo che alla fine del gioco ne restino accese il maggior numero possibile: vuole massimizzare il numero minimo di lampadine accese che Bob può ottenere azionando senza limiti gli interruttori.
Un gioco illuminante
--------------
Per capire meglio, facciamo un po’ di riscaldamento con una griglia di lato n = 3. Supponiamo che Alice imponga a Bob la configurazione iniziale qui a fianco, nella quale i cerchi bianchi corrispondono a lampadine spente e quelli neri a lampadine accese.
