Nim a perdere
Nim a perdere
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.
Trovare una strategia per perdere.
Sono il cuoco della nazionale!
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".
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.
-
- Messaggi: 99
- Iscritto il: 14 gen 2010, 14:56
- Località: Livorno
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"?
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!