122. Soluzioni del 6 maggio 2024 – Il Gioco del Nim
Nessun commento
Menu
I Giochi del Lunedì di Prisma del 5 giugno 2023 a cura di Fabio Ciuffoli
Oggi presentiamo un gioco sulle strategie di comunicazione. Questo genere di giochi, emersi in ambito informatico, prevede un acceso limitato alle informazioni e di conseguenza un’ottimizzazione dei dati a disposizione. Invitiamo i lettori a inviarci osservazioni e proposte di soluzione utilizzando lo spazio dei comenti. Domani alle ore 17.00 pubblicheremo le nostre proposte di soluzione.
L’esame di Comunicazione
Piero e Aldo, due studenti che devono sostenere l’esame di Comunicazione, vengono condotti, uno dopo l’altro, in una stanza dove ci sono quattro scatole vuote identiche numerate: 1, 2, 3 e 4.
Piero entra nella stanza per primo e qui l’insegnante mette un foglio di carta all’interno di una scatola scelta a caso e la richiude. Piero vede in quale scatola si trova il foglio. A questo punto l’insegnante lancia una moneta e la posiziona sulla scatola 1, lancia una seconda moneta e la posiziona sulla scatola 2 e via di seguito per le scatole 3 e 4, come disegnato in figura. Ogni moneta ha una probabilità del 50% di presentare Testa o Croce. Piero può vedere le facce di tutte le monete.
Ora l’insegnante chiede a Piero di scegliere una moneta e girarla in modo che Testa diventi Croce o viceversa. A questo punto Piero andrà in un’altra stanza isolata.
Infine Aldo viene portato nella stanza con le quattro scatole e vedendo le facce delle monete, dovrà aprire una scatola e se la scatola conterrà il foglio di carta, entrambi gli studenti saranno promossi.
Quale strategia garantisce il superamento dell’esame?
Questo è un enigma fantastico perché sembra impossibile che Piero possa comunicare a Aldo, girando una moneta, quale scatola contenga l’anello, in quanto deve considerare le 4 monete e le 16 possibili combinazioni di Testa e Croce. Come vedremo la soluzione sarà sorprendente!
Un suggerimento. Per facilitare la soluzione del problema, ipotizziamo che ci siano solo due scatole. L’insegnante mette il foglio di carta in una delle due scatole e posiziona una moneta a caso su ciascuna scatola. Piero sa quale scatola contiene il foglio e può vedere entrambe le monete.
Quale moneta girerà Piero per comunicare a Aldo il numero della scatola dove si trova il foglio di carta?
Aggiornamento per la soluzione click qui.
Il gioco di oggi è stato proposto da Pierre Chardaire, insegnante di informatica dell'University of East Anglia a Norwich in Inghilterra, che ringraziamo per il lavoro svolto.
In questa pagina vengono pubblicati giochi matematici, logici e di ragionamento ogni 15 giorni il lunedì in mattinata.
Siamo sempre alla ricerca di nuovi giochi e nuove proposte. Se vuoi suggerirne uno, scrivici un’e-mail a:
blog.giochi@prismamagazine.it
Fabio Ciuffoli è autore di diversi libri sul problem solving e i giochi logici e matematici, il più recente è Giochi matematici e logici.
PRISMA: pubblicazione mensile registrata presso il Tribunale di Milano (N. 235 del 19.09.2018).
Tutti i diritti di proprietà artistica e letteraria sono riservati.
L’editore è a disposizione di eventuali detentori di diritti che non sia stato possibile rintracciare.
Mateinitaly srl – p.iva 09164520968 – Corso Vercelli 27 – 20144 Milano (MI).
24 risposte
Scrivo a seguire la soluzione che ho trovato io.
Associo a “Testa” e “Croce” rispettivamente le cifre “1” (=Testa) e “0” (=Croce) del sistema binario. Per evitare confusioni rinomino le scatole con le lettere dell’alfabeto A, B, C e D (ordinatamente da sinistra a destra). In questo modo, le possibili combinazioni di monete saranno 16 (in binario, da 0000 a 1111, cioè da 0 a 15 in decimale).
Noto che l’operazione reversibile “capovolgimento di una moneta” può far variare una qualsiasi combinazione di partenza verso 4 altre possibili combinazioni, a seconda della moneta coinvolta nel capovolgimento (la 1°, la 2° la 3° o la 4°), per cui si ha la seguente tabella:
♥ 0 (0000) può mutare in 1 (0001), 2 (0010), 4 (0100) oppure 8 (1000);
♥ 1 (0001) può mutare in 0 (0000), 3 (0011), 5 (0101) oppure 9 (1001);
♣ 2 (0010) può mutare in 3 (0011), 0 (0000), 6 (0110) oppure 10 (1010);
♣ 3 (0011) può mutare in 2 (0010), 1 (0001), 7 (0111) oppure 11 (1011);
♦ 4 (0100) può mutare in 5 (0101), 6 (0110), 0 (0000) oppure 12 (1100);
♦ 5 (0101) può mutare in 4 (0100), 7 (0111), 1 (0001) oppure 13 (1101);
♠ 6 (0110) può mutare in 7 (0111), 4 (0100), 2 (0010) oppure 14 (1110);
♠ 7 (0111) può mutare in 6 (0110), 5 (0101), 3 (0011) oppure 15 (1111);
♠ 8 (1000) può mutare in 9 (1001), 10 (1010), 12 (1100) oppure 0 (0000);
♠ 9 (1001) può mutare in 8 (1000), 11 (1011), 13 (1101) oppure 1 (0001);
♦ 10 (1010) può mutare in 11 (1011), 8 (1000), 14 (1110) oppure 2 (0010);
♦ 11 (1011) può mutare in 10 (1010), 9 (1001), 15 (1111) oppure 3 (0011);
♣ 12 (1100) può mutare in 13 (1101), 14 (1110), 8 (1000) oppure 4 (0100);
♣ 13 (1101) può mutare in 12 (1100), 15 (1111), 9 (1001) oppure 5 (0101);
♥ 14 (1110) può mutare in 15 (1111), 12 (1100), 10 (1010) oppure 6 (0110);
♥ 15 (1111) può mutare in 14 (1110), 13 (1101), 11 (1011) oppure 7 (0111).
Poi vado a raggruppare le 16 combinazioni ottenute in 4 gruppi di 4, osservando che:
A) il cluster formato dalle 4 combinazioni (6, 7, 8, 9) [v. le 4 righe contrassegnate col simbolo ♠) può essere raggiunto a partire da una qualsiasi delle 16 posizioni iniziali (da 0000 a 1111) e lo assegno alla scatola A;
B) il cluster formato dalle 4 combinazioni (4, 5, 10, 11) [v. le 4 righe contrassegnate col simbolo ♦) può anch’esso essere raggiunto a partire da una qualsiasi delle 16 posizioni iniziali (da 0000 a 1111) e lo assegno alla scatola B;
C) il cluster formato dalle 4 combinazioni (2, 3, 12, 13) [v. le 4 righe contrassegnate col simbolo ♣) può anch’esso essere raggiunto a partire da una qualsiasi delle 16 posizioni iniziali (da 0000 a 1111) e lo assegno alla scatola C;
D) il cluster formato dalle 4 combinazioni (0, 1, 14, 15) [v. le 4 righe contrassegnate col simbolo ♥) lo assegno alla scatola D.
Basta che i due ragazzi si accordino in questo senso per risolvere l’enigma. Volendo indicare al compagno una delle scatole A, B, C o D non farà altro che osservare la combinazione iniziale di monete generata dal caso e rovesciare una sola moneta per indicare la scatola desiderata.
Ad esempio, partendo da (1001), la cambierà in:
– 1000 [del cluster (6, 7, 8, 9)] per indicare la scatola A;
– 1011 [del cluster (4, 5, 10, 11)] per indicare la scatola B;
– 1101 [del cluster (2, 3, 12, 13)] per indicare la scatola C;
– 0001 [del cluster (0, 1, 14, 15)] per indicare la scatola D.
E così via. Funziona con qualsiasi combinazione iniziale verso una qualsiasi delle 4 scatole.
Io assegnerei a C il valore 1 e a T il valore 2. Inoltre la prima scatola moltiplica per 1, la seconda per 2, la terza per 3 e la quarta per 4. Per trovare la scatola con il foglio si deve calcolare il resto modulo 4 del valore dato dalla combinazione di teste e croci (la scatola 4 corrisponde a resto 0).
Ad esempio supponiamo che il foglio sia nella scatola 2 e che se sulle 4 scatole si abbiano nell’ordine le monete TCCT. Il valore delle monete è 2+2+3+8=15. Per ottenere 2 come resto della divisione per 4 si deve avere ad esempio 14 (o 18). Allora si può girare la prima T e ottenere 14. Nel caso che le monete diano già il valore giusto, si può girare la moneta sulla quarta scatola, che non cambia il valore del resto per 4.
Nel pomeriggio la soluzione.
Stabiliamo che 0 sia testa e 1 sia croce.
Con le prime 2 monete si possono comporre 4 combinazioni: 00, 01, 10, 11.
Ognuna individua una posizione.
A secondo da come trova le prime 2 monete Piero può cambiarne una per indicare la posizione giusta, a meno che parta da 00 o 11 e deve indicare 11 o 00.
In questi casi lascia inalterata la posizione delle prime due monete e agisce sulla quarta che, in questo caso, diventa la moneta del vero o falso: 0 significa vero e 1 significa falso. Quindi, ad esempio, se vuole indicare la prima posizione e le prime due monete hanno 00, allora la quarta sarà 0; viceversa se le prime due monete sono 11 allora anche la quarta deve essere portata a 1.
Resta solo il caso in cui tutte le monete sono già nella posizione che vuole Piero: in questo caso Piero agirà sulla terza moneta che è assolutamente priva di significato per Aldo.
Io farei così,
La prima moneta non la considererei,
Ne rimangono tre, che in codice binario fa 2alla3 combinazioni, cioè 8
Mi metterei d’accordo con questa tabella
000 1
001 2
010 3
011 4
100 4
101 3
110 2
111 1
In tal modo girando una moneta sarà sempre possibile ottenere il numero binari associati ad una determinata scatola
Io ho trovato questa soluzione che mi sembra la più semplice.
Considero la posizione delle prime due monete, che può essere CC, TT, CT o TC.
La terza moneta mi comunica il valore che si vuole passare rapportandola alla prima:
se le prime due monete sono sullo stesso lato (CC o TT) e la terza coincide con la prima passa il valore 1
se le prime due monete sono sullo stesso lato (CC o TT) e la terza NON coincide con la prima passa il valore 2
se le prime due monete NON sono sullo stesso lato (CT o TC) e la terza coincide con la prima passa il valore 3
se le prime due monete NON sono sullo stesso lato (CT o TC) e la terza NON coincide con la prima passa il valore 4
La quarta moneta serve solo come “specchietto per le allodole”
In questo modo qualunque sia la posizione delle prime 3 monete, posso sempre ottenere la combinazione utile girando una sola moneta: una delle 3 se la combinazione è divera, la quarta se la combinazione è già corretta:
CC + C
Per ottenere 1: giro la 4
Per ottenere 2: giro la 3
Per ottenere 3: giro la 2
Per ottenere 4: giro la 1
CC + T
Per ottenere 1: giro la 3
Per ottenere 2: giro la 4
Per ottenere 3: giro la 1
Per ottenere 4: giro la 2
TT + C
Per ottenere 1: giro la 3
Per ottenere 2: giro la 4
Per ottenere 3: giro la 1
Per ottenere 4: giro la 2
TT + T
Per ottenere 1: giro la 4
Per ottenere 2: giro la 3
Per ottenere 3: giro la 2
Per ottenere 4: giro la 1
CT + C
Per ottenere 1: giro la 2
Per ottenere 2: giro la 1
Per ottenere 3: giro la 4
Per ottenere 4: giro la 3
CT + T
Per ottenere 1: giro la 1
Per ottenere 2: giro la 2
Per ottenere 3: giro la 3
Per ottenere 4: giro la 4
TC + C
Per ottenere 1: giro la 1
Per ottenere 2: giro la 2
Per ottenere 3: giro la 3
Per ottenere 4: giro la 4
TC + T
Per ottenere 1: giro la 2
Per ottenere 2: giro la 1
Per ottenere 3: giro la 4
Per ottenere 4: giro la 3
A domani per la soluzione.
E’ un quesito matematico sofisticato, quindi lasciamo da parte trucchetti come posizionare la moneta più spostata delle altre ecc. Si basa sulla somma binaria NIM, cioè senza riporto. I due sono d’accordo nell’osservare, diciamo, le croci. (x=croce O=testa) e numerano le scatole 1,2,3,4 da sinistra a destra.
Supponiamo che Piero veda XOXO e che la scatola da indovinare sia la 1. Fa la somma 1+3 (posizione delle , croci) a cui aggiunge 1,(scatola da indovinare). La somma in binario diventa: 1+(1+2)+1 dato che la somma è senza riporto si possono cancellare coppie di segni uguali quindi resta 2+1=3 e gira la terza moneta lasciando XOOO. Aldo entra e fa a sua volta la somma NIM delle croci che vede. In questo caso è 1 e indovina.
Altro esempio XXOO scatola da indovinare la 3. Somma NIM= 1+2+(1+2)=0 Piero può non girare alcuna moneta oppure la num 4 è la stessa cosa perché stiamo contando modulo 4. Supponiamo che giri la 4, lasciando questa disposizione : XXOX. Aldo entra e fa la somma NIM 1+2+4 = 1+2+2+2 ignora la coppia di 2 e indovina la terza scatola.
Ultimo esempio Piero trova XXXO e la scatola da indovinare è la 3. Somma 1+2+3+3 che in binario si traduce 1+2+(1+2)+(1+2) ignora le due coppie (1,1) e (2,2) resta 1+2=3 quindi gira la terza moneta lasciando XXOO.
Aldo entra vede 1+2=3 e indovina. Chiaramente si può applicare lo stesso principio anche a 8 scatole.
Un metodo semplice che mi viene in mente è il seguente:
Ci si accorda che valgono le indicazioni fornite dalle monete poste sulle scatole da 2 a 4 (3 monete) dove la moneta sulla scatola 2 (di seguito moneta 2) fa da negazione del codice espresso dalle monete sulle scatole 3 e 4.
Si concordano i seguenti codici di identificazione della scatola indicati dalle monete poste sulle scatole 3 e 4:
Se la moneta 2 è C:
C C = scatola 1
C T = scatola 2
T C = scatola 3
T T = scatola 4
Se la moneta 2 è T si deve negare il codice dato dalle monete 3 e 4:
T T = scatola 1
T C = scatola 2
C T = scatola 3
C C = scatola 4
In questo modo sarà sempre possibile indicare la scatola in cui è presente il foglio girando una sola moneta e nel caso le monete dalla 2 alla 4 fossero già nella configurazione corretta Piero girerà la moneta sulla scatola 1.
Questa di Carlo mi sembra la soluzione migliore, che supera anche l’incompletezza della soluzione di Sandro qui sotto.
Quindi: prime 2 monete per indicare una delle 4 scatole; terza moneta per invertire (mentalmente) entrambe le prime due nel caso siano opposte alla soluzione; quarta moneta “inutile”, da girare se le altre tre danno già il risultato voluto.
A domani per la soluzione.
La soluzione di Sandro, cui hai risposto “ottimo”, non è corretta.
Supponiamo che la disposizione delle monete sia C C T T e che la scatola da indovinare sia la terza. Cambiando solo una moneta non si può riprodurre T T per le prime due monete (che secondo la strategia indicata significano 3)
Per evitare simbolismi e rendere la cosa più semplice si può ragionare in binario ed adottare qualche regola, ad esempio:
– le prime 2 monete da destra (scatola 3 e 4) formeranno il numero binario a 2 bit (00, 01, 10, 11) che ci indicherà la scatola in cui si trova la moneta;
-alla scatola più a dx assegnamo il nr. 0 (00) mentre a quella più a sx assegnamo il numero 3 (11), le 2 in mezzo si evincono.
Stabilito ciò, potendo girare una sola moneta, bisogna stabilire con quale criterio assegnare il nr. 1 ed il nr 0, quindi decideremo che la scatola nr. 2 sarà quella la cui moneta soprastante ci indicherà il valore 1 (la moneta sulla scatola 1 non ci interesserà).
Senza stare ad indicare tutte le casistiche, agendo su una sola moneta delle 3 scatole a dx, possiamo determinare 4 valori (da 00 a 11) a cui precedentemente abbiamo assegnato le scatole.
ps grazie per averlo condiviso…
Si potrebbe fare un controllo di parità.
Casi possibili di disposizione delle monete da C C C C a T T T T: assegniamo il valore 0 se la moneta è su croce C e il valore 1 se è su testa T.
Piero vede ad esempio T C C C e fa mentalmente questi controlli (due monete per volta):
monete 1 e 2 ——> 1
monete 1 e 3 ——> 1
monete 1 e 4 ——> 1
Numero binario 1 1 1
Deve far indovinare a Aldo il numero (da 1 a 4) della scatola che contiene il foglio, che può essere:
1 —–> deve trasmettere 0 0 1 oppure 1 0 1 : gira la moneta della terza scatola da C a T : Aldo vede T C T C e calcola (con la stessa strategia di Piero, due monete per volta) 1 0 1 cui corrisponde 5 cioè la prima scatola.
2 —–> deve trasmettere 0 1 0 oppure 1 1 0 : gira la moneta della quarta scatola da C a T : Aldo vede T C C T e calcola (con la stessa strategia di Piero, due monete per volta) 1 1 0 cui corrisponde 6 cioè la seconda scatola.
3 —–> deve trasmettere 0 1 1 oppure 1 1 1 : gira la moneta della seconda scatola da C a T : Aldo vede T T C C e calcola (con la stessa strategia di Piero, due monete per volta) 0 1 1 cui corrisponde 3 cioè la terza scatola.
4 —–> deve trasmettere 1 0 0 oppure 0 0 0 : gira la moneta della prima scatola da T a C : Aldo vede C C C C e calcola (con la stessa strategia di Piero, due monete per volta) 0 0 0 cui corrisponde 4 cioè la terza scatola.
Analogamente per qualsiasi altra disposizione iniziale delle monete sulle quattro scatole.
Nel disegno c’è già la soluzione al quesito, si vede chiaramente che tre scatole hanno la moneta posizionata lateralmente e solo una al centro. Quindi non è importante che la moneta sia con la testa o con croce rivolta verso l’alto, ma che abbia la moneta posizionata al centro della scatola.
Non è questa la via per la soluzione.
Si dà per scontato che la posizione della moneta (centro e lati) non conti giusto? Nella 4 scatola dell’illustrazione la moneta ha una posizione diversa dalle altre. Se non conta la posizione si può utilizzare il sistema binario o Turing: possiamo fissare che 4 sequenze diano la posizione 1, altre 4 la due, etc girando una volta una moneta delle 4 si può rientrare in una delle sequenza stabilite.
Il problema è trovare i 4 gruppi in modo che si possa fare quel che hai scritto: bisogna assegnare ad ogni scatola 4 sequenze in modo che, qualsiasi sia la sequenza di partenza, con un solo ribaltamento (o con nessun ribaltamento) ottieni una delle 4 sequenze assegnate alla scarola giusta
Pietro girerà una delle prime tre monete in modo che la moneta con la faccia diversa dalle altre due sia sopra la scatola col premio, se le tre monete presentano la stessa faccia il premio è nella 4.
Dimostrazione.
Le monete sulle prime tre scatole possono presentarsi a Pietro solo in due modi: due monete uguali e una diversa oppure tre monete uguali.
Va da sé che se le tre monete sono uguali e il premio è nella 4, quindi Pietro modifica la moneta sulla 4.
Se le tre monete sono uguali e il premio è in una delle prime tre scatole, Pietro gira la moneta sopra la scatola col premio.
Se le monete sono due uguali e una diversa, e il premio è nella 4, Pietro gira la moneta diversa in modo che siano tutte uguali.
Se le monete sono due uguali e una diversa, e il premio è nella scatola con la moneta diversa, Pietro non modifica nulla e gira la 4.
Se le monete sono due uguali e una diversa, e il premio è in una delle prime tre scatole ma non quella coincidente con la moneta diversa, allora significa che una delle due monete uguali si trova sulla scatola del premio. Allora Pietro gira la moneta uguale alla scatola del premio che non si trova sulla scatola del premio. Infine Aldo deve scegliere, tra le prima tre, quella scatola con la moneta diversa dalle altre due, mentre se le monete delle prime tre scatole fossero tutte uguali, Aldo dovrà scegliere la 4.
(Adattato da un post di Nicola Fisco)
Tiene conto solo delle monete sulle prime due scatole e usa il codice binario. C zero e T uno. A 00 (cc) fanno corrispondere la 4, a 01 (ct) la 1, tc la due, tt la 3.se la combinazione è già presente cambia una delle altre superflue.
Ottimo a domani per la soluzione commentata.
Io l’ho pensata così. Ci sono 16 combinazioni possibili. Per ogni scatola valgono 4 combinazioni. Girando una moneta dovrebbe essere sempre possibile rientrare in una combinazione che indichi una delle 4 scatole.
Se i due conoscono il codice binario il tutto diventa molto semplice.
Girando la moneta la sposta in zona leggermente + decentrata. È questo il segno di riconoscimento
Interessante, ma troppo incerto e non rientra nelle possibili soluzioni “matematiche” del problema. A domani per la soluzione.