Perché per risolvere il gioco di Marienbad (variante del Nim) si deve far ricorso ai numeri binari?

Discutiamo prima il classico gioco del Nim, del quale il gioco di Marienbad è una variante; la tecnica risolutiva è infatti sostanzialmente la stessa.  Nel gioco del Nim vi sono due giocatori di fronte ad una serie di m file di fiammiferi, ciascuna fila contenente un certo numero di fiammiferi. A turno ogni giocatore deve togliere un certo numero di fiammiferi da una ed una sola fila (minimo uno, anche tutti), vince che toglie l'ultimo fiammifero. Per capire qual è la strategia vincente conviene scrivere i numeri dei fiammiferi di ciascuna fila in sistema binario, e si capirà presto il motivo. Invece che procedere in modo astratto, prendiamo un esempio: supponiamo di avere 3 file con rispettivamente 3,4,5 fiammiferi. Costruiamo ora la seguente tabella scrivendo 3,4,5 in binario:

  22 21 20
3 0 1 1
4 1 0 0
5 1 0 1
somma 2 1 2

Osserviamo quindi l'ultima riga ottenuta sommando gli 0 e 1 presenti nella rispettiva colonna. Esiste un numero dispari (in questo caso 1) in questa riga. Osserviamo anche che la configurazione finale, che ha come riga somma 0 0 0, non ha numeri dispari, e osserviamo infine che se un giocatore si trova davanti ad una configurazione che ha come riga somma una lista di numeri pari necessariamente, qualunque mossa lui faccia, trasforma questa riga in una riga con almeno un numero dispari (infatti deve cambiare almeno un 1 in 0 o almeno uno 0 in 1). Mettendo insieme queste osservazioni deriva che il giocatore razionale deve quindi cercare di aggiustare ad ogni mossa la parità della riga somma, di modo da portare l'avversario, alla mossa successiva, a portarsi in una configurazione con almeno un numero dispari in riga somma, che senz'altro non è vincente. Chi vince quindi? Dipende dalla configurazione iniziale: se questa configurazione ha come riga somma tutti numeri pari il primo giocatore è sicuro di perdere se il secondo gioca razionalmente, mentre se invece una configurazione ha nella riga somma almeno un numero dispari allora il primo giocatore vince se gioca razionalmente. Nel nostro esempio si presenta proprio questa seconda eventualità, per cui il primo giocatore, se razionale, vince. A conti fatti per altro si dimostra che la probabilità di avere una configurazione iniziale con almeno un dispari nella riga somma è maggiore di quella di avere tutti pari, per cui data una configurazione casuale iniziale risulta più probabile che il primo giocatore vinca, se la partita si svolge in modo razionale.

Torniamo rapidamente al gioco di Marienbad, divenuto celebre grazie al film L'anno scorso a Marienbad (1961), nel quale si presenta una piccola variante, ovvero chi toglie l'ultimo fiammifero perde. Nell'originale gioco di Marienbad la configurazione iniziale era di 16 fiammiferi disposti in 4 pile con rispettivamente 1,3,5,7 fiammiferi.

Costruiamo la tabella della posizione iniziale: 

  22 21 20
1 0 0 1
3 0 1 1
5 1 0 1
7 1 1 1
somma 2 2 4

La riga somma è interamente costituita da numeri pari per cui il primo giocatore è costretto a perdere se il secondo gioca razionalmente, questo se fosse il gioco del Nim, ma siccome nel gioco di Marienbad chi toglie l'ultimo fiammifero perde, segue che una partita razionale giocata con questa configurazione iniziale deve concludersi con la vittoria del giocatore che apre la partita.