I 22 passi

Bramo Logicar mi risponde con un programma: ha dimostrato che 22 è davvero il numero minimo di mosse facendosi aiutare dal computer. Ora qualche purista potrebbe brontolare, siamo sicuri che una dimostrazione fatta dal computer sia una vera dimostrazione? E poi, è una bella dimostrazione?

Bé, quando non esiste altra strada, non conta molto il giudizio estetico. Ma se il programma è un bel programma, tanto meglio. E, in ogni caso, il programma è stato scritto da un umano, basta leggerlo e controllare che funzioni bene. Per dire: come faccio a fidarmi del fatto che l'ultimo teorema di Fermat è stato dimostrato? Quante persone al mondo sono in grado di leggere la dimostrazione e giudicarla? Perché non devo avere problemi su quella dimostrazione e devo farmene invece su un programma che potrei leggere, o scrivere, io stesso?

Il programma di BL è bellissimo, ma è scritto in perl, linguaggio che io non conosco. E allora come faccio a dire che è bellissimo?

Bé, si vede. Anche se non conosco i dettagli del linguaggio, comunque capisco il senso del programma. E vedo anche l'eleganza con cui è scritto. Lo lancio, e mi mostra la sequenza di 22 mosse (una sequenza di 22 mosse) che risolve il problema. E, per come mi è stato descritto il funzionamento, capisco anche che quello è il minimo. Ma voglio andare più a fondo, e decido di riscrivere il programma utilizzando un linguaggio che conosco un po' e che mi piace molto: python.

(Disclaimer: programmatori seri che state per leggere il seguito, abbiate pietà. Sono un autodidatta di questo linguaggio, non conosco tutte le sue potenzialità, sto sperimentando. Se avete suggerimenti per migliorarlo, e migliorare la mia comprensione, fateli pure)

Il programma ha una filosofia molto semplice: analizza l'albero di tutte le mosse fino a che non arriva alla soluzione. Quindi non ci si può sbagliare: la prima soluzione che salta fuori è quella che si ottiene con il numero minimo di mosse.

Entrando più nel dettaglio, il programma parte dalla posizione iniziale e genera tutte le possibili mosse ottenibili facendo un movimento. Queste vengono memorizzate assieme al numero di mosse necessarie per arrivare in quella posizione, e (qui sta il bello) assieme anche alla posizione da cui provengono, per poi recuperare il percorso una volta giunti alla fine. Poi ricomincia, partendo dalle nuove posizioni ottenute e generando tutte le nuove possibili mosse, e così via.

Arrivati alla soluzione, basta percorrere il cammino all'indietro per ottenere l'elenco di tutti i passaggi.

La griglia delle varie posizioni viene numerata in questo modo

         ___     ___
        |   |   |   |
        | 2 |   | 6 | 
 ___ ___|___|___|___|___
|   |   |   |   |   |   |
| 0 | 1 | 3 | 5 | 7 | 9 |
|___|_ _|___|___|___|___|
        |   |   |   |
        | 4 |   | 8 | 
        |___|   |___|

e memorizzata in una lista (all'inizio una stringa, in realtà, poi trasformata in una lista per lavorarci sopra). Dunque la posizione iniziale sarà memorizzata così: "AI.L.A.T.I". In realtà nel programma al posto dei puntini ci metto degli zeri, per poter fare dei controlli più comodamente, ma non ha importanza.

Ecco la parte di programma che si occupa di definire la griglia: nella lista c è contenuto, per ogni casella, l'elenco delle caselle confinanti.



La variabile w contiene la posizione iniziale, finale naturalmente contiene quella finale, Nmax contiene il livello massimo al quale il programma arriverà: se non è stata trovata una soluzione fino a quel momento, si ferma.

mosse è un dizionario: è la struttura che associa, ad ogni posizione, il livello al quale la posizione è stata incontrata la prima volta, assieme alla posizione precedente, dalla quale questa proviene. All'inizio contiene solo la posizione di partenza w, che si trova a livello 0 e non proviene da nessun'altra posizione (in realtà qui la definiamo come proveniente da sé stessa).

Proseguiamo. Questa è la funzione che si occupa di calcolare la lista di tutte le possibili posizioni ottenibili con una mossa, a partire da una posizione m data.



Contiene un ciclo che esplora ogni casella, e se ne trova una vuota (cioè contenente 0) per ogni casella confinante fa uno scambio: la lettera che si trova nella casella confinante va in quella vuota. Tutte le nuove posizioni vengono inserite nella lista ris, inizialmente vuota, che alla fine viene restituita al programma chiamante.

Ora il programma principale:



È un ciclo che ripete sempre la stessa procedura, fino a che non arriva a trovare una soluzione (o non arriviamo al livello Nmax). Dal dizionario di tutte le mosse estrae quelle del livello precedente; per ogni mossa crea la lista delle mosse successive; se queste sono nuove (cioè non stanno già nel dizionario), allora vengono inserite, assieme al loro livello e alla mossa precedente. Se trova la posizione finale, ferma tutta la baracca.

Ora si tratta di stampare per bene il risultato. La funzione bellastampa()



stampa in maniera comprensibile le varie posizioni. Non c'è molto da dire, se non che ho provato a utilizzare un sistema per contare il numero di mosse utilizzando una variabile statica locale (invece di una variabile globale). Probabilmente non è il modo migliore, ma tant'è.

E ora la parte finale:



la funzione scrivisoluzione() è ricorsiva, e permette di scrivere l'elenco delle mosse dalla prima all'ultima (e non dall'ultima alla prima). Noi la chiamiamo passandole, come parametro, l'ultima posizione trovata (quella finale, insomma), e lei ripercorre l'albero delle mosse all'indietro, fino a tornare al livello zero. Da lì comincia a stampare, in discesa, tutte le mosse.

Ed ecco il risultato:

. .
 0: AILATI
      . .

      . T
 1: AILA.I
      . .

      . T
 2: AILAI.
      . .

      L T
 3: AI.AI.
      . .

      L T
 4: AI.A..
      . I

      L T
 5: AI..A.
      . I

      L T
 6: A.I.A.
      . I

      L T
 7: A..IA.
      . I

      L T
 8: A..I.A
      . I

      L T
 9: .A.I.A
      . I

      L .
10: .A.ITA
      . I

      L .
11: ..AITA
      . I

      L .
12: ...ITA
      A I

      L .
13: ..I.TA
      A I

      L .
14: ..IT.A
      A I

      L .
15: .I.T.A
      A I

      L .
16: .IT..A
      A I

      L .
17: I.T..A
      A I

      L .
18: IT...A
      A I

      . .
19: ITL..A
      A I

      . .
20: IT.L.A
      A I

      . .
21: ITAL.A
      . I

      . .
22: ITALIA
      . .

Appendice: ho scritto questo post prima di pubblicare il precedente, nei cui commenti si discute sulla validità di una dimostrazione fatta col computer. In questo caso credo che sia abbastanza semplice da poter essere considerata valida anche dai puristi. Comunque sia, il programma, prima di terminare, ha analizzato e memorizzato 24824 posizioni diverse. Per la precisione:

Posizioni di livello  0 =    1
Posizioni di livello  1 =    4
Posizioni di livello  2 =   12
Posizioni di livello  3 =   30
Posizioni di livello  4 =   58
Posizioni di livello  5 =  130
Posizioni di livello  6 =  200
Posizioni di livello  7 =  358
Posizioni di livello  8 =  442
Posizioni di livello  9 =  660
Posizioni di livello 10 =  766
Posizioni di livello 11 = 1106
Posizioni di livello 12 = 1243
Posizioni di livello 13 = 1642
Posizioni di livello 14 = 1692
Posizioni di livello 15 = 2188
Posizioni di livello 16 = 2119
Posizioni di livello 17 = 2427
Posizioni di livello 18 = 2029
Posizioni di livello 19 = 2289
Posizioni di livello 20 = 2046
Posizioni di livello 21 = 2461
Posizioni di livello 22 =  921

Una pecora, in un campo, con un lato nero

Cosa dire del quesito che ho postato sabato, quello sulla trasformazione della parola "AILATI" in "ITALIA", seguendo certe regole? Per quanto mi riguarda, mi piace poco, perché non si può risolvere se non andando a tentativi.

Siamo sicuri? Non si può, o io non ci sono riuscito?

Ma vediamo cosa è successo in realtà.

La mia scuola era una sede per i giochi matematici della Bocconi. Tempo prima dello svolgimento delle gare arriva a scuola un bel pacco sigillato contenente i testi e le soluzioni, che l'insegnante responsabile per la scuola mette in cassaforte, al riparo da sguardi indiscreti. Sul foglio risposte era riportato questo risultato, per il suddetto quesito: 26.

Qualche giorno prima della data delle gare arriva un'email urgente che dice che c'è un errore nella risposta, quella corretta è 24. Bene, prendiamo nota.

Finalmente arriva il giorno delle gare, tutti i partecipanti sono nelle aule, la banda di impallinati di giochi matematici della quale faccio parte è chiusa in un laboratorio della scuola, pronta per correggere. Cominciano ad arrivare i primi fogli con le risposte: correggiamo, facciamo un doppio controllo, introduciamo i dati nel computer.

Tra gli impallinati di giochi ci sono anche dei giocatori (figli, studenti, amici). Questi strani personaggi prima partecipano alla gara, poi vengono a fare un salto dove siamo noi correttori e danno una mano anche loro (a volte vengono solo a mangiare, perché è chiaro che tutto ciò che sto raccontando è fatto allo scopo di fare bisboccia, ehm). La prima cosa che fanno, però, prima ancora di mangiare qualche fetta di torta, è controllare le risposte. Arrivato al famoso quesito, uno di loro dice: «ma no, 24? È sbagliato! Io ho dimostrato che con 22 passi ci si riesce».

Fermi tutti, ma come? Ricontrolliamo, dai. Il gruppetto di giocatori/correttori si mette davanti a un foglio e, con una fetta di torta in una mano e una matita nell'altra, tutti cominciano a ricostruire la sequenza di mosse.

E noi che facciamo? C'è gente che ha risposto 24, e a cui abbiamo dato buona la risposta. C'è altra gente a cui invece abbiamo dato sbagliata la risposta 22, che facciamo se è giusta? Chiamiamo i colleghi di Carpi, anche loro sede dei giochi, ma sono un po' indietro con la correzione e non si sono ancora posti il problema. Chiamiamo Milano direttamente, ci dicono che controlleranno, ma capiamo che sono un po' nel caos (comprensibilmente: sono la sede centrale, avranno ricevuto un sacco di telefonate). Per un momento arriva l'indicazione di dare buone entrambe le risposte, ma nel nostro laboratorio c'è la ribellione: o è giusta una, o è giusta l'altra. Poi anche i milanesi riescono a trovare un momento per ricontrollare tutto, e finalmente si decide che 22 è la risposta giusta.

Proseguiamo la correzione, facciamo le premiazioni, arrivederci a tutti.

Però, c'è un però. Lo spirito del matematico che vede mezza pecora nera in un campo aleggia su di noi: il quesito chiede chiaramente quale sia il numero minimo di passi. Come facciamo a essere sicuri che sia il minimo? Chi ha scritto il quesito lo sa? Perché un conto è trovare una soluzione in 22 passi, un altro è invece dimostrare che con meno passi non ci si riesce.

Quando arrivo a casa, chiedo a .mau. (che, pur essendo anziano pure lui, si diletta ancora a fare giochi matematici) se dalle sue parti hanno riscontrato gli stessi problemi. Lui personalmente no (il quesito era considerato troppo facile per la categoria Grande Pubblico, quella a cui lui appartiene), però mi racconta che  anche a lui hanno chiesto di controllare se effettivamente esistesse una soluzione in 22 mosse. La richiesta proveniva da un altro amichetto, giocatore pure lui, e pure lui aiutante nelle correzioni. Amichetto che io conosco solo attraverso internet, l'ho incontrato per la prima volta sulle pagine di Rudi Mathematici, con lo pseudonimo di Bramo Logicar. Mi dice .mau. che lui ha la soluzione definitiva del problema, e quindi gli scrivo per conoscerla. Come dicevo, mi piacciono le soluzioni. Vorrei sapere se dall'altra parte la pecora è nera.

Affermazioni pericolose

Un ingegnere, un fisico e un matematico sono in vacanza in Scozia, quando da un finestrino del treno su cui stanno viaggiando scorgono una pecora nera nel mezzo di un campo.

«Ma guarda», osserva l'ingegnere, «tutte le pecore scozzesi sono nere!»

Il fisico interviene: «No, no! Alcune pecore scozzesi sono nere!»

Il matematico guarda i due con commiserazione e poi dichiara: «In Scozia esiste almeno un campo contenente almeno una pecora che ha almeno un lato nero».

A me piacciono i giochi matematici. Mi piace proprio l'idea, il concetto in sé: sono anziano e non sono tanto veloce nella loro risoluzione, per partecipare a una gara senza sfigurare troppo di fronte ai miei studenti dovrei allenarmi molto, e poi ho questa difficoltà irrisolta nei confronti delle operazioni con i numeri per cui spesso devo rifare i calcoli un sacco di volte. Le somme e le sottrazioni sono quelle che mi danno più da fare…

Se ho fra le mani un libro di giochi matematici non mi metto quasi mai a leggerli uno per uno per tentare di risolverli: a me piacciono proprio le soluzioni. Ho una particolare attenzione nei confronti delle soluzioni belle (secondo il mio particolare e soggettivissimo senso estetico per questo argomento), me le leggo e me le gusto. Mi piace vedere come il testo del problema viene matematizzato, perché di solito un problema viene presentato in forma dematematizzata, come direbbero i Rudi Mathematici, con una ambientazione, una storia, con qualche dato nascosto magari. Mi piace quando viene presentata una strada semplice che con pochi calcoli porta al risultato, strada che però è quasi invisibile, e che va cercata con molta attenzione. Come in una caccia al tesoro.

Bene, fine della premessa, ora arrivo al punto.

Qualche giorno fa si sono svolte le gare provinciali dei giochi matematici organizzati dalla Bocconi (le uniche gare alle quali possono partecipare tutti, non soltanto gli studenti, ma questa è un'altra storia). C'era un quesito che diceva più o meno così: data la seguente tabella:

         ___     ___
        |   |   |   |
        |   |   |   | 
 ___ ___|___|___|___|___
|   |   |   |   |   |   |
| A | I | L | A | T | I |
|___|_ _|___|___|___|___|
        |   |   |   |
        |   |   |   | 
        |___|   |___|

potendo spostare ogni lettera in una casella adiacente vuota, qual è il numero minimo di mosse per arrivare alla seguente configurazione?

         ___     ___
        |   |   |   |
        |   |   |   | 
 ___ ___|___|___|___|___
|   |   |   |   |   |   |
| I | T | A | L | I | A |
|___|_ _|___|___|___|___|
        |   |   |   |
        |   |   |   | 
        |___|   |___|

Per ora non scrivo la soluzione, vi lascio giocare un po'. Mentre fate le vostre prove, ripensate alla storiella che fa ridere solo i matematici che ho riportato all'inizio di questo post (non devo sottolineare il fatto che il matematico ha ragione, vero?).

[La tabella in ascii art fa schifo, ma non ho capito come fare per costruire una tabella in html, digeribile da blogger, con le dimensioni fisse]

Il gatto di Arnold

Il sistema dinamico costruito da Arnold per mostrare la proprietà di mixing fa uso di un gatto. Non che sia importante la presenza del gatto, eh, ma Arnold utilizzava sempre dei disegnini nei suoi libri per fare capire le cose, sana e ottima pratica spesso dimenticata da molti docenti universitari (per dire, ho già parlato del mio libro di geometria senza figure, tempo fa).

Prendiamo un toro.

In matematica e in storia dell'arte per toro si intende una ciambella, non l'animale (interessante l'etimologia). Una cosa così, insomma (grazie a wikipedia):

Siccome è scomodo da disegnare, trasformiamolo un po': se lo tagliamo in modo da aprirlo, come se aprissimo l'anello di una catena, e poi lo stendiamo, otteniamo un cilindro. Se poi tagliamo il cilindro in modo da aprire anche quello, otteniamo un rettangolo. Ecco, ho trovato un video che spiega la costruzione del toro a partire da un rettangolo in modo molto chiaro:

Bene, siccome non ci interessa il fatto che il toro sia immerso nello spazio tridimensionale, per semplicità possiamo sempre fare riferimento al rettangolo che lo genera. In pratica è come se avessimo una carta geografica in cui se usciamo da destra rientriamo a sinistra, e viceversa. E se usciamo dall'alto, rientriamo dal basso, e viceversa. Mi accorgo di aver già parlato una volta della costruzione del toro, qui. In quel caso avevo fatto dei disegnini a mano…

Andiamo avanti: per comodità prendiamo un quadrato, invece di un rettangolo. Il sistema dinamico del gatto di Arnold prende il quadrato, lo deforma in un certo modo, e poi rimappa sul quadrato iniziale il risultato ottenuto. La deformazione è fatta così: dato un quadrato (immaginando che sia un toro)

lo deformiamo in questo modo

[per chi è interessato, l'equazione della trasformazione è questa: (x,y) → (2x+y,x+y)].

Ora ricordiamoci che siamo su un toro, e quindi ciò che esce da destra rientra da sinistra, e ciò che esce dell'alto rientra dal basso. Se coloriamo i vari pezzi che escono dal quadrato iniziale, così

possiamo renderci conto di dove essi vadano a finire quando li rimettiamo all'interno del quadrato di partenza:

Come si vede, il quadrato iniziale è stato mischiato un po'. Bene, si può dimostrare che questo sistema è mescolante. Arnold l'ha spiegata così: se disegniamo un gattino sul quadrato, dopo infinite iterazioni ogni parte del quadrato contiene la stessa percentuale di gattino. Ecco:

Volendo, si potrebbe anche parlare di fornai e di ferri di cavallo.

Agitato, non mescolato

«Un Martini dry,» disse [Bond] alla fine. «Ma versatelo in una grande coppa da champagne.»

«Benissimo, Monsieur.»

«Un momento. Tre dosi di Gordon, una di vodka, mezza di China Lillet. Versate nello shaker, agitate col ghiaccio e poi aggiungete un bel po’ di scorza di limone.»

Qualche post fa avevo parlato di sistemi ergodici, traducendone la definizione matematica in questo modo: belli sparpagliati. Ma non c'è limite al caos, si può fare di meglio.

Per esempio, il sistema che avevo descritto, quello dei movimenti quasi periodici sulla circonferenza, non mischia per bene tutto: un archetto viene trasformato in un archetto, i suoi punti rimangono tutti vicini, mantenendo il loro ordinamento.

Qualcuno potrebbe desiderare delle proprietà di mescolamento più forti. Per esempio, supponiamo di voler ricreare il cocktail preferito da James Bond, e immaginiamo di mescolare, scusate, agitare, in modo tale che la dose di vodka si sposti all'interno dello shaker come farebbe l'archetto di cui sopra lungo la circonferenza: questo non sarebbe accettabile. La parte di vodka rimarrebbe tutta insieme (pur occupando, a lungo andare, tutte le possibili posizioni all'interno dello shaker) e James Bond non sarebbe contento.

Quello che noi vorremmo è che le proporzioni degli ingredienti (tre dosi di gin, una di vodka, mezza di vermut) fossero rispettate in ogni parte del cocktail, sia che ce lo beviamo tutto in un colpo, sia che lo sorbiamo lentamente.

Bene, un sistema dinamico con questa proprietà di mescolamento viene detto, guarda un po', sistema mescolante o mixing. Tutti i sistemi mescolanti sono ergodici, ma non è vero il viceversa. La proprietà di essere mescolante è più forte dell'ergodicità.

Un esempio di sistema mescolante molto semplice venne proposto da Arnold (mitico matematico russo) verso la fine degli anni '60.

Il sistema utilizza un gattino.

Intrecci

È dal, uhm, 1990, più o meno, che non vado a una gita viaggio di istruzione di più giorni con la scuola. Da quando quello studente, per consolare la compagna dell'altra classe, ha passato la notte nella sua camera a, appunto, consolarla. Poi è stato così signore da raccontarlo a tutti, il giorno dopo.

Domani si va in montagna, due giorni, a sciare, con poco meno di cinquanta studenti di tutte le classi. Gli altri stanno a scuola a fare autogestione assemblea di istituto. Staremo in un albergo vicino alle piste da sci, sugli Appennini, lontano dalla civiltà  Di notte ci saranno solo il freddo, la neve e i lupi: confido nel fatto che tutti saranno abbastanza stanchi da voler dormire almeno un pochino.

Nel prepararmi alla partenza mi viene in mente di quando, in prima media, andai in settimana bianca con la scuola. Settimana bianca non è un modo di dire: siamo stati via una settimana intera, con tutta la scuola, e tutti i professori. Ora, i miei ricordi si sono magari un pochino sbiaditi, la prima media l'ho fatta un po' di tempo fa, in effetti, però ricordo bene che la scuola venne chiusa, e che con noi c'erano tantissimi professori. C'era la prof di tedesco, che forse ha provato a farci un pochino di ripasso una sera, non la prima sera però, perché era domenica, c'era il Gran Premio di Formula 1, la prima gara della stagione, e c'erano delle auto di una marca nuova che facevano dei tempi incredibili, erano delle Ligier.

C'era il prof di musica, il maestro Pippo Casarini, che ogni tanto cito nei social network per anziani che frequento, perché è stato quello che ha scritto la musica della canzone Quarantaquattro Gatti, e una sera ce l'ha suonata e cantata, e poi ce ne ha fatta ascoltare un'altra, che aveva proposto allo Zecchino d'Oro, ma che non venne accettata. Si intitolava Il Pappagallo Balbuziente (o forse Il Pappagallo Giramondo, guarda cos'ho trovato), e raccontava appunto di un pappagallo che non parlava mica tanto bene, e nessuno capiva cosa dicesse, e poi alla fine si scopre che voleva dire “A sùn d'Mòdna”, cioè “sono di Modena”, in dialetto modenese. Quelli dello Zecchino d'Oro non l'hanno accettata perché c'era una frase in dialetto, e a loro non piaceva, vabbé.

Poi c'era la Viola. Per spiegare chi fosse la Viola, devo specificare che io, alle medie, andavo in una scuola che non aveva classi miste. C'erano le femmine, sì, ma stavano in altre classi, in posti lontani: altri corridoi o, addirittura, altri piani. La Viola era una famosa nella mia classe, non perché noi primini conoscessimo il concetto preciso di sesso opposto, ma perché ne parlavano i bocciati. I bocciati, in prima media, sono un gradino al di sotto di Dio, quindi son gente da ascoltare con le orecchie ben aperte. E ne parlavano perché, insomma, loro frequentavano con attenzione gli altri corridoi e gli altri piani, e compivano dettagliate analisi statistiche, e avevano notato che la Viola era una fanciulla notevolmente, come dire, sviluppata, ecco. E una volta che uno ti fa notare questo particolare, poi fai fatica a distogliere lo sguardo. O i pensieri.

E così, domani partiamo in cinquanta, ma allora eravamo ben di più, mi sa. E ancora mi chiedo come abbiano fatto i professori e il preside (o la preside? non ricordo proprio se fosse maschio o femmina, strano, perché la Viola me la ricordo bene, non era mica un maschio, no, decisamente no) a portarci tutti in montagna, a sciare, senza tanto controllo, sia di giorno che di notte, per una settimana intera. Noi stiamo via solo una notte, speriamo che non ci siano troppe fanciulle da consolare.

Facciamo così, il tasto “pubblica” lo clicco quando torno. Così, per scaramanzia.

(Ciao, Viola, chissà che fine hai fatto)

---

Sono tornato. Siamo tornati tutti, anche se uno in eliambulanza. Ma sta abbastanza bene. Tutto sommato, è andata bene.

E proprio mentre pensavo “è andata bene, via, posso pubblicare”, mi è arrivata la notizia della morte della moglie di un collega. Uno di quegli eventi improvvisi e inaspettati che ti sconvolgono la vita, e ti fanno pensare. E l'unica idea che posso accettare è che tutta la roba che abbiamo intorno sia davvero un enorme spreco di spazio, se non servisse a niente. E senza tante prove ontologiche, dimostrazioni logiche, analisi teologiche, vorrei poter consolare il collega, l'amico, dicendogli: “la rivedrai”.

Avevo quasi deciso di cancellare tutto, poi ho pensato che ciò che ho scritto non è del tutto fuori luogo, nonostante tutto. Si tratta solo di un breve segmento della linea di universo della mia vita, che si intreccia con tante altre linee, crea relazioni, interagisce col mondo e lo costruisce. Siamo tutti sub-creatori, siamo tutti poco meno degli angeli, ci rivedremo tutti.