Scacchi e astronomia

Secondo un’antica leggenda, l’inventore degli scacchi si presentò un giorno al palazzo reale, e chiese di poter presentare il gioco al sovrano. Il re lo ricevette e rimase tanto affascinato che si dichiarò pronto a offrire qualsiasi ricompensa al suo ospite. Questi disse però che si sarebbe accontentato di un chicco di grano per la prima casella della scacchiera, di due chicchi per la seconda, di quattro per la terza, e così via. Il sovrano si meravigliò di tanta modestia, e gli ricordò che poteva avere molto di più: una provincia del regno, un castello, una rendita a vita per lui e isuoi discendenti. Ma l’inventore non si mosse dal suo proposito. Il re diede ordine al tesoriere di provvedere, ma l’indomani ricevette la spiacevole notizia: non sarebbe bastato il raccolto annuale di tutto il regno, e nemmeno i raccolti di dieci anni di tutto il mondo. In effetti il geniale inventore aveva richiesto più di diciotto miliardi di miliardi di chicchi di grano: un numero decisamente astronomico.

Le connessioni tra scacchi e astronomia non si fermano certo qui. Nel trattato duecentesco noto come “Libro de los juegos” venivano descritti gli "scacchi astronomici", da giocare su una scacchiera composta di sette cerchi concentrici, uno per ogni pianeta del modello geocentrico. La struttura dell’universo tolemaico, d’altra parte, sembra essere stata determinante anche nell’origine (indiana e successivamente araba) degli scacchi classici: la scacchiera 8×8, infatti, si ricondurrebbe alle otto sfere concentriche presenti in quel sistema cosmologico.

In tempi recenti, molti astronomi, per esempio Arthur Eddington, Eugene Antoniadi e Fred Hoyle, sono stati anche ottimi giocatori di scacchi. Ma alfieri e cavalli si muovono anche nello spazio: nel giugno 1970, i cosmonauti Vitaly Sevastyanov e Andrian Nikolayev giocarono una partita contro la sala controllo mentre erano a bordo della Soyuz 9. Sette anni dopo, Sevastyanov divenne presidente della federazione di scacchi dell’URSS. Nel 1999 Sergei Andeyev si portò sulla stazione spaziale
Mir un notebook con un programma di scacchi, per non rinunciare al suo passatempo preferito durante la lunga permanenza nello spazio. L’astronauta americano Gregory Chamitoff giocò a scacchi contro la stazione di controllo mentre si trovava sullo Space Shuttle e quando era a bordo della ISS: una delle sue partite Spazio-Terra, nel maggio 2011, venne ufficialmente sponsorizzata dalla NASA e resa pubblica attraverso i social network.

Anche la fantascienza ha messo in scena partite di scacchi, giocate su astronavi o su pianeti immaginari. Memorabile, a questo proposito, la sonora sconfitta che nel film “2001: Odissea nello spazio” il supercomputer HAL 9000 infligge all’astronauta Frank Poole. Nell’universo di Dune esiste una complicata variante del gioco degli scacchi, denominata “Cheops”. Oltre a pezzi familiari come il re, la regina, la torre e il cavallo, ve ne sono alcuni di peculiari come il primo ministro e i ministri, il duca e la duchessa, il barone e la baronessa, l’assassino, il falco, il soldato, il pastore, la spia.
Ma soprattutto il gioco si svolge su una scacchiera dalla forma piramidale (ecco spiegato il nome). Obiettivo dei giocatori è portare la propria regina sul vertice, al nono piano della piramide, e mettere sotto scacco il re avversario.


Immaginate ora una mini-scacchiera 3×3, con due cavalli bianchi agli angoli superiori e due cavalli neri agli angoli inferiori. Esiste, secondo voi, una sequenza di mosse che porti da questa configurazione di partenza a quella indicata a destra nella figura, con i cavalli di sinistra scambiati tra di loro?

Naturalmente, i cavalli possono muoversi secondo le regole classiche degli scacchi, e una casella non può essere occupata da due pezzi. Buon divertimento!

Germogli

Stamattina sono uscito a fare una breve passeggiata con mia moglie alle pendici delle colline veronesi. Dopo molti giorni grigi, finalmente il sole ha fatto capolino lanciando una promessa di imminente primavera, e la visione luminosa degli alberi in fiore e dei nuovi germogli ci ha fatto bene al cuore.
D'altra parte, oggi è Pasqua, festa di resurrezione per antonomasia, la cui data è legata, anche matematicamente, a quella dell'equinozio di primavera.

Ma dicevo dei germogli. Esiste un gioco che porta proprio questo nome (in inglese sprouts), e non credo che esista una stagione migliore di questa per provare a giocarci.
Il gioco nacque nel 1967 nella mente geniale di John Conway, ideatore anche dell'automa cellulare Game of life, dell'algoritmo Doomsday per calcolare i giorni della settimana, dei numeri surreali e di molte altre meraviglie matematiche. A plasmare l'idea collaborò anche un collega di Conway a Cambridge, Michael Paterson.
Il gioco dei germogli ebbe subito un grande successo, come ricorda lo stesso Conway:

"Il giorno in cui i germogli incominciarono a germogliare sembrava che tutti, tra una lezione e l'altra, al caffè o nella pausa per il tè fossero presi dal nel nuovo gioco. In ogni angolo c'erano gruppi di studenti e professori che analizzavano movimenti e strategie dei germogli"

Come si gioca a Germogli? E' molto semplice: basta un foglio di carta e due giocatori, forniti ciascuno di una matita.
Si comincia tracciando sul foglio alcuni punti (o pallini): ne bastano pochi, ad esempio sette o otto.
A turno, ogni giocatore traccia una linea che unisca due punti (se si preferisce, la linea può partire da un punto e finire sullo stesso punto), e segna sulla linea tracciata un nuovo punto.
La linea può avere una forma qualunque, ma non deve intersecare le altre linee già presenti, né attraversare i punti esistenti. Per dirla matematicamente, il grafo del gioco deve mantenersi planare.
Il nuovo punto non deve coincidere con uno dei due punti estremi della linea: tipicamente viene disegnato intorno alla metà della linea, in modo da suddividerla, di fatto, in due nuove linee.
Esiste un'ultima regola da rispettare: da ogni punto non possono partire più di tre linee.
Vince il giocatore che, dopo aver tracciato la sua linea, mette l'avversario nelle condizione di non poter tracciare nuove linee.
Tutto qui.

Com'è noto, in matematica "bello" è quasi un sinonimo di "semplice". Ma "semplice" è il contrario di "complicato", e non di "complesso". Complicato è male, complesso è bene, si potrebbe sintetizzare. Tanto è vero che molte idee semplici, come i germogli di Conway, danno origine a meravigliose complessità, che rimangono belle e per nulla complicate.
La bellezza e l'eleganza hanno spesso a che fare con la complessità che, a sorpresa, sgorga dalla semplicità.
Il gioco "primaverile" di Conway è, in questo senso, un esempio brillante di semplicità e bellezza matematica: non stupisce quindi il fatto che sia stato ideato da un matematico e che molti matematici, a partire dallo stesso autore (in particolare nel suo libro "On Numbers and Games"), lo abbiano studiato in profondità.

Nelle tre figure seguenti è illustrata una semplice partita, con un solo punto iniziale (indicato in rosso). Come mostrato nella prima figura, il primo giocatore traccia una linea dal punto iniziale a se stesso, creando un nuovo punto (indicato in nero). Il secondo giocatore ha due mosse a disposizione, illustrate nelle due figure successive, ma entrambe lo portano alla vittoria, in quanto bloccano le mosse del primo giocatore.

In generale non esiste una strategia per giocare a Germogli, ma l'analisi del gioco porta a individuare metodi vincenti, suggerendo quali curve chiuse o aperte convenga tracciare per bloccare l'avversario. Ma tornerò sull'argomento nei prossimi post.
Per adesso, vi invito a cimentarvi nel gioco, per scoprire quanto possa essere un gioco divertente e metematicamente affascinante.
Ad esempio, per queste vacanze pasquali, potrebbe essere un'ottima alternativa alle gite fuori porta, rese impossibili dal tempo che non sembra affatto essersi messo al bello stabile.
Buona Pasqua e buona Pasquetta con i germogli!

Carnevale dei Libri di Scienza #2: il gioco

Il poeta tedesco Friedrich Schiller sosteneva che “L'uomo è veramente uomo soltanto quando gioca". Il suo omonimo e connazionale Friedrich Nietzsche, in “Così parlò Zarathustra”, rafforzò il concetto dicendo che “Nell'uomo autentico si nasconde un bambino: che vuole giocare”

Parlando di scienza, poi, perderemmo inevitabilmente di vista qualcosa se non tenessimo in seria considerazione la prospettiva del gioco. Lo scienziato, normalmente, coltiva in sé lo spirito ludico e l’atteggiamento curioso del bambino che gioca, coniugandolo con una concezione più matura che aspira alla sintesi e alla visione d’insieme. A questo proposito, il fisico americano Isidor Isaac Rabi, premio Nobel nel 1944, disse che “La scienza è un grande gioco che ispira e tonifica, e il campo di gioco è l'universo stesso.”

D’altra parte, lo spirito giocoso è utile non solo per chi la scienza la fa, ma anche, e soprattutto, per chi la comunica. Il divulgatore non è uno che riferisce asetticamente i fatti di scienza: piuttosto, li racconta, o meglio li narra, possibilmente facendo leva sugli aspetti emozionali del pubblico per rendere il messaggio più efficace e stimolante. Ecco allora che la capacità di giocare con la scienza può diventare un’arma molto potente in mano al divulgatore, e un motivo di piacere per il destinatario della comunicazione.

E chi meglio dei bambini può recepire un messaggio scientifico se viene proposto in forma giocosa? Rosa Maria Mistretta, nel suo blog La scuola del sapere ci propone il suo libro “Il sole e la sua famiglia”: un testo illustrato per bambini, ma “utile anche per i grandi”, da leggere e disegnare, che introduce i piccoli lettori alla scoperta dell’astronomia. Il protagonista Speedy viene da mondi lontani per guidare i suoi piccoli amici all’interno del sistema solare: attraverso semplici giochi i bambini familiarizzano con la grande famiglia del Sole e imparano ad orientarsi tra pianeti, asteroidi e comete.


Sempre restando sul pubblico dei bambini e dei ragazzi, Tania Tanfoglio, dal vivace blog Science for Passion, segnala il “Manuale degli indovinelli” di Vezio Melegari, concentrandosi in particolare sugli indovinelli riguardanti la matematica. Ad esempio, il classico enigma della sfinge (“Qual è l’animale che all’alba cammina con 4 zampe, a mezzogiorno con 2 e alla sera con 3?”) è fatto di numeri. Ci sono poi rompicapi che hanno a che fare con le tabelline, come: “quante volte il 12 è presente nelle tabelline?”, oppure “la tavola delle tabelline è finita o infinita?”, e tanti altri indovinelli, per divertirsi e per scoprire che dei numeri non c’è da aver paura.


Il mitico Marco Fulvio Barozzi, meglio noto come Popinga, contribuisce a questo Carnevale con un originalissimo post dedicato nientemeno che a… Mamma Oca: “una vecchia palmipede che veste alla contadina, con un grembiule variopinto e il cappellaccio in testa, e che da secoli è conosciuta per la sua grande abilità di raccontare favole, filastrocche e nonsense ai bambini”. Popinga ci accompagna in un viaggio attraverso le apparizioni di Mamma Oca nel corso degli ultimi secoli: dalle fiabe di Perrault e le nursery rhymes inglesi fino alle novecentesche citazioni musicali dovute a Maurice Ravel e ai Jethro Tull. Ma… e la scienza che c’entra? C'entra, eccome! Nella raccolta di filastrocche “Mamma Oca e la scienza moderna”, pubblicata da Frederick Winsor nel 1958 con le eleganti illustrazioni di Marian Parry, la simpatica pennuta è presa a pretesto per parlare di temi scientifici con sottile umorismo.

Nel recensire “Come dire” di Stefano Bartezzaghi, il blog Notiziole di mau di Maurizio .mau. Codogno ci fa riflettere sul fatto che “chiunque abbia visto giocare dei bambini sa che il gioco è un'attività serissima”: e questo libro è serio proprio perché gioca con la lingua e con le parole. Non si tratta di un libro di grammatica, ci ammonisce .mau., e d’altra parte il sottotitolo dell’ultimo capitolo è "come fottersene della grammatica e vivere felici"…



Il blog Scienza Express di Daniele Gouthier, fondatore e artefice di questo Carnevale, recensisce un celebre libro dal titolo deliziosamente autoreferenziale: “Qual è il titolo di questo libro?” del poliedrico e geniale Raymond Smullyan.
Come dice Daniele, l’opera di Smullyan è un libro ma al tempo stesso un gioco: “una vera avventura della mente tra barzellette ed enigmi, giochi logici e aforismi, furfanti e cavalieri, Bellini e Cellini, Dracula e...”.
Come in ogni gioco che si rispetti, ogni capitolo è un mondo, con le sue regole e le sue sfide. E, ci assicura Scienza Express, quando siete dentro, volete "provare e riprovare, per essere sicuri che la vostra logica sia alla pari con quella dell'autore. In una parola, volete giocare.”

Ad un gigante come Smullyan mi piace affiancare un altro grande, il "giocoliere" della matematica Martin Gardner. A parlare di Gardner, questo mese, siamo addirittura in due: il sottoscritto, cioè Mr. Palomar, con il libro “Ah! Ci sono! Paradossi stimolanti e divertenti”, e Roberto Zanasi, detto Zar, con il suo blog Gli studenti di oggi parla di “The colossal book of short puzzles”.
Entrambi i testi sono raccolte di articoli scritti da Gardner tra il 1956 e il 1981 per la rubrica "Mathematical Games" dello "Scientific American" (nell'edizione italiana, la rubrica "Giochi matematici" della rivista "Le Scienze").
Il primo libro è una appassionante scorribanda attraverso i paradossi, tra logica, aritmetica, geometria, fisica e statistica. I divertenti disegni che corredano il libro aiutano il lettore a superare le difficoltà insite in alcuni dei concetti esposti.

Se, come scrivo nel mio post, il libro rappresenta un "affascinante universo tascabile", il libro recensito dallo Zar è un universo di grandi dimensioni: come recita il titolo, appunto un "libro colossale", nel quale sono raccolti tutti i quesiti "brevi" di Gardner apparsi sulle pagine dello "Scientific American". Gli enigmi sono stati classificati da Dana Richards rispetto al tipo di matematica necessaria per risolverli, e sono accomunati dal fatto che ciascuno di loro può essere risolto con una qualche osservazione intelligente (anche qui, la cosiddetta esperienza aha!).

La prossima edizione del Carnevale dei Libri di Scienza cadrà nel periodo natalizio. Quale migliore argomento, allora, di quello scelto da Claudio Pasqua che ospiterà il Carnevale nel suo blog Gravità Zero ? Il tema è infatti: “10 libri da regalare per Natale”.
Le vostre recensioni devono pervenire a Gravità Zero entro martedì 20 dicembre.
Trovate il calendario delle edizioni del Carnevale nel sito di Scienza Express.

Credo sia davvero tutto. Mr. Palomar vi saluta, felice di avere per la prima volta ospitato un Carnevale, e vi augura buone letture e buona scrittura sui libri di scienza!

I paradossi del Grande Giocoliere

Come ho talvolta ricordato in questo blog, molti sono gli alti esponenti (ops, ho detto proprio esponenti...) della divulgazione matematica, ma uno è il vero padre di tutti noi: il giocoliere dei numeri, il Maestro, il più grande di tutti.
Sto parlando ovviamente di Martin Gardner, scomparso un anno e mezzo fa all'età di 95 anni, autore di più di 70 libri, e celebre soprattutto per i suoi incantevoli articoli apparsi tra il 1956 e il 1981 nella rubrica "Mathematical Games" dello "Scientific American" ("Giochi matematici" nell'edizione italiana, cioè la rivista "Le Scienze").
Gli inesauribili giochi matematici di Gardner hanno affascinato generazioni di appassionati; e certamente moltissime persone hanno scelto di intraprendere una carriera matematica o scientifica grazie all'influenza dei suoi articoli.

Di Gardner si è detto molto (per la verità non abbastanza, dato che il suo nome non è poi così celebre al grande pubblico): e non mi dilungherò nel tessere le sue lodi, peraltro più che meritate.
La sua grande bravura è stata quella di saper coniugare il senso della bellezza della matematica con il divertimento del gioco.
"La matematica matemagica combina la bellezza della struttura matematica con l'efficacia spettacolare di un trucco da prestigiatore" scrisse in uno dei suoi primi libri (coniando tra l'altro il fortunato termine "matemagica").

Come scrive Maurizio Codogno in un suo post:
"Gardner non aveva una formazione matematica, e si può dire che si è fatto le ossa negli anni, affinando sempre più le sue conoscenze; ma soprattutto il suo grande contributo fu lo sdoganamento della matematica ricreativa, e la possibilità per molti matematici di professione di pubblicare i propri risultati non troppo accademici, rendendoli contemporaneamente noti al pubblico."

I numerosissimi articoli che Gardner scrisse per lo "Scientific American" sono raccolti, in edizione italiana, nei volumi di "Enigmi e giochi matematici": un testo fondamentale che ogni appassionato di matematica dovrebbe possedere.

Avevo quasi deciso di dedicare un post a questa celebre e deliziosa raccolta, e mi stavo già cimentando nella recensione, quando dallo scaffale della mia libreria un altro libretto di Gardner ha fatto capolino. Mi riferisco a "Ah! Ci sono! Paradossi stimolanti e divertenti" (nell'edizione originale "Aha! Gotcha. Paradoxes to puzzle and delight"): anche in questo caso una selezione di articoli usciti su "Scientific American".
Ebbene, alla fine ho scelto proprio questo libro, meno noto degli "Enigmi e giochi matematici", ma ricco della geniale brillantezza che contraddistingue ogni creazione di Gardner.
L'edizione che posseggo è quella della collana "Sfide matematiche" di RBA, uscita tre anni fa (pare che la prima edizione italiana, Zanichelli 1981, sia ormai introvabile)
Il libro è una piacevolissima carrellata di paradossi di ogni tipo, reali e apparenti che siano.
L'argomento è particolarmente accattivante, tanto è vero che sulla scia del libro di Gardner sono apparsi, in anni più recenti, altri testi abbastanza simili, di altri autori.

Nell'introduzione Gardner parafrasa la frase di Desdemona nell'Otello di Shakespeare ("Questi sono vecchi e amati paradossi per far ridere gli sciocchi in birreria") trasformandola in "Questi sono vecchi e amati paradossi per farci ridere all'ora di pranzo", e ci accompagna in un viaggio che inizia dai celebri e antichissimi paradossi logici, passa per l'aritmetica, la geometria, la probabilità e la statistica, per concludersi con gli strani paradossi che hanno a che fare con il tempo e con il moto.
Uno dei pregi del libro è rappresentato da un'infinità di disegnini divertenti che aiutano la comprensione del testo, a tratti non immediata data la difficoltà intrinseca di certe sottili tematiche.

Il lettore potrà quindi spaziare dal paradosso del mentitore a quello del barbiere, dai sogni di Alice e del Re Rosso ai numeri interessanti e non interessanti, dalle bizzarrie dell'hotel infinito alle magie delle matrici, dalla scala impossibile di Penrose alle curve frattali e ai nastri di Moebius, dal principio di indifferenza alla scommessa di Pascal, dal mondo piccolo alle cifre di pi greco, dai paradossi di Zenone alle macchine del tempo, fino ad arrivare alla relatività e a disquisizioni filosofiche sul caso e sul libero arbitrio.
Un affascinante universo tascabile, com'è ogni libro di Gardner.

Meraviglie possibili e impossibili con il cubo Soma

Nei giorni scorsi ho passato qualche giorno a Torino, città che in questo periodo offre numerosi spunti culturali di altissimo livello, in gran parte legati alla celebrazione dei 150 anni dell'unità d'Italia: proposte che uniscono l'antico con il moderno, in una meravigliosa dimostrazione di eccellenza italiana.
Nel corso delle mie esplorazioni torinesi, ho visitato la magnifica reggia della Venaria Reale, nella quale trova posto una specie di tempio del gioco al quale è stato dato il nome di "Fantacasino". Qui ho trovato, con mia grande sorpresa, un paio di rompicapi matematici realizzati in legno e offerti al divertimento dei visitatori: le torri di Hanoi (delle quali ho parlato in un mio precedente post) e il celebre cubo Soma.
Il cubo Soma fu inventato da un genio dei rompicapi matematici: il danese Piet Hein.
La vita di Hein sembra uscita da un romanzo: nacque a Copenhagen nel 1905 da una famiglia che tra i suoi antenati vanta un altro Piet Hein, l'eroe nazionale olandese che si distinse all'inizio del Seicento come comandante navale nella guerra degli Ottant'Anni.
Nel 1940, quando la Danimarca fu invasa dai nazisti, il nostro Piet Hein si arruolò come partigiano, e combattè a capo di un gruppo antinazista fino alla fine della guerra.
Si sposò quattro volte, ed ebbe cinque figli.
Nel corso della sua lunga vita, Hein fu matematico, fisico, ingegnere, progettista e inventore, ma anche divulgatore scientifico, poeta e scrittore.
Durante la sua milizia nella resistenza danese, inventò un particolare tipo di poesia breve, chiamato "gruk" o "grook", e pubblicò i suoi primi componimenti antinazisti sul quotidiano danese "Politiken", con lo pseudonimo "Kumbel Kumbel".
Un esempio di gruk? Eccolo:

La via della saggezza

La via della saggezza?
E' evidente
e molto semplice:
sbaglia,
sbaglia
e sbaglia ancora,
ma sempre meno,
meno
e meno.

Come matematico, studiò a fondo una particolare curva, chiamata "superellisse": una sorta di via di mezzo tra un'ellisse e un rettangolo. La superellisse è divenuta un marchio di fabbrica dell'architettura scandinava moderna, ma è stata utilizzata anche in molti oggetti di design e nella progettazione dello stadio Olimpico di Città del Messico.

A noi Piet Hein interessa soprattutto come inventore di giochi e rompicapi matematici, tra i più belli che siano mai stati creati. Il gioco dell'Hex, profondamente studiato dalla "beautiful mind" di John Nash e descritto dal grande Martin Gardner, è suo. Sono suoi anche giochi noti come TacTix, Nimbi, Tangloids, Morra, Tower, Polytaire, Qrazy Qube, Pyramystery.

L'idea del cubo Soma, probabilmente il suo gioco più celebre, gli venne nel 1936, mentre seguiva una lezione di fisica quantistica di Werner Heisenberg. Il grande fisico stava descrivendo uno spazio suddiviso in celle cubiche, e il giovane Hein si trovò a riflettere su quali forme possano essere costruite combinando insieme cubetti uniti tra di loro per una faccia.
Hein concentrò il proprio interesse sulle forme "irregolari", cioè sulle combinazioni di cubetti che presentano delle concavità. Ad esempio, con un solo cubetto o con due cubetti, non è possibile creare forme irregolari; con tre cubetti è possibile creare una sola forma irregolare, illustrata nella figura seguente:



E con quattro cubetti? Hein osservò che potevano essere costruite sei figure irregolari:



Ora, il bello deve ancora venire. Hein provò a contare i cubetti utilizzati per costruire queste sette figure: 3 per l'unica figura da 3 cubetti, 4x6=24 per le 6 figure da 4 cubetti, in tutto 27 cubetti.
Ma... 27 è il cubo di 3! La domanda nacque spontanea nella mente di Hein: non è che combinando opportunamente queste sette figure si possa ottenere un bel cubo 3x3x3?

Hein si mise al lavoro e trovò subito la risposta: sì, è possibile!
La soluzione non è unica: nel 1961 i matematici J. H. Conway e M. J. T. Guy hanno dimostrato che escludendo simmetrie e rotazioni il problema ammette 240 diverse soluzioni.
Certo, trovare il modo giusto di combinare i sette pezzi del cubo Soma non è per tutti facile, e la sfida è un rompicapo appassionante.




Con i sette pezzi base, oltre al cubo 3x3x3 che rappresenta la prima sfida per chi voglia cimentarsi con il rompicapo, è possibile costruire innumerevoli altre forme curiose. Nella figura a lato è illustrata una ipotetica "stanza del matematico", nella quale il tavolo, le sedie e il divano sono tutte figure che si possono ottenere a partire dai sette pezzi base.

Naturalmente non tutte le figure costituite da 27 cubetti possono essere costruite con i sette pezzi base: un po' come accade con i bidimensionali polimini, anche le costruzioni Soma si prestano a interessanti dimostrazioni di impossibilità.



Martin Gardner, nel suo classico "Enigmi e giochi matematici", mostra come le due forme illustrate nella figura seguente non possano essere costruite con i pezzi del cubo Soma.

Della seconda forma, Gardner propone anche una interessante dimostrazione di impossibilità.

Il cubo Soma assomiglia un po' al tangram e un po' ai rompicapi con i polimini (dei quali ho già accennato in questo blog in questo e in questo articolo), ma ha in più il pregio di essere tridimensionale.
Perché Hein scelse questo nome? "Soma" è il nome dell'immaginaria droga descritta da Aldous Huxley nel suo romanzo "Brave New World" ("Il mondo nuovo").
Concludo con un passo da questo romanzo:

...non un momento di riposo... non un momento per sedersi e pensare - ché se per qualche sfortunato caso una tal fessura di tempo si apre nella solida sostanza delle loro distrazioni, c'è sempre il Soma, il delizioso Soma...

Il gioco della fine del mondo

Hanoi è la capitale dello stato di Vietnam dal 1976, anno della riunificazione tra Vietnam del Nord e Vietnam del Sud. Lo scorso 10 ottobre (un giorno matematicamente molto particolare secondo il calendario gregoriano: 10/10/10) gli abitanti di Hanoi e tutti i vietnamiti hanno festeggiato il millesimo anniversario della costruzione della città, voluta dall'imperatore Lý Thái Tổ che la chiamò Thăng Long, cioè "dragone che si alza in volo".
La città di Hanoi è ben nota, oltre che ai geografi, agli storici e ai viaggiatori, anche agli informatici. Perché mai? Semplicemente perché nel 1883 il matematico francese Edouard Lucas, per attribuire un tocco di esotismo ad un rompicapo di sua invenzione, si inventò una leggenda collegata all'antica città di Hanoi. Secondo la leggenda di Lucas, in un tempio di Hanoi alcuni monaci sono intenti, da tempo immemore, a poggiare dischi d'oro su colonne di diamante, consapevoli che nel momento in cui avranno terminato il loro compito il mondo avrà fine.
Più precisamente, ci sono 3 colonne e 64 dischi di dimensioni diverse. All'inizio dei tempi i dischi erano incolonnati sulla prima colonna in ordine di grandezza, cioè in modo tale che ogni disco poggiasse su un disco più grande (i dischi formavano quindi un cono). Da allora i monaci hanno cominciato a spostare dischi, uno alla volta, rispettando la regola fondamentale secondo la quale è vietato poggiare un disco su un disco più piccolo, e con l'obiettivo supremo di spostare tutti i dischi sulla terza colonna.
Come si risolve il rompicapo? La soluzione che si impara nei corsi di programmazione è un tipico esempio di algoritmo ricorsivo, e anche un eccellente esempio di ragionamento per induzione.
Supponiamo di essere in grado di risolvere il gioco per n dischi, e cimentiamoci nella versione con n+1 dischi. Sulla prima colonna avremo quindi n+1 dischi, che dobbiamo spostare sulla terza colonna. Sapendo risolvere il rompicapo con n dischi, non avremo difficoltà a spostare i primi n dischi dalla prima alla seconda colonna; potremo agevolmente spostare il disco (n+1)-esimo dalla prima alla terza colonna, e infine ripeteremo il procedimento degli n dischi spostando tutti i dischi dalla seconda alla terza colonna.
Siccome il gioco è banalmente risolvibile se n=1 (si tratta semplicemente di spostare un disco dalla prima alla terza colonna), per induzione possiamo concludere che è possibile risolvere il rompicapo per qualsiasi numero n.
Si può dimostrare che il numero minimo di mosse necessarie per risolvere il rompicapo con n dischi è pari a 2ⁿ-1. Se i dischi fossero soltanto 3, basterebbero quindi 2³ - 1 = 7 mosse; con 64 dischi, il numero diventa enorme: i monaci dovrebbero effettuare più di 18 miliardi di miliardi di spostamenti!
Possiamo quindi stare tranquilli: se immaginiamo che per spostare un disco i monaci impieghino un secondo, il mondo finirà tra circa 584 miliardi di anni, un tempo ben superiore a quello necessario a trasformare il Sole nella gigante rossa che inghiottirà anche il nostro pianeta.

Il numero di Dio

Immaginate di dover raggiungere un luogo della vostra città dove non siete mai stati, assolutamente entro una certa ora. Potete aiutarvi con il navigatore, o affidarvi alla vostra conoscenza della città, o ancora chiedere indicazioni a qualche passante. In ogni caso non vi basta semplicemente arrivare, ma avete bisogno di trovare un tragitto ottimale, possibilmente il più breve possibile.
Esistono infatti moltissimi, addirittura infiniti percorsi per arrivare in un certo luogo, e uno di essi è quello che permette di giungere a destinazione nel minor tempo possibile.
Se invece di raggiungere un luogo dovete cimentarvi con un rompicapo, ad esempio il celeberrimo cubo magico di Rubik, o il gioco del quindici, di cui ho parlato in un mio precedente post, la situazione non è molto diversa. Potreste accontentarvi di risolvere “semplicemente” il gioco, cioè portare il cubo, probabilmente disordinato, nella configurazione ordinata con tutte le facce colorate di un solo colore, oppure spostare le tessere del gioco del quindici in modo che i numeri siano tutti in sequenza. Ma se siete giocatori provetti, questo non vi basta: volete trovare la via più breve, che conduce sempre alla disposizione finale ordinata nel minor numero di mosse. Se la trovaste davvero, probabilmente sareste talmente orgogliosi di voi stessi da sentirvi “come un dio”: e ne avreste ben donde! Non a caso un algoritmo, cioè un procedimento ben definito, che consenta di risolvere un rompicapo come il cubo di Rubik o il gioco del quindici con il numero minimo possibile di mosse e riducendo al minimo la quantità di memoria utilizzata viene chiamato “algoritmo di Dio”.
Se il riferimento all’essere supremo può sembrarvi esagerato, sappiate che escogitare una procedura di questo tipo, in genere, non è compito facile. La clausola sull'utilizzo della memoria è a questo proposito importante: riferendoci per esempio al cubo di Rubik, sarebbe facile, in linea di principio, pensare ad una enorme tabella precompilata in cui ad ogni configurazione possibile del cubo viene fatta corrispondere la sequenza ottimale per risolvere il rompicapo. Ma si dà il caso che il giocattolo di Rubik può assumere 43 miliardi di miliardi di possibili configurazioni: produrre e utilizzare una simile tabellona sarebbe poco maneggevole perfino per i computer più potenti.
Albert Einstein disse "Quando la soluzione è semplice, Dio sta rispondendo". Potremmo anche immaginare Dio come un risparmiatore, che predilige le vie che consentono di sprecare meno risorse possibili: non solo il tempo, ma anche lo spazio, cioè la memoria.
Un degno algoritmo di Dio per il cubo di Rubik, quindi, dovrebbe essere sempre capace di determinare la sequenza di mosse più breve per riordinare il diabolico marchingegno, senza ricorrere a giganteschi indici. La ricerca di una procedura di questo tipo è strettamente collegata ad una domanda che molti di noi, giocherellando con il famoso rompicapo, ci siamo posti: quante mosse sono necessarie per risolvere questo puzzle? Equivalentemente: qual è il numero minimo di mosse con cui possiamo certamente risolvere il cubo partendo da una configurazione qualsiasi? Sono certo che avrete già immaginato come i matematici hanno chiamato questo numero. Proprio così: il numero di Dio.
Già nel 1981, quando il cubo magico era all'apice del suo successo in tutto il mondo, il matematico Morwen Thistlethwaite dimostrò che 52 mosse sono sempre sufficienti per risolvere il cubo, partendo da qualsiasi configurazione. Questo significava che il numero di Dio non poteva essere maggiore di 52: ma probabilmente era più basso. Dal 1981 in poi, molti altri matematici cercarono di abbassare quel numero, e ci riuscirono. Nel 1990 si era già arrivati a 42, nel 1992 si scese a 37, e nel 1995 si arrivò a quota 29.
In questo stesso anno Michael Reid si cimentò nel compito opposto: trovare un limite inferiore al numero di Dio, cioè un numero di mosse sotto il quale non si può andare per configurazioni particolarmente "rognose". Reid fissò questo limite a 20.
Il numero di Dio era quindi compreso tra 20 e 29. Il limite superiore non scese per dieci anni, ma nel 2005 scoprì che 28 mosse sono sempre sufficienti. Tra il 2006 e il 2008 il gioco si fece duro, e l'asticella si abbassò per cinque volte, toccando quota 22 nell'agosto 2008.
La ricerca del numero di Dio era ormai giunta alla sua fase decisiva. La risposta definitiva arrivò esattamente un anno fa, nel luglio 2010, quando Morley Davidson, Tomas Rokicki, Herbert Kociemba e John Dethridge dimostrarono che bastano sempre 20 mosse per riordinare i colori del cubo.
Il numero di Dio è quindi 20. Ma come hanno fatto questi matematici a determinarlo? Utilizzando calcolatori potentissimi e software molto sofisticati che hanno esplorato in modo intelligente l'enorme numero di possibili configurazioni. Gli studi di Davidson e colleghi hanno determinato che su un totale di 43 miliardi di miliardi di possibili configurazioni, circa 300 milioni necessitano di esattamente 20 mosse, mentre la stragrande maggioranza delle configurazioni possono essere risolte in un numero di mosse compreso tra 15 e 19.
Per chi volesse saperne di più:
http://www.cube20.org/
http://www.bbc.co.uk/news/technology-10929159

L'evoluzione artificiale e i doppietti di Lewis Carroll

Questo post è un post... scriptum al post intitolato "Il gioco dell'evoluzione artificiale". In quell'articolo ho descritto come giochi di parole le operazioni di mutazione e di crossing-over, fondamentali negli algoritmi genetici.
Non potevo però tacere il fatto che il gioco delle "parole mutanti" vanta un padre particolarmente autorevole: niente meno che Lewis Carroll, scrittore-matematico amatissimo dai matematici, autore di "Alice nel paese delle meraviglie" e di "Attraverso lo specchio".

In un post del 2010, Gianluigi Filippelli ha descritto quello che Carroll aveva chiamato il gioco dei "doppietti": da una parola data si deve passare a un'altra parola prefissata (con lo stesso numero di lettere), sostituendo una lettera alla volta e utilizzando sempre parole di senso compiuto.
Secondo quanto racconta Martin Gardner ("Enigmi e giochi matematici - volume 3", Sansoni Editore), Carroll inventò questo gioco nel Natale del 1877, per due bambine che "non avevano nulla da fare".
Nel 1879 la rivista "Vanity Fair" ospitò sulle sue pagine diversi doppietti ideati da Carroll. Il gioco divenne molto popolare soprattutto grazie alle gare a premi promosse da quella stessa testata.
Il gioco venne successivamente ripreso da molti enigmisti. Dmitri Borgmann, nel suo libro "Language on vacation" del 1965, osservò che il doppietto ideale conduce da una parola all'altra attraverso un numero di passi uguale alla lunghezza delle due parole, e le due parole di partenza e di arrivo non hanno in comune alcuna lettera uguale nella stessa posizione. Ad esempio:
MARE --> MALE --> MELE --> MELA --> VELA

Già l'autore di Alice doveva avere intuito il forte legame tra questo gioco e la teoria di Darwin. Infatti, ad esempio, uno degli enigmi proposti da Carroll consisteva nel far evolvere l'uomo (MAN) dalla scimmia (APE). La soluzione del gioco è in questo caso:
APE --> ARE --> ERE --> ERR --> EAR --> MAR --> MAN

Se volete qualcosa di simile in lingua italiana, sono certamente in grado di accontentarvi, ma al prezzo di discostarmi (solo leggermente) dalla lezione di Darwin:
CANE --> RANE --> RAME --> RAMO --> REMO --> TEMO --> TOMO --> UOMO

Il genetista inglese John Maynard Smith, famoso per avere applicato la teoria dei giochi (e sottolineo, giochi) all'evoluzione, sottolineò in un suo libro del 1962 come il gioco dei doppietti riflettesse bene i meccanismi attraverso i quali una specie si evolve in un'altra. Immaginando il genoma di una specie come un'unica lunghissima parola, nella quale le basi azotate del DNA recitano la parte delle lettere, le mutazioni, faceva notare Smith, assomigliano sorprendentemente ai doppietti di Carroll.
D'altra parte questa somiglianza è esattamente l'idea alla base degli algoritmi genetici, di cui ho parlato nel mio post "Il gioco dell'evoluzione artificiale".
Il saggio di Smith uscì proprio negli anni in cui queste tecniche evolutive cominciavano ad essere concepite dai ricercatori informatici.
Mi pare che questa storia sia un bell'esempio di come letteratura, biologia e matematica si possano incrociare (ecco, di nuovo il crossing-over!) dando origine a bellissimi frutti. Sempre nel segno del gioco.

La matematica di Ummagumma (Parte 2)

Quale altra meraviglia matematica emerge dalla copertina di "Ummagumma" dei Pink Floyd?
Osserviamo ancora una volta l'immagine del disco (basta scendere un attimo alla prima parte di questo "multi-post"): al primo "livello" di ricorsività, cioè nella prima delle matrioske, troviamo in primo piano, seduto, il chitarrista David Gilmour; dietro di lui riconosciamo il bassista Roger Waters, seduto appena fuori della soglia di casa; il batterista Nick Mason è in piedi nel prato; e sullo sfondo, nella posizione della candela, scorgiamo il tastierista Rick Wright.
Per spostare la nostra attenzione al secondo dei livelli di ricorsività dobbiamo osservare la fotografia appesa al muro; balza subito all'occhio che qui le posizioni occupate dai musicisti e le pose da loro assunte sono le stesse del primo livello: anche qui uno dei membri della band è seduto sulla sedia in primo piano, un altro è seduto per terra fuori della porta, un terzo membro è in piedi nel prato, e l'ultimo sta a testa in giù sullo sfondo.
Ma si nota altrettanto subito che gli stessi posti non sono occupati dalle stesse persone: la successione Gilmour-Waters-Mason-Wright del primo livello è infatti diventata ora Waters-Mason-Wright-Gilmour.
Detto diversamente, il chitarrista, che nella prima scena appariva in primo piano, ora si trova laggiù in fondo a fare yoga, mentre gli altri tre sono avanzati ciascuno di un posto: in particolare il paroliere-bassista si trova ora davanti a tutti.
Spingendoci nei livelli più profondi del ciclo ricorsivo, cosa che ci richiede uno sforzo visivo non indifferente per scavare nell'immagine, la permutazione si ripete altre due volte con la stessa logica. Al terzo livello la successione diventa, ormai prevedibilmente, Mason-Wright-Gilmour-Waters, mentre all'ultimo livello è Wright-Gilmour-Waters-Mason: è a questo punto che la copertina di "A saucerful of secrets" appesa al muro interrompe il loop.


La tabella precedente illustra la situazione che emerge dalla copertina.
I livelli della ricorsione sono associati alle righe della tabella, e le posizioni (o pose) corrispondono alle sue colonne; nelle caselle intermedie viene indicato quale musicista occupa una certa posizione ad un certo livello.
Non è difficile notare che su ogni riga e su ogni colonna della tabella i quattro componenti del gruppo appaiono ciascuno esattamente una volta.
Ciò equivale a dire che ad ogni livello sono presenti i quattro musicisti, ciascuno dei quali associato ad una delle posizioni standard, e ognuno degli accoppiamenti musicista-posizione è unico, cioè non compare mai in più di un livello.
Una struttura matematica di questo tipo, in cui un certo numero di oggetti (in questo caso i quattro musicisti) sono associati ad altrettanti oggetti (le posizioni) in altrettanti modi tra loro completamente diversi (i livelli) viene chiamata "quadrato latino".


Chiaramente, se a realizzare "Ummagumma" fossero stati, anziché i Pink Floyd, gli Emerson Lake & Palmer, che erano in tre, il gioco si sarebbe dovuto sviluppare su tre livelli e tre posizioni, e non su quattro; analogamente, i Genesis della formazione classica avrebbero dovuto spaziare su cinque livelli e cinque posizioni.
In altre parole, questi gruppi avrebbero creato quadrati latini con lati di tre o cinque caselle, e non di quattro.

A scanso di equivoci, un quadrato latino non ha necessariamente a che fare con la ricorsività: accidentalmente nella copertina di "Ummagumma" intervengono entrambi questi concetti, intrecciati tra di loro (e questa straordinaria coincidenza mi ha ispirato questo doppio post), ma solitamente i quadrati latini non c'entrano nulla con strutture ricorsive.

Un semplice quadrato latino estraneo a questioni di ricorsività lo possiamo realizzare in casa con un mazzo di carte da gioco. Immaginiamo di estrarre i quattro re, le quattro regine, i quattro fanti e i quattro assi, e di voler disporre queste 16 carte in un quadrato 4x4, in modo che su ogni riga e su ogni colonna si trovino tutti i quattro diversi tipi di carte, senza ripetizioni. Vogliamo insomma che sulla prima riga ci siano un re, una regina, un fante e un asso, non importa in che ordine, e lo stesso deve accadere su ciascuna delle altre righe e su ciascuna delle colonne.
Una configurazione che soddisfi questi vincoli (come quella illustrata nella figura a lato) è ovviamente un quadrato latino: in questo caso, infatti, al posto dei quattro Pink Floyd abbiamo le quattro figure (re, regina, fante, asso), mentre le quattro colonne del quadrato giocano il ruolo delle quattro pose della copertina di "Ummagumma".

Il modo più semplice e comune di compilare un quadrato latino di lato N è quello di disporre nella griglia NxN i numeri da 1 a N, facendo attenzione che in ogni riga e in ogni colonna non si abbiano ripetizioni.
Chi si diletta a giocare a sudoku si sarà già reso conto che quel rompicapo altro non è che la ricerca di un quadrato latino 9x9: l'unica complicazione consiste nel fatto che, oltre alle righe e alle colonne, occorre considerare anche le sottogriglie interne 3x3.

Naturalmente nessuno ci impedisce di usare, al posto dei numeri, altri simboli: ad esempio colori (come nel quadrato latino qui a lato), lettere o quello che volete voi.

Ma torniamo al nostro quadrato di carte di gioco, complicando un po' le cose.
Ora non vogliamo soltanto che su ogni riga e su ogni colonna si trovino tutti i quattro tipi di carte, senza ripetizioni, ma anche che su ogni riga e su ogni colonna si trovino tutti i quattro semi, anche loro senza ripetizioni.
Quello che otterremo sarà una specie di sovrapposizione tra due quadrati latini: i matematici la chiamano "quadrato greco-latino".
Come comporre una simile struttura di carte da gioco? Semplice, anzi ce l'abbiamo già! Se andate a controllare, infatti, il quadrato latino che abbiamo creato poco fa con le figure delle carte da gioco, è anche un quadrato greco-latino, se in esso teniamo in considerazione anche i semi delle carte.

Perché queste strutture matematiche vengono chiamate "quadrati latini" e "quadrati greco-latini"? Leonhard Euler, il grande matematico svizzero del Settecento, noto in Italia come Eulero, fu il primo a usare questi reticoli, e introdusse la convenzione di usare, per i primi, lettere dell'alfabeto latino (nello stesso ruolo delle figure del nostro mazzo di carte), e, per i secondi, coppie formate da lettere latine e lettere greche (nel ruolo delle figure e dei semi).
In un post futuro parlerò delle applicazioni dei quadrati latini e greco-latini, soprattutto nella progettazione di esperimenti in biologia, medicina e sociologia, e di come i matematici e gli informatici si siano cimentati a lungo nel problema di ricercare quadrati latini e greco-latini di dimensioni sempre più grandi.

Se la copertina di "Ummagumma", uscita nel 1969, incasellava i quattro Pink Floyd in un sorprendente quadrato latino 4x4, nove anni dopo lo scrittore francese Georges Perec (nella foto sotto) scrisse addirittura un intero romanzo, il celebre "La vita, istruzioni per l'uso", basandosi su un quadrato greco-latino 10x10 (Eulero aveva ipotizzato che non esistessero quadrati greco-latini di tale dimensione, ma si era sbagliato: nel 1959 i matematici Bose, Parker e Shrikhande ne scoprirono uno).
Il blog Popinga ha parlato di questo argomento in un suo post di circa due anni fa (mi scuso quindi se ripeterò qui alcune delle cose scritte in quel post).

Il libro di Perec descrive un condominio parigino costituito da 99 stanze disposte su dieci piani. Ogni capitolo è ambientato in una stanza, ragione per cui il romanzo è composto da 99 capitoli.
Cosa c'entra il quadrato greco-latino 10x10 scoperto nel 1959? E' presto detto.
Perec compilò 42 elenchi (esercizio assai di moda ultimamente), ciascuno formato da dieci elementi che potevano essere utilizzati come "vincoli narrativi". Ad esempio, compose un elenco di citazioni letterarie, uno di località geografiche, uno di animali, e così via.
Divise quindi gli elenchi in 21 coppie, e utilizzò 21 volte il quadrato greco-latino 10x10, riempendone ogni volta le caselle con coppie di elementi presi dai due elenchi, esattamente come noi avevamo disposto, poco fa, coppie di figure e semi in un quadrato greco-latino 4x4.
Ovviamente ogni casella del quadrato 10x10 corrispondeva ad una delle stanze, e quindi a uno dei capitoli del romanzo. Il quadrato greco-latino ebbe quindi l'effetto di far corrispondere ad ogni stanza 21 coppie di elementi presi dai 42 elenchi. Questi elementi furono utilizati da Perec come "vincoli narrativi": ad esempio, una delle coppie associate ad una stanza poteva prescrivere di menzionare, nella narrazione del capitolo corrispondente, una certa citazione letteraria e una particolare località geografica.

Il gioco del quindici

Non è sorprendente che molti esperti di scacchi siano passati alla storia non tanto per aver lasciato importanti contributi sul gioco dei pezzi bianchi e neri, ma per avere inventato enigmi matematici o proposto tecniche algoritmiche per risolvere difficili problemi.
Abbiamo già incontrato, qualche post fa, il caso di Johann Berger, scacchista austriaco con l'hobby degli algoritmi per stilare i calendari dei tornei.
Un altro celebre scacchista fu Samuel Loyd, americano, anche lui vissuto a cavallo tra Ottocento e Novecento.


Il nome di Loyd è ben noto agli appassionati di scacchi come compositore di problemi, ma i suoi meriti vanno ben oltre le frontiere di quel gioco. Molti, tra i quali Martin Gardner, lo hanno considerato "il più grande enigmista d'America": pare che abbia inventato migliaia di giochi ed enigmi, alcuni dei quali molto sofisticati dal punto di vista matematico. Una delle sue intuizioni più geniali è un rompicapo nel quale tutti noi ci siamo prima o poi cimentati: il cosiddetto "gioco del quindici".
Lo scopo del gioco è ben noto: in una specie di scatola quadrata di plastica dobbiamo mettere in ordine quindici tesserine quadrate, numerate da 1 a 15; le tesserine possono scorrere solo in orizzontale e in verticale, ma nello spostarle dobbiamo fare i conti con il fatto che esiste un solo spazio vuoto!
Si parte solitamente da una situazione casuale, più o meno caotica, e si deve arrivare nella configurazione illustrata nella figura in alto.

Sam Loyd propose il suo gioco nel 1878. Si racconta che il successo del rompicapo fu così travolgente, che i francesi arrivarono a descriverlo come un flagello peggiore dell'alcool e del tabacco, in Germania diventò molto popolare tra i deputati del Reichstag, mentre in America venne proibito il suo utilizzo negli uffici durante le ore di lavoro!

Su disposizione di Loyd, la confezione del gioco che venne messa in commercio non aveva le tessere disposte in una configurazione caotica: semplicemente, rispetto alla situazione finale ordinata, aveva le due caselle del 14 e del 15 scambiate, come illustrato nella figura qui accanto.
Loyd offrì un premio di ben 1000 dollari al primo che avesse trovato una soluzione.
Visto che si trattava soltanto di due caselle scambiate tra loro, sulle prime si pensò che l'enigma fosse di facile risoluzione: tuttavia, i mesi e gli anni passarono senza che nessuno si facesse avanti a reclamare il premio.


Ovviamente, Loyd aveva fatto bene i suoi conti: il problema era impossibile!
Perché?
Per capire l'arcano, almeno a grandi linee, occorre considerare, in ogni configurazione del gioco dalla quale si parte per cercare di arrivare all'ordinamento totale, il numero di coppie di caselle che non si trovano nella situazione "naturale". Ad esempio, la disposizione iniziale proposta da Loyd presenta una sola coppia di caselle non ordinate tra di loro: quella del 14 e quella del 15, che sono appunto invertite l'una rispetto all'altra.


Anche la configurazione illustrata nella figura qui accanto presenta un numero di inversioni pari a 1: infatti soltanto la casella del 2 e quella dell'1 sono scambiate tra di loro.




Nella successiva figura, le inversioni sono in tutto 4: per verificarlo, osservate una per una tutte le caselle, e per ognuna controllate con quali altre caselle si verifica un "cattivo" ordinamento reciproco.


Non è difficile dimostrare (e infatti i matematici lo hanno fatto) che se il numero di inversioni di una certa disposizione iniziale è pari, allora si può risolvere il rompicapo, portando tutte le caselle nella loro situazione completamente ordinata, ma se è dispari ciò non è possibile.
Ecco perché Loyd sapeva di non correre alcun rischio, e mise in palio una somma che nessuno poté mai riscuotere!

Ancora sui polimini

La storiella di Mr. Palomar e Mr. Wilson che giocano con i pezzi del Tetris su una scacchiera generalmente riservata ad altri giochi, come gli scacchi, merita certo alcuni approfondimenti.
Innanzitutto, i polimini di Golomb: uno dei primi tentativi del matematico americano deve essere stato certamente quello di trovare una formula che permettesse di calcolare quanti polimini possono essere costruiti con un certo numero di quadrati.
Non mi risulta che sia nota una simile formula: la funzione, come si può vedere nella figura seguente, cresce molto rapidamente (già con 12 quadrati esistono ben 63600 polimini possibili).


Il problema di coprire una scacchiera 8x8 con i 12 pentamini esistenti, lasciando vuote quattro caselle, è molto vecchio: Martin Gardner, nei suoi "Enigmi e giochi matematici" raccolti dallo "Scientific American", ci racconta che una soluzione a questo rompicapo fu pubblicata nel 1907 da Henry Dudeney nel suo libro "The Canterbury puzzles", che proponeva enigmi e giochi ispirati ai personaggi dei "Canterbury Tales" di Geoffrey Chaucer.
Molte altre soluzioni vennero proposte successivamente. E' stato dimostrato che se le quattro caselle sparse vengono poste vicine, a formare un tetramino quadrato, esistono soluzioni per qualsiasi collocazione di questo tetramino. Ad esempio, se il tetramino viene posto al centro della scacchiera, come nella soluzione proposta da Mr. Wilson, esistono 65 soluzioni diverse, che vennero trovate nel 1958 dall'informatico Dana Scott, premio Turing nel 1976. Se invece si accetta che le quattro caselle sparse possano stare ovunque, le soluzioni possibili del rompicapo di Dudeney diventano molte migliaia.
Il gioco competitivo nel quale ognuno dei due giocatori dispone polimini sulla scacchiera, cercando di far sì che l'avversario si trovi a un certo punto senza spazio per porre propri pezzi, fu inventato da Golomb nel 1954. Golomb calcolò che, giocando con i pentamini, una partita può durare da 5 a 12 mosse: in altri termini, 5 è il numero minimo di pentamini diversi che devono essere sistemati sulla scacchiera in modo che non ci sia più spazio per disporre altri pentamini diversi; d'altra parte, dopo aver collocato 12 pentamini in qualsiasi maniera, sicuramente resterebbero soltanto le quattro famose caselle in sovrappiù, e non ci sarebbe spazio per un altro pentamino (e comunque non esisterebbe un tredicesimo tipo di pentamino).
Golomb suggerì anche un paio di principi strategici utili per aumentare le probabilità di vittoria:
1. "cercate di fare mosse che lascino spazio per un numero pari di pezzi";
2. "se non riuscite ad analizzare bene la situazione, fate qualcosa per complicarla ancora di più, in modo che l'avversario faccia ancora più fatica a fare la sua analisi".
Giocando con i tetramini, invece, non ho idea di come potrebbe cambiare la natura del gioco: sarebbe interessante provare!
Il gioco nel quale i due giocatori collocano tetramini sulla scacchiera rispettando la regola delle carte geografiche politiche, nelle quali regioni confinanti devono avere colori diversi, è di mia invenzione. In questo caso, ovviamente si deve disporre di più pezzi per ogni tipo di tetramino: altrimenti non si potrebbero mettere sulla scacchiera pezzi con lo stesso colore. D'altra parte, utilizzando la convenzione dei matematici e non quella del Tetris, con cinque tetramini si coprono soltanto 20 caselle: appare quindi evidente che il gioco necessita di più pezzi per ogni tipo (o colore). Con l'accorgimento di Mr. Wilson, peraltro, due dei cinque tipi di tetramini hanno una doppia colorazione, a seconda della faccia che viene scelta per la collocazione sulla scacchiera.
Anche per questo gioco, non ho prove sperimentali della giocabilità: potrebbe anche rivelarsi un gioco poco divertente o addirittura non giocabile. Anche qui non c'è che da provare a giocare: se qualche lettore volesse galileianamente sperimentare la cosa, sarei curiosissimo di conoscere i risultati.

Un'ultima nota: il nostro Golomb, oltre a fondare la matematica dei polimini, inventò anche un'altra diavoleria matematica: il "regolo" che porta il suo nome. Immaginate di avere un regolo, sul quale sono indicate le posizioni corrispondenti ai numeri interi: 1, 2, 3, e così via. Ora vogliamo tracciare alcune tacche su di esso, in corrispondenza di alcune delle posizioni intere indicate, ma in modo che non ci sia alcuna coppia di tacche poste alla stessa distanza. Trovare regoli di Golomb è semplice, ma trovare quello con il numero di tacche più grande possibile compatibilmente con la sua lunghezza è un problema computazionalmente molto difficile.

Come giocare su una scacchiera con i pezzi del Tetris

Una ventina d'anni fa Mr. Palomar passava molto tempo davanti al pc giocando a Tetris, il gioco delle forme colorate che cadono in una sorta di pozzo e che devono essere spostate e ruotate in modo da completare il numero maggiore possibile di righe orizzontali ininterrotte: quando una siffatta riga viene creata, come per incanto sparisce, dando respiro al giocatore.
Mr. Palomar ricorda bene i sette tipi di pezzi del Tetris:


Il gioco del Tetris venne ideato nel 1985 da un geniale programmatore russo, Aleksej Leonidovič Pažitnov, che allora lavorava in un centro di ricerca dell'Accademia delle Scienze Sovietica. Quando il gioco cominciò a spopolare in tutto il mondo, verso la fine degli anni Ottanta, al buon Pažitnov, in quanto dipendente statale, non vennero riconosciuti i diritti d'autore: cosicché nel 1991 fece le valigie ed emigrò negli Stati Uniti, dove poté meglio raccogliere i frutti del proprio ingegno.
Passato il periodo di "innamoramento" per l'allucinogeno videogame, Mr. Palomar esaurì ben presto l'interesse verso il Tetris, dedicandosi ad altro e dimenticando quella passione giovanile.
Spesso, però, le cose del passato tendono imprevedibilmente a tornare. Poco tempo fa Mr. Palomar fu invitato a casa di un suo amico, Mr. Wilson, esperto di matematica e di giochi matematici. Mentre i due parlavano del più e del meno, Mr. Palomar notò alcuni pezzi di cartone colorato su un tavolo e domandò all'amico di cosa si trattasse.
- I tetramini! Non ti ricordi più il Tetris?
- Ah, è vero!
A Mr. Palomar sembrò che un remoto ricordo fosse riemerso da uno sperduto anfratto della sua memoria.
- Ricordi perché si chiamano così, vero? Ogni pezzo colorato che nel Tetris deve essere sistemato sul fondo del pozzo è formato da quattro quadratini, e quindi...
- Sì, lo ricordo, non c'è bisogno che me lo spieghi.
- Aspetta, porto la scacchiera!
- La scacchiera? Stavamo parlando del Tetris, mica degli scacchi!
- Aspetta. Aspetta e vedrai - rispose Mr. Wilson, infilandosi frettolosamente nel suo studio.
Tornò con una pesante scacchiera di legno sotto braccio. La posò sul tavolo. Mr. Palomar prese in mano uno dei tetramini di cartone e si accorse che i quattro quadrati che lo costituivano coincidevano perfettamente con la dimensione dei quadrati della scacchiera. In altre parole, ogni forma colorata di Mr. Wilson poteva essere posata sulla scacchiera in modo da coprire le caselle con precisione.
- Un momento! - disse improvvisamente Mr. Palomar - Qui ci sono solo cinque tetramini di cartone, mentre nel Tetris i pezzi erano di sette tipi. Ne hai persi due?
- No - rispose Mr. Wilson - Guarda qui! - e capovolse due delle cinque sagome: quella rossa e quella blu. Il tetramino rosso era colorato di verde sull'altro lato, mentre quello blu aveva l'altra faccia arancione.
- Ahhh, forse ho capito! - esclamò Mr. Palomar - Nel Tetris due tetramini sono considerati di tipo diverso se differiscono per una riflessione o per una rotazione nello spazio tridimensionale. Quindi il tetramino blu, simile ad una J, è diverso dal tetramino arancione, simile ad una L, e così quello rosso, dalla forma di una Z va distinto da quello verde, fatto a S.
- Esatto. I matematici, invece, preferiscono considerare uguali due tetramini che differiscono per una riflessione o per una rotazione, ed io ho seguito questa convenzione nel ritagliare queste sagome. Però, in onore del glorioso Tetris, ho mantenuto, sulle due facce dei tetramini "bivalenti", le due diverse colorazioni. Guarda queste altre forme adesso.
Mr. Wilson aprì una busta, dalla quale fuoriuscirono altre 12 sagome di cartone colorato.


- Queste però non sono tetramini, o sbaglio?
- Non sbagli. Conta i quadrati in ogni forma.
- Uno, due, tre, quattro... cinque. Sono... pentamini?
- Indovinato. Tetramini e pentamini non sono che casi particolari di polimini, cioè figure piane composte da un numero finito di quadrati connessi tra di loro lungo i lati. In inglese si chiamano polyominoes.
- Quindi se usiamo soltanto tre quadratini per ogni forma, abbiamo dei... trimini?
- Certo. E con due quadratini abbiamo...
- Aspetta! Lasciami indovinare: domini?
- Già. Non ti dice niente questa parola? Non ti ricorda un famoso gioco?
- Il domino! Certo! In effetti i pezzi del domino non sono altro che coppie di quadrati connessi.
- Proprio così. E con numeri di quadrati superiori a cinque, abbiamo invece gli esamini (che non sono esami facili!), gli ettamini, e così via.
Mr. Palomar rimase qualche secondo in silenzio, osservando le sagome colorate sul tavolo. Poi disse:
- Stavo pensando ai domini, polimini con due quadrati: esiste un solo modo di connettere due quadrati tra di loro per i lati, cioè esiste un solo tipo di domino. Giusto?
- Giusto. Così come esistono due tipi di trimino.
- E i pentamini? Quanti sono?
- Sono 12, seguendo la convenzione in auge presso i matematici. Gli esamini invece sono 35, gli ettamini 108, gli ottamini 369, e così via. Fu un certo Solomon W. Golomb, studente di Harvard negli anni Cinquanta, che, annoiato dalle lezioni, cominciò a disegnare polimini sul suo quaderno a quadretti, per poi classificarli e analizzarli.


Mr. Wilson tacque per qualche secondo, poi aggiunse, quasi tra sè e sè:
- Forse mentre faceva questo non immaginava che stava fondando uno dei capitoli più affascinanti della matematica ricreativa. Qualche anno dopo, però, Golomb divenne professore alla University of Southern California e approfondì molti settori dell'ingegneria, della teoria dei numeri e della teoria delle comunicazioni elettriche. Dopo la sua invenzione dei polimini, molti matematici e divulgatori, primo fra tutti il grande Martin Gardner, hanno esplorato a fondo quel mondo di quadratini, anche molto prima che il Tetris lo portasse alla ribalta del grande pubblico.
- Ma la scacchiera? Cosa vuoi farci?
- Cosa vuoi fare con una scacchiera? Giocare, no?
- Con i tetramini e i pentamini?
- Certo. Ci sono un sacco di giochi che si possono fare su una scacchiera usando polimini come questi. Ad esempio, prova a coprire la scacchiera usando i 12 pentamini.
Mr. Palomar rifletté:
- Dodici pentamini coprono 12x5=60 caselle, mentre la scacchiera comprende 8x8=64 caselle. Cosa ne facciamo delle 4 caselle rimanenti?
- Molto perspicace, complimenti! Le lasciamo vuote, semplicemente.
Per qualche secondo Mr. Palomar guardò l'amico con sguardo ebete, poi provò a sistemare sulle caselle della scacchiera le sagome di cartone, cercando di ricoprire esattamente tutta la scacchiera.
Dopo qualche minuto di tentativi infruttuosi, esclamò:
- Mica facile, però!
- No, non lo è. Su internet ci sono molti programmini che mostrano come si può ottenere un simile ricoprimento. Ad esempio una soluzione è questa.
Mr. Wilson spostò alcuni pezzi sulla scacchiera e ottenne la seguente configurazione:


- Eh, troppo comodo! La fai facile tu che conosci già la soluzione.
- Hai ragione. Ma pensa, anche imponendo il vincolo di collocare le quattro caselle eccedenti al centro della scacchiera, esistono ben 65 soluzioni diverse.
- Va bene, proverò ad esercitarmi a casa.
- Adesso ti faccio vedere un gioco che ho inventato io, con i cinque tipi di tetramini. Si gioca in due, io contro di te. Soltanto che devo tirare fuori altri pezzi di cartone che ho preparato. Infatti serve avere un certo numero di pezzi per ciascun tipo di tetramini: ad esempio un po' di pezzi del tipo lungo (quello celeste), un po' del tipo quadrato (quello giallo), e così via. Il gioco prende ispirazione dalle carte geografiche politiche.
- Le carte geografiche?
- Sì, in queste carte due stati confinanti non possono essere colorati con lo stesso colore. Analogamente, il gioco consiste nel posare a turno sulla scacchiera un pezzo, con la regola che non si può mettere un pezzo vicino ad altro dallo stesso colore.
- Interessante, proviamo.
I due giocarono per un po'. Il gioco era abbastanza divertente, ma a un certo punto Mr. Palomar, desideroso di provare nuovi rompicapi, domandò:
- Conosci altri giochi?
- Certo. Ce n'è uno ancora più semplice, ma molto divertente. Anche questo si può giocare in due, con i tetramini oppure con i pentamini. Io scelgo un pezzo e lo metto dove voglio sulla scacchiera. Poi tocca a te, e fai altrettanto. Perde chi che non riesce più a collocare un pezzo senza che vada a sovrapporsi agli altri.
- Caspita! Questo mi sembra un bel gioco!
- L'ha inventato il buon Golomb in persona.
- Proprio un tipo interessante, questo Golomb. Mi piacerebbe conoscerlo.
- Potremmo andare a trovarlo in California.
- Perché no?
I due cominciarono a giocare, e non smisero se non dopo parecchie ore.

Il problema del campionato - Parte 2

Una delle meraviglie (meravigliosa per me, s'intende) presenti nel mitico almanacco del calcio (vedi Parte 1 di questo multi-post) era che venivano riportati i risultati di tutte le partite di tutti i campionati italiani di serie A, dalle lontane ottocentesche origini fino alla stagione in corso; ma la vera meraviglia per i miei occhi era che queste informazioni erano pubblicate in un modo estremamente compatto: una paginetta per ogni campionato, cioè per ogni anno.
Com'è possibile? Venivano usati caratteri microscopici, da leggere con la lente d'ingrandimento? No, semplicemente avevano escogitato un semplice ma ingegnoso metodo per risparmiare molto spazio, che a me piacque molto.

Solitamente i risultati delle partite di un torneo vengono riportati in una forma come la seguente (tratta da Wikipedia):


Nell'almanacco, invece, per ogni stagione veniva presentata una matrice quadrata con un numero di righe (e di colonne) pari al numero di squadre partecipanti, e nelle caselle interne venivano riportati i risultati delle partite che avevano visto in campo le due squadre corrispondenti alla riga e alla colonna di riferimento.
Per convenzione, in ogni incontro la squadra di casa era quella corrispondente alla riga, e quella ospite era quella corrispondente alla colonna. In questo modo, la diagonale principale della matrice restava vuota per l'ovvio motivo che una squadra non può giocare contro se stessa.
Presa una qualsiasi casella (quindi una partita) in una o nell'altra delle sezioni triangolari divise dalla diagonale principale, la casella speculare rispetto alla diagonale stessa risulta corrispondere alla ripetizione della stessa partita nell'altro girone della stagione (se la prima partita appartiene al girone di andata, la seconda appartiene al girone di ritorno, e viceversa).
Se N è il numero di squadre del torneo (si ipotizza che N sia sempre pari), la matrice quadrata avrà lato N per costruzione; le partite complessivamente presenti sono quindi N² - N (occorre infatti togliere la diagonale principale vuota), quindi N(N-1).
In effetti le giornate del campionato sono N-1, perché ogni squadra deve giocare contro tutte le squadre tranne se stessa (d'altra parte, N-1 è il numero di caselle compilate in ogni riga e in ogni colonna); e in ogni giornata vengono disputate N/2 partite. Quindi le partite complessive in un girone di andata sono 1/2 N(N-1), numero che va raddoppiato per tener conto del girone di ritorno: viene così confermato il risultato N(N-1) ottenuto sopra.
(Nelle figure seguenti, per semplificare un po', ho posto N=4).


Il trucco della matrice per risparmiare spazio è piuttosto banale e ovvio, direte voi. Certo, ma all'undicenne che ero allora ingenuamente sembrò geniale.
Quando, anni dopo, mi cimentai nel problema della generazione del calendario, tema centrale di questi post, mi tornarono subito alla mente le magiche matrici dell'almanacco del calcio.
Immaginai che all'interno delle caselle, anziché i risultati degli incontri, fossero scritti i numeri delle giornate in cui tali incontri sono programmati (o già disputati).
Ad esempio, la partita tra la Squadra A e la Squadra B è programmata per la giornata n. 1, la partita tra la Squadra B e la Squadra C è programmata per la giornata n. 3, e così via.


Ora apportiamo una nuova leggera variazione alla matrice: trascuriamo la differenza tra andata e ritorno, e di conseguenza nelle due caselle corrispondenti all'andata e al ritorno di un certo incontro tra due squadre (due caselle speculari nel senso spiegato prima), mettiamo lo stesso numero, relativo, per convenzione, alla giornata del girone di andata in cui si disputa la prima delle due gare.
Otteniamo una matrice come quella seguente:


Osservando la matrice ottenuta, notiamo che essa gode di due interessanti proprietà:
1) è simmetrica rispetto alla diagonale principale;
2) tralasciando le caselle vuote sulla diagonale, su ogni riga e su ogni colonna sono presenti tutti i numeri da 1 a N-1, senza ripetizioni.
Per la verità, queste due condizioni sono necessarie e sufficienti affinché la matrice rappresenti un calendario valido per un campionato. Infatti, se su una stessa riga o colonna ci fossero due caselle con lo stesso numero, vorrebbe dire che una squadra dovrebbe giocare due partite nella stessa giornata (e, corrispondentemente, un'altra squadra non giocherebbe alcuna partita): situazione questa ovviamente non ammessa.

Vi viene in mente qualche famoso rompicapo in cui accade qualcosa di simile?
Risposta esatta: il sudoku!


Anche il sudoku si gioca su una matrice quadrata, precisamente con N=9.
Su ogni riga e colonna devono essere posti tutti i numeri da 1 a 9, senza ripetizioni: lo stesso termine "sudoku", in giapponese, significa proprio qualcosa come "i numeri devono comparire una sola volta".
Le uniche due differenze, rispetto alla matrice del campionato, sono le seguenti:
1. anche le caselle sulla diagonale vanno riempite regolarmente, come le altre;
2. esiste un ulteriore vincolo, relativo ai 9 sotto-quadrati 3x3 evidenziati all'interno dello schema complessivo: anche in ciascuno di essi, tutti i numeri da 1 a 9 devono essere presenti senza ripetizioni.

Sia per giocare a sudoku sia per stilare il calendario del campionato, quindi, si tratta di risolvere un problema vincolato in cui occorre assegnare dei numeri ad alcune caselle.
Prendiamo in esame la matrice del campionato, di lato N, e trasformiamo ogni casella in un nodo di un grafo, mettendo in ogni casella l'indicazione della partita corrispondente.
Poi colleghiamo tra loro, mediante archi, gli N nodi che appartengono alla stessa riga, e poi facciamo lo stesso con i nodi che appartengono alla stessa colonna.
Usiamo però l'accortezza di accorpare tra loro i nodi che contengono una partita tra le stesse due squadre: andata e ritorno per noi, ora, sono la stessa cosa.
Il grafo che si ottiene alla fine di questo procedimento è il seguente:


Il nostro problema iniziale consisteva nell'assegnare un numero (da 1 a N) a ciascuna delle caselle della matrice. Il corrispondente problema sul grafo è assegnare un numero (da 1 a N) ad ogni nodo del grafo ottenuto.
In questo grafo, infatti, ogni nodo corrisponde a due caselle della matrice originaria. Sappiamo che queste due caselle conterranno lo stesso numero, corrispondente alla giornata in cui si disputerà la gara di andata tra le squadre in questione: per determinare la giornata della gara di ritorno basterà aggiungere N-1.

Se ci viene dato un grafo come quello della figura precedente, come possiamo procedere per assegnare un numero da 1 a N a ciascun nodo?
L'unico vincolo che dobbiamo rispettare è che a due nodi collegati tra loro non può essere assegnato lo stesso numero.
Spesso, per rendere il problema più... vivace, anziché assegnare un numero da 1 a N a ciascun nodo del grafo, si assegna un colore, preso da una gamma di N colori.
Il vincolo diventa allora che due nodi contigui non possono condividere lo stesso colore (a volte si descrive questo vincolo dicendo che "non possono esistere archi monocromatici").
E' chiaro che usando colori invece che numeri, il problema non muta minimamente la sua struttura matematica.
I matematici chiamano questo problema graph coloring, cioè colorazione dei grafi.
Si tratta di un problema molto noto nell'ambito della ricerca operativa, cioè di quella parte della matematica e dell'informatica che si occupa di formalizzare problemi complessi di ottimizzazione attraverso modelli matematici, allo scopo di trovare soluzioni ottime, se possibile, o approssimate.
Tornerò sull'argomento in altri post; qui mi limito a sottolineare che colorare i grafi (ovviamente rispettando la condizione degli archi monocromatici) non è per niente affare da poco, anzi il più delle volte rappresenta un problema molto difficile.
Nella prossima parte, quindi, vedremo come il problema del campionato convenga che sia risolto utilizzando altri metodi, molto più semplici.
Valeva la pena, però, fare questa deviazione: anche se non fruttuosa sul piano della ricerca di tecniche risolutive, per lo meno interessante e, spero, divertente.