Categoria: Giochi matematici

  • I soldati di Conway

    I soldati di Conway

    Un esercito di pedine occupa una parte della scacchiera. Davanti ha uno spazio vuoto, e una sola possibilità per avanzare: saltare un compagno, che viene tolto dal gioco. Ogni progresso costa un soldato.

    Puoi scegliere quanti pezzi usare e come disporli dietro la linea di partenza. Non c’è un avversario, non c’è un tempo limite e la scacchiera non ha bordi. Sembra che basti preparare un esercito abbastanza grande per arrivare ovunque.

    Il rompicapo di John Conway mette alla prova proprio questa intuizione. La domanda non è soltanto quale mossa fare: è capire se un obiettivo apparentemente vicino possa davvero essere raggiunto.

    PROBLEMA 1729 #027

    Tempo: 20–30 minuti

    Difficoltà:

    Classificazione: 4 su 5.

    Categoria: Invarianti e impossibilità

    Il problema

    Immagina una griglia quadrata infinita. Numera le righe con gli interi: la riga 0 è l’ultima riga di partenza; sopra ci sono le righe 1, 2, 3, 4, 5 e così via. All’inizio puoi collocare un numero finito, grande quanto vuoi, di pedine nelle righe 0, −1, −2… Al massimo una pedina per casella; tutte le righe positive sono vuote.

    Una mossa consiste nel saltare con una pedina sopra una pedina immediatamente adiacente, atterrando nella casella subito successiva, che deve essere vuota. La pedina saltata viene rimossa. Sono ammessi salti orizzontali e verticali in entrambi i versi, mai diagonali. Non si aggiungono nuovi pezzi durante il gioco.

    Puoi portare una pedina nella quinta riga sopra la linea di partenza, cioè nella riga 5? Puoi scegliere liberamente la disposizione iniziale. Trova una strategia oppure dimostra perché nessuna strategia può funzionare.

    Prima di proseguire, fermati: prova con monete o bottoni su carta quadrettata. Raggiungi le prime righe e osserva quanti pezzi devi consumare per continuare.

    💡 Mostra un indizio

    Contare soltanto le pedine non basta: una pedina vicina all’obiettivo può essere più utile di molte pedine lontane.

    Prova ad assegnare un valore a ogni casella. Cerca un punteggio complessivo che nessuna mossa possa aumentare. Se l’obiettivo richiedesse più punti di quelli disponibili all’inizio, avresti una dimostrazione.

    💡 Mostra un altro indizio

    Cerca un numero q compreso fra 0 e 1 che soddisfi q + q² = 1.

    Fissa una casella della riga 5 come bersaglio. Assegna valore 1 al bersaglio, q alle caselle a distanza 1, q² a quelle a distanza 2 e così via. Misura la distanza contando passi orizzontali e verticali, senza diagonali. Che cosa succede al totale quando due pedine diventano una?

    ✅ Mostra la soluzione

    No: la quinta riga è irraggiungibile. Non è una questione di pazienza o di numero di tentativi. La dimostrazione usa un “bilancio” che nessuna mossa può migliorare.

    1. Scegliamo il bersaglio. Possiamo chiamarlo (0,5), spostando l’origine orizzontale se necessario. Poniamo q = (√5−1)/2, circa 0,618. Vale q + q² = 1.
    2. Attribuiamo i pesi. Alla casella (x,y) assegniamo q|x|+|y−5|. Il bersaglio pesa 1. Il punteggio di una posizione è la somma dei pesi delle caselle occupate.
    3. Controlliamo i salti. Quando un salto avvicina di due passi al bersaglio, i due pesi consumati sono qd+2 e qd+1, mentre quello ottenuto è qd: sono uguali perché q² + q = 1. Un salto nella direzione opposta diminuisce il punteggio. Se il salto attraversa una riga o colonna del bersaglio, partenza e arrivo hanno lo stesso peso e si perde il peso della pedina centrale. Questi casi coprono tutti i salti ammessi.
    4. Sovrastimiamo l’esercito iniziale. Immaginiamo, soltanto per fare il conto, di occupare tutte le caselle con y ≤ 0. La somma dei pesi è il prodotto di due serie geometriche: [q5/(1−q)] × [(1+q)/(1−q)] = 1. Il primo fattore somma le distanze verticali; il secondo le colonne a destra e sinistra, compresa quella centrale.
    5. Torniamo a un esercito finito. Ogni disposizione iniziale consentita occupa solo un numero finito di caselle, tutte con peso positivo. Il suo punteggio è quindi strettamente minore di 1. Una pedina sul bersaglio varrebbe già 1 da sola. Poiché il totale non può crescere, non possiamo arrivarci.

    Il passaggio decisivo è quello fra il semipiano infinito usato per stimare la somma e l’esercito finito con cui giochiamo. Anche aggiungendo milioni di pedine, il punteggio può avvicinarsi a 1, ma resta inferiore. La stessa dimostrazione vale per qualsiasi casella della quinta riga.

    Nessun esercito finito può raggiungere la riga 5.

    La matematica dentro al gioco

    Lo strumento è una funzione potenziale, detta in questo contesto anche funzione pagoda. Non è un invariante in senso stretto, perché può diminuire: è una quantità monotona. Questa distinzione aiuta a capire perché non occorre analizzare ogni possibile partita.

    La sezione aurea non compare come decorazione. Il suo reciproco q è esattamente il numero che rende compatibili i pesi di due pedine con quello della pedina risultante: qd+1 + qd+2 = qd. La regola locale del salto suggerisce l’equazione.

    Per verificare il conto delle serie, usa 1−q = q² e 1+q = 1/q: q5(1+q)/(1−q)² diventa q4/q4 = 1. Dimostrare che il bersaglio costa troppo è molto più efficace che cercare di esaurire una quantità enorme di tentativi.

    Una variante per te

    Un obiettivo più vicino: disponi soltanto quattro pedine nelle righe non positive e prova a raggiungere la riga 2. Puoi farcela in tre salti?

    Una disposizione che funziona occupa le caselle (0,−1), (0,0), (−2,0) e (−1,0). Esegui: (0,−1) → (0,1), saltando (0,0); poi (−2,0) → (0,0), saltando (−1,0); infine (0,0) → (0,2), saltando (0,1). Verifica a ogni passaggio che l’arrivo sia vuoto e togli la pedina saltata.

    Lo sapevi?

    La quarta riga, invece, è raggiungibile: nell’esercito classico il numero minimo di pedine necessario è venti. La crescita dei minimi è sorprendente: due, quattro, otto e poi venti per raggiungere rispettivamente le prime quattro righe.

    Il problema nasce dal lavoro di John Conway sui giochi matematici. Regole diverse, per esempio l’aggiunta di salti diagonali, richiedono nuovi ragionamenti: la dimostrazione appena vista dipende dalle mosse ammesse.

    Per approfondire: George I. Bell, Daniel S. Hirschberg e Pablo Guerrero-García, The minimum size required of a solitaire army, Integers, 2007. Un’esposizione del metodo dei pesi si trova anche nel capitolo dedicato all’esercito di Conway ospitato dall’Università dell’Illinois a Chicago.

    Problema 1729

    #027 — I soldati di Conway

    Giochi, enigmi e idee matematiche per menti curiose.

  • Una moneta

    Una moneta

    Lasciatemi cambiare un po’ le modalità di questa serie di articoli. Modalità fast. Nessun indizio, nessuna soluzione, andiamo in scena.

    Lanciamo una moneta (onesta) più volte: se compare per prima la sequenza Croce-Croce-Testa vincete 16 euro, se compare prima la sequenza Testa-Croce-Croce perdete 8 euro. Accettate?

  • Le dodici monete e le tre pesate

    Le dodici monete e le tre pesate

    Dodici monete sembrano identiche, ma una ha un peso diverso. Potrebbe essere più pesante oppure più leggera, e non disponi di una moneta certamente autentica con cui confrontarla.

    Una bilancia a due piatti offre soltanto tre risultati: sinistra più pesante, equilibrio, destra più pesante. In tre pesate bisogna quindi trasformare ogni possibile esito in informazione e non sprecare nessun ramo della ricerca.

    Il rompicapo non richiede fortuna. Una strategia adattiva, nella quale la pesata successiva dipende dal risultato precedente, permette di individuare sempre la moneta falsa e stabilire se pesa di più o di meno.

    PROBLEMA 1729 #026

    Tempo: 10–15 minuti

    Difficoltà:

    Classificazione: 3 su 5.

    Categoria: Informazione e alberi decisionali

    Il problema

    Hai dodici monete apparentemente identiche, numerate da 1 a 12. Undici hanno lo stesso peso; una è falsa e pesa diversamente.

    Non sai se la moneta falsa sia più pesante o più leggera. Hai a disposizione una bilancia a due piatti, senza pesi campione, e puoi effettuare al massimo tre pesate.

    Come puoi identificare con certezza la moneta falsa e stabilire se è più pesante o più leggera?

    Prima di proseguire, fermati: inizia dividendo le monete in tre gruppi da quattro e prova a costruire un albero in cui ogni pesata abbia tre possibili esiti.

    💡 Mostra un indizio

    Prima pesata: confronta 1, 2, 3, 4 con 5, 6, 7, 8.

    Se i piatti si equilibrano, la falsa è tra 9, 10, 11 e 12 e le prime otto sono autentiche. Se non si equilibrano, sai già quali quattro potrebbero essere pesanti e quali quattro potrebbero essere leggere.

    💡 Mostra un altro indizio

    Se nella prima pesata il lato 1–4 è più pesante, pesa 1, 2, 5 contro 3, 6 e una moneta certamente autentica, per esempio la 9.

    Questa scelta divide gli otto sospetti in gruppi di tre, tre e due. Nel caso opposto usa lo stesso schema scambiando “pesante” e “leggera”.

    ✅ Mostra la soluzione

    Prima pesata: 1, 2, 3, 4 contro 5, 6, 7, 8. Segui il ramo corrispondente al risultato.

    A. La prima pesata è in equilibrio

    1. Pesa 9, 10, 11 contro tre monete autentiche, per esempio 1, 2, 3.
    2. Se c’è equilibrio, la 12 è falsa: confrontala con la 1 per sapere se è pesante o leggera.
    3. Se 9–11 sono più pesanti, una di esse è pesante; confronta 9 con 10. La più pesante è falsa, oppure è la 11 se c’è equilibrio.
    4. Se 9–11 sono più leggere, confronta 9 con 10. La più leggera è falsa, oppure è la 11 se c’è equilibrio.

    B. Nella prima pesata 1–4 sono più pesanti

    I sospetti sono 1, 2, 3, 4 come possibili monete pesanti e 5, 6, 7, 8 come possibili monete leggere. Pesa 1, 2, 5 contro 3, 6, 9.

    1. Se il lato 1, 2, 5 è più pesante, i casi sono 1 pesante, 2 pesante o 6 leggera. Confronta 1 con 2: la più pesante è falsa; se sono uguali, è la 6 leggera.
    2. Se c’è equilibrio, i casi sono 4 pesante, 7 leggera o 8 leggera. Confronta 7 con 8: la più leggera è falsa; se sono uguali, è la 4 pesante.
    3. Se il lato 3, 6, 9 è più pesante, i casi sono 3 pesante o 5 leggera. Confronta 3 con la 9: se 3 pesa di più è falsa; altrimenti è la 5 leggera.

    C. Nella prima pesata 1–4 sono più leggere

    La strategia è simmetrica. Pesa ancora 1, 2, 5 contro 3, 6, 9.

    1. Se 1, 2, 5 sono più leggeri, confronta 1 con 2: la più leggera è falsa; se sono uguali, è la 6 pesante.
    2. Se c’è equilibrio, confronta 7 con 8: la più pesante è falsa; se sono uguali, è la 4 leggera.
    3. Se 3, 6, 9 sono più leggeri, confronta 3 con la 9: se 3 pesa meno è falsa; altrimenti è la 5 pesante.

    In ogni ramo la terza pesata distingue tutti i casi rimasti e determina anche se la moneta falsa è pesante o leggera.

    La matematica dentro al gioco

    Ogni moneta genera due stati possibili: falsa pesante oppure falsa leggera. Con dodici monete ci sono quindi 24 casi da distinguere.

    Una pesata ha tre esiti, perciò tre pesate possono generare al massimo 3³ = 27 sequenze di risultati. Il margine rispetto ai 24 casi è minimo: non basta dividere casualmente, bisogna costruire un albero decisionale quasi perfettamente bilanciato.

    La strategia è adattiva: il secondo confronto dipende dal primo esito e il terzo dal secondo. È lo stesso principio con cui un test diagnostico o un algoritmo di ricerca sceglie la domanda successiva per massimizzare l’informazione utile.

    Una variante per te

    Hai nove monete e sai già che una sola è più pesante delle altre. Riesci a trovarla con due pesate?

    Dividile in tre gruppi da tre e pesa due gruppi. Se si equilibrano, la falsa è nel terzo; altrimenti è nel gruppo più pesante. Confronta poi due monete del gruppo sospetto: la più pesante è falsa, oppure lo è la terza se c’è equilibrio.

    Lo sapevi?

    Il numero 12 non è casuale. Tre pesate offrono 27 esiti teorici e i casi da distinguere sono 24. Con tredici monete diventerebbero 26, ma senza una moneta autentica di riferimento i vincoli fisici della prima pesata impediscono di distribuire correttamente tutti i casi nei tre rami.

    Il rompicapo mostra la differenza tra contare gli esiti disponibili e costruire davvero un esperimento che li realizzi. Il limite informativo è necessario, ma non sempre sufficiente.

    Problema 1729

    #026 — Le dodici monete e le tre pesate

    Giochi, enigmi e idee matematiche per menti curiose.

  • Il gioco del Nim

    Il gioco del Nim

    Tre mucchietti di pietre e una regola semplicissima: a turno si possono togliere quante pietre si desidera, ma da un solo mucchietto. Chi prende l’ultima vince. Il gioco del Nim sembra lasciare spazio soltanto all’intuito.

    In realtà ogni posizione contiene un’informazione nascosta. Non dipende dal numero totale di pietre né dal mucchietto più grande: emerge quando le quantità vengono scritte in base due e confrontate colonna per colonna.

    Scoprire quella regolarità permette di distinguere le posizioni vincenti da quelle perdenti e di scegliere una mossa che obbliga l’avversario a restituire il vantaggio.

    PROBLEMA 1729 #024

    Tempo: 10–15 minuti

    Difficoltà:

    Classificazione: 3 su 5.

    Categoria: Strategia e numerazione binaria

    Il problema

    Sul tavolo ci sono tre mucchietti contenenti rispettivamente 3, 4 e 5 pietre. Due giocatori si alternano.

    A ogni turno un giocatore deve togliere almeno una pietra e può prenderne quante vuole, purché tutte dallo stesso mucchietto. Chi prende l’ultima pietra vince.

    Se giochi per primo, puoi assicurarti la vittoria? Qual è la prima mossa corretta e quale strategia devi seguire dopo?

    Prima di proseguire, fermati: prova alcune partite e annota le posizioni in cui, qualunque mossa tu faccia, l’avversario sembra poter riprendere il controllo.

    💡 Mostra un indizio

    Il numero totale delle pietre non basta. Scrivi 3, 4 e 5 in base due usando tre cifre.

    Ottieni 011, 100 e 101. Osserva in ciascuna colonna quante cifre 1 compaiono.

    💡 Mostra un altro indizio

    Le posizioni speciali sono quelle in cui ogni colonna binaria contiene un numero pari di 1.

    Cerca una mossa che trasformi 3, 4, 5 in una terna con questa proprietà. Puoi cambiare una sola quantità e soltanto diminuendola.

    ✅ Mostra la soluzione

    Calcoliamo la somma Nim, cioè lo XOR bit a bit delle dimensioni dei mucchietti:

    3 ⊕ 4 ⊕ 5 = 011 ⊕ 100 ⊕ 101 = 010 = 2

    Poiché il risultato non è zero, la posizione iniziale è vincente per chi comincia. Bisogna lasciare all’avversario una posizione con somma Nim uguale a zero.

    1. Considera il mucchietto da 3: 3 ⊕ 2 = 1, e 1 è minore di 3.
    2. Riduci quindi quel mucchietto da 3 a 1, togliendo 2 pietre.
    3. La nuova posizione è 1, 4, 5 e infatti 1 ⊕ 4 ⊕ 5 = 0.
    4. Dopo ogni mossa dell’avversario, la somma Nim diventa diversa da zero. Esiste allora una mossa che la riporta a zero.

    Ripetendo questa risposta, prima o poi sarai tu a prendere l’ultima pietra. La strategia non consiste nel copiare la quantità rimossa dall’avversario: consiste nel ripristinare ogni volta lo XOR nullo.

    Prima mossa vincente: togli 2 pietre dal mucchietto da 3 e lascia 1, 4, 5.

    La matematica dentro al gioco

    Lo XOR confronta le cifre binarie e scrive 1 quando in una colonna compare un numero dispari di 1. Per più mucchietti, la somma Nim è zero esattamente quando ogni colonna ha parità pari.

    Una posizione con somma Nim zero è perdente se l’avversario gioca perfettamente: qualunque mossa altera una sola dimensione e rende lo XOR non nullo. Da una posizione con XOR non nullo, invece, si può sempre ridurre un mucchietto in modo da ottenere zero.

    Il Nim è il modello fondamentale dei giochi imparziali, nei quali le mosse disponibili non dipendono dal giocatore. Il teorema di Sprague–Grundy associa a molte posizioni di gioco un numero e permette di combinarle come se fossero mucchietti di Nim.

    Una variante per te

    Prova la versione misère: le mosse restano identiche, ma chi prende l’ultima pietra perde.

    Finché almeno due mucchietti contengono più di una pietra, usa la normale strategia della somma Nim. Quando ne resta uno solo più grande di 1, riducilo a 0 oppure a 1 in modo da lasciare all’avversario un numero dispari di mucchietti da una pietra. Se tutti i mucchietti valgono già 1, togline uno e consegna all’avversario una quantità dispari. Verifica la strategia partendo da 1, 1, 1 e poi da 1, 1, 1, 1.

    Lo sapevi?

    La strategia completa del Nim fu pubblicata nel 1901 dal matematico di Harvard Charles L. Bouton. Il suo risultato è uno dei primi esempi moderni di analisi matematica rigorosa di un gioco.

    La forza del metodo sta nel cambio di rappresentazione: in base dieci le quantità sembrano indipendenti; in base due rivelano una condizione di parità che può essere mantenuta dopo ogni risposta.

    Problema 1729

    #024 — Il gioco del Nim

    Giochi, enigmi e idee matematiche per menti curiose.

  • Somma e prodotto

    Somma e prodotto

    Due numeri interi sono scelti in segreto. Una persona conosce soltanto la loro somma, un’altra soltanto il prodotto. Nessuna delle due vede i numeri, eppure dopo quattro brevi frasi entrambe riescono a determinarli.

    Il rompicapo sembra impossibile perché somma e prodotto ammettono molte scomposizioni. Ma ogni dichiarazione elimina non una coppia, bensì tutte le coppie incompatibili con ciò che un interlocutore può sapere dell’altro.

    Per risolverlo bisogna ragionare su più livelli: che cosa sa Prodotto, che cosa Somma sa che Prodotto non sa, e che cosa cambia quando questa informazione diventa pubblica.

    PROBLEMA 1729 #023

    Tempo: 15–20 minuti

    Difficoltà:

    Classificazione: 4 su 5.

    Categoria: Deduzione e teoria dei numeri

    Il problema

    Sono scelti due interi x e y tali che 1 < x < y e x + y ≤ 100.

    A Somma viene comunicato soltanto il valore x + y. A Prodotto viene comunicato soltanto il valore x·y. Entrambi conoscono le regole e sanno che l’altro ragiona perfettamente.

    Prodotto: «Non conosco i due numeri.»
    Somma: «Sapevo che non li conoscevi.»
    Prodotto: «Adesso li conosco.»
    Somma: «Adesso li conosco anch’io.»

    Quali sono i due numeri?

    Prima di proseguire, fermati: prova a leggere ogni frase come un filtro applicato all’insieme di tutte le coppie possibili.

    💡 Mostra un indizio

    Prodotto non sa: il numero che ha ricevuto deve possedere almeno due fattorizzazioni compatibili con le regole.

    Somma dice che lo sapeva già. Quindi, per ogni scomposizione possibile della sua somma, il relativo prodotto deve essere ambiguo.

    💡 Mostra un altro indizio

    Dopo la frase di Somma, i soli valori possibili della somma sono 11, 17, 23, 27, 29, 35, 37, 41, 47 e 53.

    Ora considera il prodotto 52: può essere 2·26 oppure 4·13. Le somme sono 28 e 17, ma soltanto 17 è rimasta nell’elenco.

    ✅ Mostra la soluzione

    I due numeri sono 4 e 13. Il loro prodotto è 52 e la loro somma è 17. La certezza emerge attraverso eliminazioni successive.

    1. Prodotto non conosce i numeri. Il suo valore non ha una fattorizzazione unica tra le coppie ammesse. Per esempio 52 può essere 2·26 oppure 4·13.
    2. Somma sapeva che Prodotto non poteva sapere. Qualunque coppia compatibile con la somma ricevuta deve avere un prodotto ambiguo. Applicando questo controllo a tutte le somme fino a 100 restano soltanto 11, 17, 23, 27, 29, 35, 37, 41, 47 e 53.
    3. Prodotto ora conosce i numeri. Tra le fattorizzazioni del suo prodotto, esattamente una ha una somma sopravvissuta. Se il prodotto è 52, 2+26=28 è stato escluso, mentre 4+13=17 è ancora possibile: Prodotto deduce 4 e 13.
    4. Somma ora conosce i numeri. Per la somma 17 esistono sette coppie: 2+15, 3+14, 4+13, 5+12, 6+11, 7+10 e 8+9. Soltanto il prodotto della coppia 4+13 avrebbe permesso a Prodotto di dichiarare la propria certezza. Somma deduce quindi la stessa coppia.

    Un controllo completo parte da 2.352 coppie, ne conserva 1.747 dopo la prima frase, 145 dopo la seconda e 86 dopo la terza. La quarta frase lascia una sola coppia.

    Risultato: x = 4 e y = 13.

    La matematica dentro al gioco

    Il gioco combina fattorizzazione ed epistemologia. Ogni giocatore vede una partizione diversa dello stesso insieme di possibilità: Somma raggruppa le coppie con uguale somma; Prodotto quelle con uguale prodotto. “Sapere” significa che nel proprio gruppo resta una sola coppia.

    Ogni dichiarazione pubblica modifica l’insieme comune delle possibilità. Dopo l’annuncio, i gruppi vengono ricalcolati e un’informazione prima insufficiente può diventare decisiva. È lo stesso principio degli algoritmi di eliminazione e dei modelli di conoscenza usati in logica epistemica e informatica teorica.

    Una variante per te

    Sostituisci il limite x + y ≤ 100 con x + y ≤ 60 e mantieni identico il dialogo. Esiste ancora una coppia?

    No. Ripetendo le stesse eliminazioni non resta alcuna coppia compatibile con tutte e quattro le frasi. Il limite superiore non è un dettaglio decorativo: determina quali fattorizzazioni e quali somme sono considerate possibili, quindi cambia ciò che i due interlocutori possono dedurre.

    Lo sapevi?

    Il rompicapo fu pubblicato nel 1969 dal matematico olandese Hans Freudenthal. Martin Gardner lo rese celebre con il nome di “problema impossibile”, perché all’inizio sembra mancare l’informazione necessaria. In realtà l’informazione decisiva non è contenuta nei numeri comunicati, ma nelle dichiarazioni dei due interlocutori e nel fatto che ciascuno sa come ragiona l’altro.

    Problema 1729

    #023 — Somma e prodotto

    Giochi, enigmi e idee matematiche per menti curiose.

  • Il compleanno di Cheryl

    Il compleanno di Cheryl

    Cheryl propone ad Albert e Bernard dieci possibili date per il suo compleanno. Poi comunica il mese soltanto ad Albert e il giorno soltanto a Bernard. Nessuno dei due possiede la risposta completa, ma entrambi sanno come ragiona l’altro.

    Seguono appena tre frasi. Ogni frase elimina interi gruppi di possibilità, non per ciò che rivela direttamente, ma per ciò che dimostra sulla conoscenza degli interlocutori.

    È un piccolo capolavoro di logica epistemica: per risolverlo non basta chiedersi “che cosa so?”, bisogna chiedersi “che cosa so che l’altro non può sapere?”.

    PROBLEMA 1729 #022

    Tempo: 10–15 minuti

    Difficoltà:

    Classificazione: 4 su 5.

    Categoria: Logica della conoscenza

    Il problema

    Cheryl dice ad Albert e Bernard che il suo compleanno è una delle seguenti date:

    15, 16 o 19 maggio
    17 o 18 giugno
    14 o 16 luglio
    14, 15 o 17 agosto

    Cheryl comunica in segreto il mese ad Albert e il giorno a Bernard.

    Albert: «Non so quando sia il compleanno, ma so che nemmeno Bernard lo sa.»
    Bernard: «All’inizio non lo sapevo, ma adesso lo so.»
    Albert: «Allora adesso lo so anch’io.»

    Qual è la data del compleanno di Cheryl?

    Prima di proseguire, fermati: prova a cancellare soltanto le date rese impossibili da ciascuna frase, una frase alla volta.

    💡 Mostra un indizio

    Bernard conoscerebbe subito la data se gli fosse stato detto 18 o 19, perché quei giorni compaiono una sola volta nell’elenco.

    Albert è certo che Bernard non possa sapere: che cosa implica questo sul mese ricevuto da Albert?

    💡 Mostra un altro indizio

    Dopo la prima frase restano soltanto luglio e agosto. Bernard afferma di sapere: il suo giorno non può quindi comparire in entrambi i mesi.

    Elimina il giorno 14 e osserva che cosa può dedurre Albert dal mese che conosce.

    ✅ Mostra la soluzione

    Il compleanno di Cheryl è il 16 luglio. La deduzione procede in tre passaggi, seguendo esattamente le tre affermazioni.

    1. Albert sa che Bernard non sa. I giorni 19 e 18 compaiono una sola volta: se Bernard avesse ricevuto uno di questi, conoscerebbe immediatamente la data. Albert può essere certo del contrario soltanto se il mese non è maggio e non è giugno. Restano luglio e agosto.
    2. Bernard ora sa. Dopo aver eliminato maggio e giugno, le date possibili sono 14 e 16 luglio, 14, 15 e 17 agosto. Se Bernard avesse ricevuto 14, avrebbe ancora due possibilità. Poiché ora conosce la data, il giorno non è 14. Restano 16 luglio, 15 agosto e 17 agosto.
    3. Albert ora sa. Se il mese fosse agosto, Albert non potrebbe scegliere tra il 15 e il 17. Siccome afferma di conoscere la data, il mese deve essere luglio. L’unica possibilità rimasta è il 16 luglio.

    Ogni frase diventa informazione pubblica: quando uno dei due parla, l’altro aggiorna non soltanto l’elenco delle date, ma anche ciò che sa sul ragionamento dell’interlocutore.

    Risultato: il compleanno di Cheryl è il 16 luglio.

    La matematica dentro al gioco

    Il problema appartiene alla logica epistemica, che formalizza frasi come “Albert sa che Bernard non sa”. Ogni persona distingue le date in base all’informazione privata ricevuta: per Albert sono equivalenti tutte le date dello stesso mese; per Bernard tutte quelle con lo stesso giorno.

    Una dichiarazione pubblica elimina i mondi incompatibili con ciò che è stato detto. La prima frase cancella maggio e giugno; la seconda cancella il 14; la terza cancella agosto. Questa procedura è chiamata aggiornamento mediante annuncio pubblico ed è usata anche in informatica teorica, teoria dei giochi e sistemi distribuiti.

    Una variante per te

    Ripeti il problema dopo aver eliminato dall’elenco la data del 17 agosto, lasciando invariate le tre frasi.

    La prima frase elimina ancora maggio e giugno. Dopo la seconda restano il 16 luglio e il 15 agosto: il giorno 14 sarebbe ancora ambiguo per Bernard. A questo punto Albert può identificare la data in entrambi i casi, perché ciascun mese conserva una sola possibilità. La terza frase non permette quindi a noi lettori di scegliere: restano due soluzioni, il 16 luglio e il 15 agosto.

    Lo sapevi?

    Il problema comparve nel 2015 in una competizione matematica scolastica di Singapore e fu ideato da Joseph Yeo, docente del National Institute of Education. Dopo essere stato condiviso online diventò virale in tutto il mondo. Il fascino dipende anche dal contrasto tra l’aspetto elementare dell’elenco e il livello di ragionamento necessario: nessun calcolo difficile, ma tre livelli successivi di conoscenza reciproca.

    Problema 1729

    #022 — Il compleanno di Cheryl

    Giochi, enigmi e idee matematiche per menti curiose.

  • Il gioco del 15 impossibile

    Il gioco del 15 impossibile

    Quindici tessere numerate, una casella vuota e una regola semplicissima: si può far scorrere soltanto una tessera adiacente nello spazio libero. Il celebre gioco del 15 sembra chiedere pazienza e abilità, ma nasconde un ostacolo che nessuna sequenza di mosse può superare.

    La griglia è quasi ordinata: soltanto il 14 e il 15 sono scambiati. Bastano poche mosse per sistemarli, oppure c’è qualcosa che impedisce di raggiungere la soluzione?

    Per rispondere non occorre provare tutte le mosse: bisogna scoprire una proprietà che ogni spostamento conserva.

    PROBLEMA 1729 #021

    Tempo: 10–15 minuti

    Difficoltà:

    Classificazione: 3 su 5.

    Categoria: Permutazioni e parità

    Il problema

    Hai una griglia 4×4 con quindici tessere numerate e una casella vuota. Nella configurazione obiettivo le tessere sono in ordine da 1 a 15, leggendo da sinistra a destra e dall’alto in basso, con lo spazio vuoto nell’angolo in basso a destra.

    Parti invece dalla stessa griglia ordinata, ma con le tessere 14 e 15 scambiate. A ogni mossa puoi far scorrere nello spazio vuoto una sola tessera adiacente in orizzontale o in verticale.

    È possibile raggiungere la configurazione ordinata? Se no, come puoi dimostrarlo senza provare tutte le mosse?

    Prima di proseguire, fermati: prova a ragionare su ciò che cambia e su ciò che resta invariato dopo ogni mossa.

    💡 Mostra un indizio

    Leggi le tessere riga per riga, ignorando la casella vuota. Conta quante coppie risultano nell’ordine sbagliato: sono le inversioni.

    Nella griglia finale le inversioni sono zero. Nella griglia con 14 e 15 scambiati ce n’è esattamente una.

    💡 Mostra un altro indizio

    Su una griglia di larghezza pari non basta guardare le inversioni: considera anche la riga della casella vuota, contata dal basso.

    Osserva la parità della somma: numero di inversioni + numero della riga del vuoto dal basso.

    ✅ Mostra la soluzione

    La configurazione è impossibile. Per dimostrarlo associamo a ogni posizione due numeri: le inversioni della sequenza di tessere e la riga occupata dal vuoto, contata dal basso.

    1. Scrivi le tessere riga per riga, ignorando il vuoto. Un’inversione è una coppia in cui il numero maggiore appare prima del minore.
    2. Nella posizione ordinata ci sono 0 inversioni e il vuoto è nella riga 1 dal basso. La somma è 0 + 1 = 1, dispari.
    3. Nella posizione proposta, il solo scambio 15–14 crea 1 inversione; il vuoto resta nella riga 1. La somma è 1 + 1 = 2, pari.
    4. Una mossa orizzontale non cambia né la riga del vuoto né la parità delle inversioni. Una mossa verticale cambia entrambe le parità: la tessera scavalca tre posizioni nella lista e il vuoto passa a una riga adiacente.

    Perciò la parità della somma resta sempre la stessa. Una posizione con somma pari non può trasformarsi in una con somma dispari. Non importa quante mosse tentiamo: le due configurazioni appartengono a due famiglie separate.

    Risultato: scambiando soltanto 14 e 15, il gioco non può essere risolto.

    La matematica dentro al gioco

    Le posizioni delle tessere sono permutazioni. Ogni permutazione ha parità pari o dispari, determinata dal numero di inversioni. Nel gioco del 15 la casella vuota aggiunge una seconda informazione: su una griglia 4×4 una posizione è risolvibile, nella convenzione usata qui, quando inversioni + riga del vuoto dal basso è dispari.

    Questa quantità è un invariante: può cambiare valore numerico durante il gioco, ma non cambia parità. Gli invarianti sono strumenti potenti perché sostituiscono un’enorme esplorazione di casi con un solo controllo. In generale, esattamente metà delle configurazioni possibili del puzzle appartiene alla classe raggiungibile dalla posizione finale.

    Una variante per te

    Passa al gioco dell’8, una griglia 3×3 con otto tessere e uno spazio vuoto. Parti dalla posizione ordinata e scambia soltanto il 7 e l’8. È risolvibile?

    Sulle griglie di larghezza dispari la riga del vuoto non serve: la parità del numero di inversioni resta invariata. La configurazione ordinata ha zero inversioni; lo scambio 7–8 ne crea una. Anche questa variante è quindi impossibile.

    Lo sapevi?

    Il rompicapo fu ideato negli Stati Uniti da Noyes Palmer Chapman negli anni Settanta dell’Ottocento e nel 1880 divenne una moda internazionale. Sam Loyd lo rese celebre con storie e sfide promozionali, arrivando a rivendicarne l’invenzione. La configurazione con 14 e 15 scambiati fu la sfida più famosa proprio perché sembrava quasi risolta: due sole tessere fuori posto, eppure nessuna soluzione.

    Problema 1729

    #021 — Il gioco del 15 impossibile

    Giochi, enigmi e idee matematiche per menti curiose.

  • Missionari e cannibali

    Missionari e cannibali

    Tre missionari e tre cannibali devono attraversare un fiume con una barca che porta al massimo due persone. Sembra un semplice problema di trasporto, finché una regola di sicurezza trasforma ogni viaggio in una scelta delicata.

    Su nessuna riva i cannibali possono essere più numerosi dei missionari, quando almeno un missionario è presente. Inoltre la barca non si muove da sola: a ogni attraversamento qualcuno deve condurla, anche quando tornare indietro sembra vanificare i progressi.

    La soluzione nasce non dall’andare sempre avanti, ma dal controllare gli stati possibili e scegliere con cura chi deve riportare la barca.

    PROBLEMA 1729 #020

    Tempo: 10–15 minuti

    Difficoltà:

    Classificazione: 3 su 5.

    Categoria: Logica e ricerca di percorso

    Il problema

    Tre missionari e tre cannibali si trovano sulla riva sinistra di un fiume. Devono raggiungere tutti la riva destra usando una barca che può trasportare una o due persone.

    Su ciascuna riva, se è presente almeno un missionario, i cannibali non possono mai essere più numerosi dei missionari. La stessa regola vale durante ogni passaggio. La barca deve avere a bordo almeno una persona per muoversi.

    Quale sequenza di attraversamenti permette a tutti di arrivare sani e salvi sull’altra riva?

    Prima di proseguire, fermati: prova a rappresentare dopo ogni viaggio quante persone di ciascun gruppo restano sulle due rive e dove si trova la barca.

    💡 Mostra un indizio

    All’inizio non conviene trasferire missionari da soli: sulla riva di partenza rimarrebbero in minoranza.

    Prova a usare i cannibali per far avanzare e tornare la barca nelle prime mosse, conservando sempre una configurazione sicura.

    💡 Mostra un altro indizio

    A metà percorso dovrai trasferire due missionari insieme e poi riportare indietro una coppia mista.

    Indica uno stato con (M,C,B), dove M e C sono le persone rimaste sulla riva sinistra e B segnala la posizione della barca. Elimina subito ogni stato che viola la regola.

    ✅ Mostra la soluzione

    Una soluzione minima richiede undici attraversamenti. Indichiamo con M un missionario e con C un cannibale.

    1. Due cannibali attraversano: CC →
    2. Un cannibale torna: C ←
    3. Due cannibali attraversano: CC →
    4. Un cannibale torna: C ←
    5. Due missionari attraversano: MM →
    6. Un missionario e un cannibale tornano: MC ←
    7. Due missionari attraversano: MM →
    8. Un cannibale torna: C ←
    9. Due cannibali attraversano: CC →
    10. Un cannibale torna: C ←
    11. Gli ultimi due cannibali attraversano: CC →

    Ogni ritorno ha una funzione precisa: rende disponibile la barca senza creare una maggioranza pericolosa. La coppia mista al sesto passaggio è la mossa meno intuitiva, perché sembra arretrare ma prepara il secondo trasferimento dei missionari.

    Tutti attraversano in 11 viaggi, senza mai violare la regola.

    La matematica dentro al gioco

    Il problema può essere descritto come un grafo. Ogni nodo è uno stato (M,C,B): il numero di missionari e cannibali sulla riva sinistra e la posizione della barca. Due nodi sono collegati quando un viaggio ammesso trasforma uno stato nell’altro.

    Gli stati illegali vengono eliminati. Restano così pochi nodi sicuri, e la soluzione diventa un cammino dal nodo iniziale (3,3,sinistra) al nodo finale (0,0,destra). Una ricerca in ampiezza esplora il grafo per livelli e trova automaticamente un percorso con il minor numero di attraversamenti.

    È lo stesso schema usato in molti problemi di intelligenza artificiale: definire gli stati, stabilire le mosse, imporre i vincoli e cercare un percorso. La parte più difficile non è calcolare, ma scegliere una rappresentazione che renda visibile la struttura.

    Una variante per te

    Lascia invariati i tre missionari e i tre cannibali, ma aumenta la capacità della barca a tre persone. Qual è ora il numero minimo di attraversamenti?

    Esiste una soluzione in cinque viaggi: CC →, C ←, MMM →, C ←, CCC →. Prova a verificare la sicurezza delle due rive dopo ogni mossa e a dimostrare che quattro attraversamenti non possono bastare.

    Lo sapevi?

    Missionari e cannibali appartiene alla grande famiglia dei problemi di attraversamento del fiume. Nel 1968 Saul Amarel lo usò come esempio nello studio della rappresentazione dei problemi nell’intelligenza artificiale.

    Il rompicapo è importante proprio perché la soluzione dipende da come viene descritto. Elencare mosse a caso è faticoso; rappresentare gli stati come nodi di un grafo rende invece naturale applicare algoritmi di ricerca.

    Problema 1729

    #020 — Missionari e cannibali

    Giochi, enigmi e idee matematiche per menti curiose.

  • I cento prigionieri e le cento scatole

    I cento prigionieri e le cento scatole

    Cento persone, cento scatole e una regola che sembra lasciare alla fortuna ogni decisione. Ciascuno può controllare soltanto metà delle scatole e il gruppo vince esclusivamente se tutti trovano il proprio numero.

    Se ognuno sceglie cinquanta scatole a caso, la probabilità di successo collettivo è praticamente nulla. Eppure esiste una strategia condivisa che la porta a oltre il 31 per cento, senza segnali, senza modificare le scatole e senza comunicare durante la prova.

    Il segreto è riconoscere che la disposizione dei numeri non è soltanto casuale: è una permutazione, e ogni permutazione si divide naturalmente in cicli.

    PROBLEMA 1729 #019

    Tempo: 20–30 minuti

    Difficoltà:

    Classificazione: 4 su 5.

    Categoria: Probabilità e permutazioni

    Il problema

    Cento prigionieri sono numerati da 1 a 100. In una stanza ci sono cento scatole, anch’esse numerate da 1 a 100. Ogni scatola contiene uno e uno solo dei numeri dei prigionieri, disposti casualmente: nel complesso, una permutazione dei numeri da 1 a 100.

    I prigionieri entrano uno alla volta. Ciascuno può aprire al massimo cinquanta scatole e deve richiuderle come le ha trovate. Dopo l’inizio non può comunicare con gli altri. Tutti vengono liberati soltanto se ciascun prigioniero trova il foglio con il proprio numero; basta un solo insuccesso perché il gruppo perda.

    Prima della prova possono concordare una strategia. Quale strategia massimizza la probabilità che vincano tutti?

    Prima di proseguire, fermati: prova a trovare una regola che permetta a tutti di esplorare la stessa disposizione in modo coordinato, pur entrando separatamente.

    💡 Mostra un indizio

    La collocazione dei fogli definisce una permutazione dei numeri da 1 a 100. Come si può seguire una permutazione senza conoscerla in anticipo?

    Immagina che il numero trovato in una scatola non sia soltanto un contenuto, ma anche l’indicazione della scatola successiva da aprire.

    💡 Mostra un altro indizio

    Il prigioniero numero 37 potrebbe iniziare dalla scatola 37. Se vi trova il numero 82, aprire la scatola 82; se lì trova 14, continuare con la scatola 14.

    Questa catena prima o poi torna al punto di partenza. Che cosa deve essere vero sulla sua lunghezza perché il prigioniero incontri il proprio numero entro cinquanta aperture?

    ✅ Mostra la soluzione

    Ogni prigioniero segue il ciclo della permutazione che contiene il proprio numero.

    1. Il prigioniero n apre per prima la scatola n.
    2. Se trova il proprio numero, ha finito.
    3. Altrimenti legge il numero m contenuto nella scatola e apre la scatola m.
    4. Ripete la regola, per non più di cinquanta aperture.

    Ogni numero appartiene a un unico ciclo. Tutti i prigionieri che appartengono allo stesso ciclo seguono le stesse scatole, iniziando da punti diversi. Se il ciclo è lungo al massimo cinquanta, ciascuno incontra il proprio numero; se è più lungo, falliscono tutti i membri di quel ciclo.

    Il gruppo vince quindi esattamente quando la permutazione non contiene cicli più lunghi di cinquanta. Per una permutazione casuale di cento elementi la probabilità che esista un ciclo di lunghezza k, con k maggiore di 50, è 1/k. Due cicli così lunghi non possono coesistere, perciò le probabilità si sommano.

    P(vittoria) = 1 − (1/51 + 1/52 + … + 1/100) ≈ 31,18%

    Scegliendo invece cinquanta scatole indipendenti a caso, ogni prigioniero avrebbe probabilità 1/2 di riuscire e la probabilità che riescano tutti sarebbe (1/2)100, circa 7,9 × 10−31. La strategia dei cicli non migliora la probabilità del singolo: crea una correlazione favorevole tra i risultati del gruppo.

    La matematica dentro al gioco

    Una permutazione è un riordinamento degli elementi e può sempre essere scomposta in cicli disgiunti. Per esempio, se la scatola 1 contiene 7, la 7 contiene 3, la 3 contiene 9 e la 9 contiene 1, abbiamo il ciclo (1 7 3 9). Chiunque parta da uno di questi quattro numeri percorre l’intero ciclo.

    La probabilità di fallimento è la probabilità che compaia un ciclo di lunghezza fra 51 e 100. In una permutazione casuale, il numero atteso di cicli di lunghezza k è 1/k; sopra 50 può essercene al massimo uno. Ne segue la formula 1 − (H100 − H50), dove Hn è l’n-esimo numero armonico.

    Il punto sorprendente è la dipendenza tra gli esiti. La scelta casuale rende quasi indipendenti cento eventi con probabilità 1/2 e li moltiplica. La strategia dei cicli trasforma invece cento prove separate in un’unica proprietà globale della permutazione.

    Una variante per te

    Sostituisci cento con 2n: ci sono 2n prigionieri e altrettante scatole, e ciascuno può aprirne n. La strategia resta identica. La probabilità di successo è

    1 − (H2n − Hn)

    Prova a calcolarla per 10 prigionieri e 5 aperture. Che cosa accade aumentando n? Il valore diminuisce lentamente e tende a 1 − ln 2, circa il 30,685 per cento: anche con gruppi enormi, la probabilità non crolla a zero.

    Lo sapevi?

    Il problema comparve nella letteratura informatica nel 2003 in un lavoro di Anna Gál e Peter Bro Miltersen. La strategia dei cicli fu segnalata da Sven Skyum e in seguito il rompicapo si diffuse in varie forme: scatole, armadietti, carte o portafogli.

    Nel 2006 Eugene Curtin e Max Warshauer dimostrarono anche che, nelle condizioni date, la strategia dei cicli è ottimale: nessun altro accordo preventivo può garantire una probabilità collettiva maggiore.

    Problema 1729

    #019 — I cento prigionieri e le cento scatole

    Giochi, enigmi e idee matematiche per menti curiose.

  • La bottiglia avvelenata

    La bottiglia avvelenata

    Mille bottiglie sono allineate in una cantina e una sola contiene una sostanza avvelenata. Hai dieci rilevatori che possono essere usati contemporaneamente, ma il risultato arriverà soltanto il mattino seguente. Come individuare con certezza la bottiglia contaminata in un solo turno?

    Provare una bottiglia alla volta è impossibile, e dividere semplicemente il lotto in dieci gruppi non basta. Il punto non è assegnare ogni bottiglia a un unico rilevatore, ma costruire per ciascuna una combinazione riconoscibile di risposte positive e negative.

    Il classico racconto parla di assaggiatori; qui li sostituiamo con rilevatori binari, senza cambiare la matematica. Ogni rilevatore può ricevere una miscela di gocce provenienti da molte bottiglie e restituisce uno dei due soli esiti: positivo oppure negativo.

    PROBLEMA 1729 #018

    Tempo: 5–10 minuti

    Difficoltà:

    Classificazione: 2 su 5.

    Categoria: Codifica binaria

    Il problema

    Ci sono 1000 bottiglie numerate da 0 a 999. Una sola è avvelenata. Disponi di 10 rilevatori: su ciascuno puoi versare una miscela composta da una goccia di tutte le bottiglie che vuoi. Dopo 24 ore ogni rilevatore darà un risultato positivo o negativo. Puoi effettuare un solo turno di test. Come puoi identificare con certezza la bottiglia avvelenata?

    Prima di proseguire, fermati qui: chiediti quante combinazioni diverse si possono ottenere con dieci risposte che valgono soltanto sì o no.

    💡 Mostra un indizio

    Un rilevatore distingue 2 casi; due rilevatori ne distinguono 4; tre ne distinguono 8. Quanti casi distinguono dieci rilevatori?

    Ogni rilevatore aggiunge una scelta binaria: positivo oppure negativo.

    Con dieci rilevatori ottieni 2¹⁰ = 1024 sequenze diverse, abbastanza per etichettare tutte le 1000 bottiglie.

    💡 Mostra un altro indizio

    Scrivi il numero di ogni bottiglia in binario usando esattamente dieci cifre, da 0000000000 a 1111100111.

    Associa ogni posizione binaria a uno dei dieci rilevatori.

    Da una bottiglia versa una goccia soltanto sui rilevatori corrispondenti alle cifre 1 del suo codice.

    ✅ Mostra la soluzione

    Usiamo le dieci risposte come le dieci cifre di un codice binario.

    1. Scrivi ogni numero da 0 a 999 in forma binaria, completandolo a sinistra fino a ottenere dieci cifre.
    2. Assegna ciascuna delle dieci posizioni del codice a un rilevatore.
    3. Per ogni bottiglia, versa una goccia sui rilevatori nelle cui posizioni il suo codice contiene 1; non versarla dove compare 0.
    4. Dopo 24 ore interpreta un rilevatore positivo come 1 e uno negativo come 0.
    5. La sequenza ottenuta è esattamente il numero binario della bottiglia avvelenata.

    Per esempio, la bottiglia 713 ha codice 1011001001. Le sue gocce vengono inserite nei rilevatori associati alle cinque posizioni in cui compare 1. Se è quella contaminata, il mattino seguente i risultati ricompongono proprio 1011001001, che in base dieci vale 713.

    10 bit distinguono 2¹⁰ = 1024 casi: una sola notte basta.

    La matematica dentro al gioco

    Il gioco è un problema di codifica dell’informazione. Ogni rilevatore fornisce un bit: 0 se il test è negativo, 1 se è positivo. Dieci bit possono rappresentare tutti gli interi da 0 a 1023.

    La strategia non cerca la bottiglia con prove successive; assegna prima a ogni bottiglia una firma unica. Il risultato collettivo dei test non è un semplice conteggio, ma una parola binaria che identifica direttamente un elemento.

    In generale, con k rilevatori binari si possono distinguere al massimo 2ᵏ possibilità. Per n bottiglie occorre quindi il più piccolo k tale che 2ᵏ ≥ n, cioè k = ⌈log₂ n⌉.

    È la stessa idea usata nei codici digitali: combinando componenti che hanno soltanto due stati si possono rappresentare quantità molto grandi di informazione.

    Una variante per te

    Quanti rilevatori servono per 2000 bottiglie? Dieci non bastano, perché 2¹⁰ = 1024. Undici producono 2¹¹ = 2048 combinazioni, quindi sono sufficienti.

    Prova ora il problema inverso: con 12 rilevatori, qual è il massimo numero di bottiglie distinguibili in un solo turno? La risposta è 2¹² = 4096.

    Lo sapevi?

    La versione tradizionale dell’enigma ricorre spesso a prigionieri o cavie e a un veleno che agisce in una notte. Sostituirli con rilevatori a due stati rende esplicita la struttura matematica e conserva intatto il problema.

    Il principio è vicino a quello dei codici identificativi e della diagnostica combinatoria: più campioni vengono raggruppati secondo schemi diversi e la combinazione dei test positivi rivela quale elemento cercare.

    Problema 1729

    #018 — La bottiglia avvelenata

    Giochi, enigmi e idee matematiche per menti curiose.