Nim a perdere

[Anér]

Ricordo che il nim è il gioco di Alberto e Barbara in cui ci sono un numero finito di pile di monete (anch'esse in numero finito in ogni pila) e a turno i due giocatori scelgono una pila e tolgono qualche moneta (anche tutte) dalla pila; vince chi riesce a togliere l'ultima moneta.

Trovare una strategia per perdere.

[ng]

Chi comincia? Dobbiamo trovare una strategia perdente per il primo che comincia o l'altro?

[Anér]

Bisogna trovare una strategia perdente per chi ce l'ha, ovvero devi stabilire in quali casi ce l'ha Alberto (il primo) e in quali Barbara (il secondo); in ogni caso c'è un giocatore che ha la strategia perdente.

[Reginald]

Anér, ti andrebbe di mostrare la soluzione di questo?

[Zephyrus]

Chiamiamo g di n il numero dei gettoni presenti in una pila n.
Ordiniamo tutte le pile per numero di gettoni che contengono. Se c'è un numero pari di pile per ogni numero di gettoni esistente (es. 2 pile da 3, 2 da 4, 6 da 9, 8 da 1), e se esiste almeno una coppia di pile con numero gettoni >1, allora vince (cioè può perdere) il secondo. Infatti, se Alberto prende un certo numero di gettoni da una pila k, Barbara ne prende altri da una pila j tale che g di j fosse= a g di k, e riporta le due pile all'uguaglianza. Procedendo in questo modo, prima o poi dopo la mossa di Barbara ci saranno tutte coppie di pile con numero di gettoni uguale a 1 o a 0, una sola > di 1, che chiameremo d. Continuando, o Alberto annullerà una delle due pile della coppia d, e allora Barbara lascia un gettone nella seconda, in modo che rimanga un numero dispari di pile con 1; oppure Alberto lascia un solo gettone in una delle due pile, e Barbara elimina l'altra. In entrambe queste situazioni c'è vittoria per Barbara.

Chiaramente esistono altri casi. Notiamo subito che, se c'è un numero pari di pile 1, oltre ad altre pile , è come se non ci fosse nulla, mentre se ce n'è un numero dispari, qualsiasi situazione viene invertita. Ora, può capitare che uno o più numeri di gettoni siano contenuti in un numero dispari di pile (es. 3 da 6, 2 da 8, 5 da 2). Vediamo chi può ricondursi alla "situazione vincente". Contiamo quanti sono i numeri dispari di pile che contengono lo stesso numero di gettoni (nell'esempio 2) e contiamo anche gli altri numeri (nell'esempio 1), chiamando i due risultati rispettivamente "e" ed "f".

[Zephyrus]

Adesso però le cose si complicano alla grande ...

[Gogo Livorno]

Conoscete il trucco del sistema binario nel nim? =D

Sennò sono estremamente lieto di spiegarvelo, con quello si risolve tutto!

[Reginald]

Quello del nim normale si...non sono riuscito a usarlo su questo però..

[Anér]

Zephyrus, controlla bene tutto quello che hai scritto, ad esempio se ho 2 pile da 2 è il secondo giocatore che riesce a perdere, ma se ho 2 pile da 1 è il primo giocatore che riesce (ed è obbligato) a perdere.

Negli altri casi occorre prestare molta attenzione, perché se il secondo giocatore porta una certa pila al livello di un'altra, il primo giocatore può fare una mossa del genere anche lui: ad esempio se le pile sono 1 3 2 5 4 può accadere che il primo tolga la moneta singola, il secondo riduca a 2 la colonna da 3 e poi il primo riduca a 4 la colonna da cinque.

Ricordare la strategia del nim normale, quella per vincere, è un'ottima idea, benché qui sia necessario riuscire a perdere.

In effetti qui riesce a perdere chi lascia un numero dispari di monete singole, e chi ha la possibilità di decidere la parità di monete singole quando arriva all'ultima colonna "molteplice"?

[Zephyrus]

Effettivamente la soluzione che ho dato è completamente errata... proverò a modificare qualcosa...
L'unica cosa (ovvia) che mi viene in mente, è che, se esiste una strategia per vincere a nim, questa consente a chi l'adotta di scegliere la parità degli 1 alla fine, quindi anche di perdere.

[Anér]

Esatto. Formalizza un po' tutto (dimostra che la strategia tradizionale funziona per perdere solo se a un certo punto sei libero di abbandonarla, sennò finisci per vincere!), e hai finito.