Ogni giocatore prende, al suo turno, un numero qualsiasi di oggetti, ma attenzione: può prenderli solamente da una riga per ogni turno.
Si può scegliere se essere primi o secondi a inziare il gioco.
Bisogna trovare una strategia che vi permetta di vincere, e specificare se bisogna cominciare per primi o per secondi.
Segnalato da cip999
32 commenti:
Innanzitutto, manca un piccolo accorgimento: se non viene specificata la regola che afferma "Un giocatore deve necessariamente prendere un numero di oggetti che non sia 0", tutte le partite sono destinate ad arrivare a un punto di stallo, nel quale nessuno dei due giocatori pescherà più nulla...
Se tale regola viene specificata allora stiamo parlando della seconda variante del magnifico gioco del "Nim" (la prima prevede che il giocatore peschi l'ultimo oggetto presente anzichè obbligare l'altro a pescarlo)... Il gioco del Nim prevede inoltre che i giocatori possano inizialmente concordare quale sia la disposizione degli oggetti e il loro numero...
Ti spiegherei volentieri la strategia completa, ma sarebbe necessario far riferimento a concetti della teoria dei giochi e di calcolo binario abbastanza complessi per chi abbia almeno un'infarinatura di ciò (puoi comunque trovare su internet decine di siti che spiegano ciò nel dettaglio, se ti interessa). Fare l'elenco delle configurazioni "sicure" che ti portino dalla prima mossa fino alla vittoria è una cosa fin troppo lunga e una sorta di spreco di energie (come credo tu possa immaginare sono varie decine di possibilità), quindi in bocca al lupo a chi abbia voglia di trovarle tutte...
quello che posso dirti senza troppa fatica (e ci sarai sicuramente arrivato anche da solo se ci hai pensato un po' su o se ci hai giocato abbastanza) è che delle ottime combinazioni da realizzare (o a cui puntare) nel tuo turno per avere la vittoria quasi assicurata (ovviamente se il tuo avversario ne realizza una dopo di te sarà lui a vincere) sono:
- 1/2/3
- 2/4/6
- 1/1/1
- 1/4/5
- o due gruppi composti dallo stesso numero di oggetti.
chiaramente ad ogni turno si deve peacare un numero diverso da 0 di oggetti. quelle che tu hai proposto sono alcune situazioni in cui chi le ha create avrà la vittoria certa (o quasi). ora però dovresti trovare(ma da quello che ho letto penso che tu l'abbia già trovato o ci sia molto vicino) il modo di arrivare a queste combinazioni, che, anche essendo abbastanza lungo da spiegare, può essere sintetizzato in poche righe. adesso però ho già detto troppo e lascio a walter il compito di rispondere.
Se cominci per primo la soluzione e':
prendere come prima mossa tutti gli oggetti MENO UNO da una qualsiasi fila.
Tale oggetto poi lo lasci per l'ultima presa dell'avversario, giocando di conseguenza alle sue prese.
Cosi' facendo vinci di sicuro.
Precisazione:
se si arriva alla situazione
- fila 1 vuota
- fila 2 una biglia
- fila 3 una biglia
- fila 4 completa
devi prendere ancora tutte le biglie MENO UNA della fila 4 (completa).
A questo punto rimangono tre file con un oggetto e l'avversario prende per forza per ultimo.
Secondo me per vincere bisogna iniziare per secondi.
ed agire in questo senso.
se il nostro avversario nella prima fila prende 1 oggetto io completerò la fila prendendone 2
viceversa se ne prende 2 io la completerò prendendone il rimanente in questo caso 1.
così facendo iniziera' anch'esso la seconda fila ed io prendero sempre il restante degli oggetti al fine di completare la fila. così fino all'ultima fila che come abbiamo detto visto inizierà sempre lui, di conseguenza
in base all'oggetto o agli oggetti che prenderà questa volta io non li prenderò tutti ma nè lascerò soltanto uno obbligandolo a prenderlo per ultimo.
Ciao,
la mia soluzione è:
il primo che muove vince, e lo fa togliendo la colonna da 4 e passando qiundi da una configurazione 3/4/5/6 ad una 3/5/6.
Prima del ragionamento, pongo un paio di definizioni, tanto per intenderci.
Definisco "posizione perdente" usando il metodo ricorsivo:
- una posizione è perdente se colui che muove NON è in grado in nessun modo, con una sola mossa, di passare ad una posizione perdente "più semplice", dove con "più semplice" intendo con una colonna in meno oppure, a parità di colonne, con meno elementi.
- la posizione perdente più semplice di tutte è naturalmente 1.
Di contro, una "posizione vincente" è una non perdente, ovvero una posizione dalla quale è possibile in una sola mossa passare ad una perdente.
Esempi: 1/2 è una posizione vincente, perchè in una mossa passo a 1 che è perdente; 2/2 è una posizione perdente perchè con una mossa posso solo passare o a 2 o a 1/2, entrambe posizioni vincenti.
Da una posizione perdente, quindi, con una mossa si può solo andare verso posizioni vincenti, mentre da una vincente si può passare anche a posizioni vincenti, ma sempre ad almeno una perdente.
Ora spiego il ragionamento. Lo scopo è trovare TUTTE le posizioni perdenti. La definizione che ho dato fornisce un medodo "costruttivo" per la ricerca: basta andare dalle posizioni perdenti più semplici verso le più complesse.
a) posizioni perdenti da 1 sola fila:
- 1
b) posizioni perdenti da 2 file, in ordine di complessità:
- 2/2
- 3/3
- 4/4
- 5/5
Infatti, chi ha la mossa in una di queste pos.,non può far altro che o togliere tutta una fila, così che l'avversario lo porti a 1 in una mossa, oppure togliere parte di una fila, così che l'avversario lo porti ad una pos. perdente più semplice in una mossa, pareggiando l'altra fila (es. 5/5 --> 5/3 --> 3/3); una volta arrivati a 2/2, o si toglie una fila come prima, oppure si lascia l'avversario con 1/2, il quale ci lascierà con 1.
c) posizioni perdenti da 3 file, in ordine di complessità:
- 1/1/1 : banale
- 1/2/3 : avendo la mossa, si è costretti a togliere una fila esponendosi alla posizione perdente di 2 file pareggiate, oppure ad avere 1/1/x con x>1, esponendosi alla precedente 1/1/1
- 1/4/5 : si è costretti a togliere una fila o a cadere, in un paio di mosse, in 1/2/3
- 2/4/6 : si è costretti a togliere una fila o a cadere in un paio di mosse in 1/2/3 o 1/4/5
- 3/5/6 : si è costretti a togliere una fila o a cadere in un paio di mosse in 2/4/6, 1/4/5 o 1/2/3
E' abbastanza intuitivo come si costruisce una posizione perdente da 3 colonne, date le precedenti meno complesse: si cercano combinazioni che abbiano 1 numero uguale a una delle precedenti, ma almeno 2 numeri "appena" diversi da ciascuna di esse: in questo modo si è praticamente costretti in una mossa a generare una combinazione che è distante una sola mossa da una posizione perdente più semplice.
Adesso è fatta: a partire da 3/4/5/6, basta togliere la fila da 4 per cadere in 3/5/6, che è una posizione perdente da 3 file...da lì, potrò sempre forzare l'avversario a rimanere in posizioni perdenti via via più semplici, fino ad arrivare alla fine, cioè a 1.
Una dimenticanza sul punto c) posizioni perdenti da 3 file: in ogni posizione citata è possibile anche muovere generando due colonne "pareggiate" e una no: anche in questo caso l'avversario ci porterà verso una posizione perdente, togliendo l'altra colonna. Esempio: 1/4/5 --> 1/4/4 --> 4/4.
ok inizierei io ed agirei così:
1 fila tre perle ne prendo due ed obbligo l'avversario a prendere l'ultimo.
2 fila 4 biglie ne prendo tre ed obbligo l'avversario a prendere l'ultimo.
3 fila 5 monete ne prendo quattro ed obbligo l'avversario a prendere l'ultimo.
4 fila sei fiammiferi ne prendo cinque ed obbligo l'avversario a prendere l'ultimo.
mi sa che non ho capito il quesito. Pensavo si trattasse di far prerndere all'avversario l'ultimo oggetto, non un solo oggetto.
Ci riprovo da capo.
cip999 ti prego di definire meglio lo scopo del gioco. Saro' io un po' strambo ma non riesco a capire se:
- si tratta di lasciare l'avversario con un solo tipo di oggetto dei quattro (biglie, monete, fiammiferi e perle), ed allora e' impossibile poiche' lui puo' prendere oggetti da qualsiasi fila e ne avra' sempre minimo 2 oggetti diversi.
- si tratta di far prendere all'avversario l'ultimo oggetto di una fila, allora e' un altro conto
- invece si tratta di far prendere l'avversario l'ultimo di tutti gli oggetti (18) presenti sul tavolo, ed e' un altro paio di maniche.
Grazie mille.
credo di aver trovato la soluzione: vince il giocatore che muove per
primo e la strategia vincente è prendere tutti i 4 elementi della
seconda fila.
prima di spiegare la stretegia nel dettaglio, introduco brevemente la
notazione che andrò ad utilizzare:
con [a,b,c,d] indico gli elementi residui suddivisi per fila, ad
esempio la situazione di partenza è [3,4,5,6]; [2,3,5] indica una
situazione in cui rimangono tre file, contenenti rispettivamente 2
oggetti, 3 oggetti e 5 oggetti (per semplicità ometto le file con zero
elementi)
quando rimangono pochi elementi, la soluzione del gioco è immediata e
può essere sintetizzata tremite i seguenti casi significativi:
caso 1: [1]
ovviamente chi muove perde, essendo costretto a prendere l'ultimo
elemento
caso 2: [N]
chi muove vince, prendendo (n-1) elementi e lasciando l'avverssario in
una situazione di "caso 1".
caso 3: [1,1]
chi muove vince, prendendo uno dei due elementi residui e lasciando
l'avverssario in una situazione di "caso 1".
caso 4: [1,N]
chi muove vince, prendendo tutti gli elementi della seconda fila e
lasciando l'avverssario in una situazione di "caso 1".
caso 5: [2,2]
chi muove perde. se prende un solo elemento, lascia l'avversario in
[2,1] che è posizione vincente già vista nel "caso 4"; se prende due
elementi invece lascià l'avversario in [2] che è una posizione vincente
del tipo "caso 2". In entrambi i casi quindi chi muove perde.
caso 6: [N,N]
chi muove perde. se prende tutti gli elementi di una fila lascerà
l'avversaio in [N], che è una posizione vincente del tipo "caso 2"; se
prende (n-1) elementi lascerebbe invece l'avversario in [1,N],
posizione vincente del tipo "caso 4"; se ne prende (n-2), l'avversario
può rispondere prendendone (n-2) dall'altra fila ed il primo giocatore
si ritrova in [2,2] che è una posizione perdente del tipo "caso 5".
Infine, se chi muove prende un numero X di elementi, l'avversario può
rispondere prendendo anche lui X elementi dall'altra fila ed il primo
giocatore si ritrova di nuovo in [N,N] (ma con N decrementato rispetto
a prima): è una situazione ricorsiva in cui chi muove per primo può
solo ritardare la sconfitta.
caso 7: [1,1,1]
chi muove perde: a questa posizione segue necessariamente [1,1] che è
una posizione vincente ("caso 3").
caso 8: [1,2,3]
chi muove perde: qualunque delle sei mosse a disposizione
dell'avversario porta ad una posizione vincente per il primo giocatore:
8.1 [2,3] basta rispondere [2,2] per ricadere nel "caso 5"
8.2 [1,1,3] basta rispondere [1,1,1] per ricadere nel "caso 7"
8.3 [1,3] è una posizione vincente del tipo "caso 4".
8.4 [1,2,2] basta rispondere [2,2] per ricadere nel "caso 5"
8.5 [1,1,2] basta rispondere [1,1,1] per ricadere nel "caso 7
8.6 [1,2] è una posizione vincente del tipo "caso 4".
caso 9: [1,4,5]
chi muove perde: qualunque delle dieci mosse a disposizione
dell'avversario porta ad una posizione vincente per il primo giocatore:
9.1 [4,5] basta giocare [4,4] per ricadere nel "caso 6"
9.2 [1,3,5] basta rispondere [1,2,3] per ricadere nel "caso 8"
9.3 [1,2,5] basta rispondere [1,2,3] per ricadere nel "caso 8"
9.4 [1,1,5] basta rispondere [1,1,1] per ricadere nel "caso 7"
9.5 [1,5] è una posizione vincente del tipo "caso 4".
9.6 [1,4,4] basta giocare [4,4] per ricadere nel "caso 6"
9.7 [1,3,4] basta rispondere [1,2,3] per ricadere nel "caso 8"
9.8 [1,2,4] basta rispondere [1,2,3] per ricadere nel "caso 8"
9.9 [1,1,4] basta rispondere [1,1,1] per ricadere nel "caso 7"
9.10 [1,4] è una posizione vincente del tipo "caso 4".
dicevamo che la strategia vincente è prendere tutti i 4 elementi dalla
seconda fila, lasciando quindi l'avversario in [3,5,6]. Ora
l'avversario ha a disposizione 3+5+6=14 mosse diverse, ovvero:
[2,5,6]
[1,5,6]
[5,6]
[3,4,6]
[3,3,6]
[2,3,6]
[1,3,6]
[3,6]
[3,5,5]
[3,4,5]
[3,3,5]
[2,3,5]
[1,3,5]
[3,5]
vediamo come poter volgere a nostra favore ognuna di queste:
situazione A:
nel caso ci trovassimo in [5,6], [3,3,6], [3,6], [3,5,5], [3,3,5],
[3,5] sarebbe per noi facile prendere un numero opportuno di elementi
per lasciare l'avversario in una situzione del tipo [N,N] che come
abbiamo visto è una situazione perdente ("caso 6").
sitauzione B:
se ci troviamo in [2,3,6], [1,3,6], [2,3,5], [1,3,5], potremmo prendere
un numero opportuno di elmenti per mettere l'avversario in [1,2,3] da
cui posso raggiungere una posizione vincente in un paio di mosse al
massimo: ad [1,2,3] l'avversaio può rispondere nei seguenti sei modi:
B1: [2,3] e noi risponderemmo con [2,2] lasciandolo in posizione
perdente "caso 5".
B2: [1,1,3] e noi risponderemmo con [1,1,1], lasciando l'avversario in
posizione perdente "caso 7". B3: [1,3] che è già un posizione vincente
del tipo "caso 4".
B4: [1,2,2] a cui rispondremmo con [2,2] riconducendoci al "caso 5"
B5: [1,1,2] a cui si risponde con [1,1,1], lasciando l'avversario in
posizione perdente "caso 7".
B6: [1,2] che è già una posizione vicente del tipo "caso 4".
situazione C:
se ci troviamo in [2,5,6], [3,4,6] [3,4,5], possiamo rispondere con
[2,4,6]. L'avversario a questo punto potrebbe muovere in dodici modi
differenti:
C1: [1,4,6] a cui si risponde con [1,4,5], posizione vincente del tipo
"caso 9"
C2: [4,6] a cui si risponde con [4,4], lasciando l'avversario in
posizione perdente del tipo "caso 6"
C3: [2,3,6] a cui si risponde [1,2,3], che è una posizione perdente del
tipo "caso 8"
C4: [2,2,6] a cui si risponde con [2,2], lasciando l'avversario in
posizione perdente del tipo "caso 5"
C5: [1,2,6] a cui si risponde [1,2,3], che è una posizione perdente del
tipo "caso 8"
C6: [2,6] a cui si risponde con [2,2], lasciando l'avversario in
posizione perdente del tipo "caso 5"
C7: [2,4,5] a cui si risponde con [1,4,5], posizione vincente del tipo
"caso 9"
C8: [2,4,4] a cui si risponde con [4,4], posizione vincente del tipo
"caso 6"
C9: [2,3,4] a cui si risponde [1,2,3], che è una posizione perdente del
tipo "caso 8"
C10: [2,2,4] a cui si risponde con [2,2], lasciando l'avversario in
posizione perdente del tipo "caso 5"
C11: [1,2,4] a cui si risponde [1,2,3], che è una posizione perdente
del tipo "caso 8"
C12: [2,4] a cui si risponde con [2,2], lasciando l'avversario in
posizione perdente del tipo "caso 5"
situazione D:
infine se ci troviamo in [1,5,6], si risponde con [1,4,5], posizione vincente del tipo "caso 9"
quindi, come abbiamo visto, iniziando per primi e muovendo in [3,5,6] si ha la vittoria assicurata.
PS: sicuramente avrò fatto qualche strafalcione nei calcoli, ad ogni modo credo che in linea di principio il ragionamento dovrebbe reggere
allora non essendo specificata la posizione delle fila io l'avrei pensata cosi ( anche se di sicuro sbaglio XD ) che tutte le fila siano messe in sequenza quindi cosi:
111 2222 33333 444444 e quindi iniziando per primi si prende dall'unica fila possibile (che io intendo come linea retta infinita) tutti gli oggetti tranne uno lasciando cosi all'avversario come unica mossa quella di prendere l'ultimo oggetto. questo è il mio primo enigma spero di averla azzeccata XD il mio è un ragionamento semplice rispetto ai vostri XD
Ma che intendi dire lasciare l'avversario con un oggetto? Deve aver preso un solo oggetto oppure avere un solo oggetto da prendere alla fine? Mi sembra un po confuso questo indovinello....
Approccio empirico osservando le sequenze che mi garantivano la vittoria su 2 e 3 righe.
INIZIO IO A GIOCARE.
Cancello la riga da 3. A questo punto mi trovo in una configurazione 345.
Se l'avversario cancella a sua volta una riga applico la strategia "2Righe" altrimenti applico la strategia "3Righe".
Strategia "3Righe".
Ogni volta che si effettua una mossa bisogna fare in modo da creare una configurazione la cui somma sia un multiplo di 3. Si applica questa strategia finchè il numero di righe non si riduce a 2.
Strategia "2Righe"
Bisogna fare in modo da mantenere le due righe sempre con lo stesso numero di oggetti. Quando una delle due righe va a 1 si elimina l'altra riga e si vince, se invece l'avversario elimina una riga si lascia un solo oggetto e si vince.
P.
Scusate, nel precedente post ho detto che cancellando la riga da 3 mi trovavo in una configurazione 345. E' errato. Mi trovo in 456.
P.
l'enigma si risolve in questo modo:
tenere presente i numeri 3 5 7 9 11 14...
In tutto ci sono 18 oggetti messi in 4 file.
Se cominci x primo fai in modo di ottenere subito 3,o 5 o 7 o 9(dipende da quanti oggetti prende il tuo avversario se ne prende tanti vai piano) oggetti in poche mosse senza distruggere tu stesso completamente le file da 4 o 5 o 6.( falli svuotare dal tuo avversario)
Poi devi vedere quanti oggetti prende il tuo avversario.
Devi fare in modo che l'undicesimo e assolutamente il quattordicesimo oggetto sia tuo, e fare in modo che alla fine rimangano almeno 2 file 2+2 e avrai la vittoria assicurata.
Se cominci x secondo, hai bisogno solo di vedere quanti oggetti ha il tuo avversario, e prendere il 14° oggetto lasciando ovviamente 2 file 2+2...
Se qualcuno nn capisce, mi chieda spiegazioni grazie.
Si deve fare in modo che alla fine non rimanga solo una "fila". Ma 2 file almeno.
2 file ognuna con 2 oggetti o
3 file 2 con 1 oggetto e 1 con 2 oggetti..
per primi
parto da una fila qualsiasi e pesco tutto tranne un elemento.
ora sussistono generalmente due situazioni possibili:
_la prima è che l'avversario peschi l'elemento solitario.
_la seconda è che l'avversario peschi un numero qualsiasi di elementi in una qualunque altra fila.
Per risolvere la prima situazione basta procedere come in apertura (ovvero pescare tutti gli elementi tranne uno da un'altra fila)
Per risolvere la seconda situazione è necessario pescare il numero di elementi rimanenti dalla fila presa in considerazione dall'avversario al fine di svuotarla.
Da questa nostra seconda mossa in poi le situazioni che verranno a crearsi saranno identiche a quelle già descritte.
Devo iniziare per primo e rimuovere 4 elementi dalla fila dove ce ne sono 6. Qualsiasi altra mossa darebbe la vittoria all’avversario.
La situazione dopo la mia prima mossa è 2-3-4-5 (l’ordine non conta).
Così partendo, la strategia descritta sotto porterà l'avversario ad una delle 3 configurazioni vincenti cioè, dopo la mia mossa, lui si ritroverà con:
A) 2-2-0-0
B) 1-1-1-0
C) 3-2-1-0 (questa si evolverà poi in A o B)
Chiarito che l'obiettivo è raggiungere una di queste 3 configurazioni, le strade per arrivarci sono:
I) se la mossa dell’avversario pareggia il numero di elementi presenti su due file (per es. porta ad un 2-3-4-2) -> io pareggio il numero degli elementi sulle altre due file, così da avere file pareggiate a due a due (nell’es. rimuovo un elemento dalla fila dei 4). Ad ogni successiva mossa dell’avversario io rispondo riportando la situazione di file pareggiate a due a due, tranne quando con la mia ultima mossa potrò portare ad A o B.
II) se la mossa dell’avversario non pareggia il numero di elementi presenti su due file, allora ho due possibilità:
1 - ha portato ad 1 o a 0 una delle file che avevano 4 o 5 elementi -> porto con la mia mossa a C.
2 - ha portato ad 1 o a 0 una delle file che avevano 2 o 3 elementi ->
porto con la mia mossa alla situazione di 0-1-4-5. La sua prossima mossa mi offrirà la possibilità di portarlo a B, C o II.
Ciao a tutti :-)
Scusate, con l'ultima frase volevo dire "portarlo a B, C o I (intendendo con I la situazione di file pareggiate a due a due.
non potendo conoscere le mosse del mio avversario è impossibile conoscere il vincitore!
Su questo gioco ho scritto tramite storielle romanzate e calcoli seri. Così come proposto, e con la debita premessa che non si possa "passare la mano" ovvero togliere 0 oggetti, il quesito conduce ad un' unica strategia: Chi muove per primo
deve togliere il gruppo di 4 oggetti e, come è evidente (anche verificando per tentativi) chi muove per secondo sarà condannato all' ultima presa.
Il gioco è affascinante con almeno cinque gruppi di oggetti ed ogni gruppo contenente un elevato numero di essi. Ciò per rendere difficili strategie basate sul calcolo binario che permettono sempre e comunque di individuare se una posizione è vincente o se si possa trasformarla in tale. Dòtti articoli e perfino tesi di laurea esistono sull' argomento ma ripeto, togliendo la possibilità di usare carta e penna e aumentando gruppi e numero di oggetti contenuti, magari mettendo un tempo limite di 20 secondi a mossa, la partita diventa diabolicamente difficile, recentemente ho postato una partita con la morte ispirata al "settimo sigillo"
complimenti per il blog
Dante
Ma non possiamo andare avanti con un altro indovinello visto che qst è stato risolto?
basta iniziare per secondi e prendere un numero più piccolo possibile di oggetti in modo tale da lasciare sul tavole sempre un numero dispari di oggetti
vorrei proporre un indovinello, purtroppo non ho trovato come scrivere solo a walter quindi non mi è possibile postare qui la soluzione.
si tratta di indovinare con quali numeri continuare la serie
1
11
21
1211
111221
312211
voglio anche darvi un piccolo aiuto dicendo che la serie può continuare all'infinito.
se walter mi dice come contattarlo gli mando la soluzione
alloraaaaaaaaa
123
1234
12345
lui prende 1
io prendo 2
lui prende 3
io prendo 4
a lui rimane solo una cosa ! ho indovinato?
bisogna iniziare per prmimi;ai primi 3 turni bsogna prendere una fila alla volta ,poi al quarto turno bisogna prendere tutta l intera fila tranne un oggetto che sarà quello che rimarrà al giocatore
(soluzione di un bambino)
Oramai chi prende i punti vince il sito HAHAHAHA
Iniziare x secondo è fondamentale...
ogni presa di oggetti da un fila scelti dal primo io prendo tutti rimanenti in modo che l'altro passi alla fila successiva fino all' ultima quando gli lascerò un solo oggetto.
chissa
Posta un commento