Nim a perdere

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
Anér
Messaggi: 720
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

Nim a perdere

Messaggio da Anér » 05 gen 2010, 10:44

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.
Sono il cuoco della nazionale!

ng
Messaggi: 1
Iscritto il: 05 gen 2010, 15:23

Messaggio da ng » 05 gen 2010, 15:25

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

Avatar utente
Anér
Messaggi: 720
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

Messaggio da Anér » 07 gen 2010, 18:33

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.
Sono il cuoco della nazionale!

Avatar utente
Reginald
Messaggi: 137
Iscritto il: 24 gen 2009, 15:52
Località: Trento

Messaggio da Reginald » 25 mar 2010, 15:58

Anér, ti andrebbe di mostrare la soluzione di questo?
Ci sono due errori che si possono fare lungo la via verso la verità...non andare fino in fondo, e non iniziare.
Confucio

Zephyrus
Messaggi: 40
Iscritto il: 10 feb 2010, 14:08
Località: Vicenza

Messaggio da Zephyrus » 25 mar 2010, 19:40

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".
Ultima modifica di Zephyrus il 27 mar 2010, 10:50, modificato 1 volta in totale.

Zephyrus
Messaggi: 40
Iscritto il: 10 feb 2010, 14:08
Località: Vicenza

Messaggio da Zephyrus » 26 mar 2010, 14:04

Adesso però le cose si complicano alla grande :roll: ...
Ultima modifica di Zephyrus il 27 mar 2010, 10:52, modificato 1 volta in totale.

Gogo Livorno
Messaggi: 99
Iscritto il: 14 gen 2010, 14:56
Località: Livorno

Messaggio da Gogo Livorno » 26 mar 2010, 20:39

Conoscete il trucco del sistema binario nel nim? =D

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

Avatar utente
Reginald
Messaggi: 137
Iscritto il: 24 gen 2009, 15:52
Località: Trento

Messaggio da Reginald » 26 mar 2010, 20:49

Quello del nim normale si...non sono riuscito a usarlo su questo però.. :oops:
Ci sono due errori che si possono fare lungo la via verso la verità...non andare fino in fondo, e non iniziare.
Confucio

Avatar utente
Anér
Messaggi: 720
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

Messaggio da Anér » 26 mar 2010, 22:44

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"?
Sono il cuoco della nazionale!

Zephyrus
Messaggi: 40
Iscritto il: 10 feb 2010, 14:08
Località: Vicenza

Messaggio da Zephyrus » 27 mar 2010, 09:33

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.

Avatar utente
Anér
Messaggi: 720
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

Messaggio da Anér » 27 mar 2010, 21:03

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.
Sono il cuoco della nazionale!

Rispondi