Gli enigmi di Coelum: Natale su Ganimede

Proseguendo la serie dedicata ai miei enigmi pubblicati in passato sulla rivista "Coelum", ho pensato di non rispettare, per la prima volta, l'ordine di pubblicazione degli articoli: questo allo scopo di offrirvi ora, in dicembre, il pezzo più "natalizio" che abbia mai pubblicato sulla suddetta rivista, evitandone così una inopportuna uscita intorno a Ferragosto.

Prendete un foglio di carta. Disegnate a caso alcuni punti, e colorate di rosso uno di loro. Immaginate ora che il punto rosso rappresenti il punto di partenza e di arrivo di un tragitto che deve necessariamente toccare anche tutti gli altri punti, ciascuno una e una sola volta.
Ora, se esaminate il vostro foglio, vi accorgerete che, molto probabilmente, esistono numerosi tragitti che soddisfano i requisiti: tutti partono dal punto rosso, passano attraverso tutti gli altri (ciascuno esattamente una volta), e finiscono di nuovo sul punto rosso. Il bello è che i percorsi possono avere lunghezze diverse. Il vostro compito è trovare il tragitto più breve tra tutti quelli ammissibili.
Ogni percorso possibile è formato da una sequenza di segmenti consecutivi, ciascuno dei quali congiunge tra di loro due punti. Per stabilire qual è il percorso più breve, dovete armarvi di righello (e di pazienza), prendere in esame tutte le soluzioni possibili e di ciascuna misurare la lunghezza totale (equivalente alla somma delle lunghezze dei singoli segmenti che congiungono i punti): in questo modo il problema si riduce alla fine a un confronto tra tutte le soluzioni trovate.
Una formulazione più rigorosamente matematica richiede che vengano specificate in partenza le distanze esistenti tra tutte le possibili coppie di punti. Ciò è necessario perché le coppie di punti connesse da segmenti in una certa soluzione sono in generale diverse dalle coppie congiunte in un’altra soluzione. I matematici chiamano grafo completo una rete di punti corredata di queste informazioni sulle distanze tra punti.
Il problema che ho descritto è noto come “problema del commesso viaggiatore”. È uno dei problemi classici della teoria dei grafi, e trae il suo nome dall’interpretazione tipica che viene data: un commesso viaggiatore deve visitare una serie di città (ciascuna esattamente una volta) partendo da una di esse e terminando il suo giro nella stessa città di partenza, scegliendo però il viaggio più breve possibile.
Ad esempio, consideriamo il grafo completo della figura qui sotto. Supponiamo che ognuno dei 4 nodi corrisponda a una città, e che gli archi che congiungono i nodi tra di loro rappresentino le strade che collegano una città all’altra.
Su ogni strada viene indicata la sua lunghezza (ad esempio in km). Consideriamo la città 1 come punto di partenza e di arrivo dei tragitti.

Un possibile percorso è quello che attraversa, nell’ordine, le città 1 – 4 – 2 – 3 -1. Se fate la somma dei numeri indicati sugli archi interessati, scoprite che la lunghezza complessiva di questo percorso è 95 km. Un altro percorso possibile è 1 – 3 – 4 – 2 – 1, la cui lunghezza è 80 km. Il secondo percorso, quindi, è migliore del primo.
Quanti sono i possibili percorsi che dobbiamo considerare? Il loro numero equivale al numero di possibili permutazioni dei nodi del grafo completo privato del nodo di partenza e di arrivo (che sicuramente deve trovarsi all’inizio e alla fine della sequenza), cioè al numero di modi di mettere in fila questi 3 nodi. Ebbene, non è difficile dimostrare che il numero di permutazioni di un insieme di N elementi è dato dal fattoriale di N, che si indica con il simbolo N! e che corrisponde al prodotto di tutti i numeri interi compresi tra 1 e N. Nel nostro esempio di grafo con 4 città, i nodi in questione sono N = 3, e quindi le possibili soluzioni sono pari a N! = 3! = 3 × 2 × 1 = 6.

Per risolvere il problema, dovremmo misurare la lunghezza di ciascuno dei possibili 6 percorsi, e alla fine potremmo stabilire qual è il più breve in assoluto.
Finché i nodi del grafo (cioè le città) sono soltanto 4, o comunque molto poche, il numero di soluzioni possibili è abbastanza limitato, ed è quindi possibile esaminarle tutte, magari conl’ausilio di un programma informatico. Purtroppo, però, il fattoriale è una funzione che cresce molto rapidamente (vedi tabella): già con 8 città le alternative sarebbero 40.320, con 10 città salirebbero a 3.628.800, e con 20 città si arriverebbe a più di 2 miliardi di miliardi!
Anche impiegando computer potentissimi, il problema diventa ben presto intrattabile, e sono necessarie tecniche di approssimazione (o euristiche) per la ricerca delle soluzioni.

Qualche lettore affezionato ricorderà che nel primo articolo della rubrica Moebius, uscito nel numero di luglio-agosto 2013, avevo parlato di due celebri rompicapi matematici: le torri di Hanoi e il gioco icosiano. L’inventore di quest’ultimo fu Sir William Rowan Hamilton, che nel 1857 descrisse il gioco durante una riunione della British Association for the Advancement of Science.
Il rompicapo consisteva nel trovare un cammino che toccasse tutti i vertici di un dodecaedro (uno dei solidi platonici, da me trattati nel numero di settembre 2014), percorrendo ciascuno degli spigoli esattamente una volta. Nelle due figure sono mostrati la confezione originale del gioco e una soluzione.

Il gioco icosiano è, evidentemente, una particolare variante del problema del commesso viaggiatore, in cui il grafo di partenza non è completo, cioè è possibile utilizzare solo alcuni archi (quelli che corrispondono a spigoli del dodecaedro) e non altri.
Il problema generale del commesso viaggiatore, invece, fu analizzato negli anni Trenta del XX secolo dopo dal matematico austriaco Karl Menger, famoso soprattutto per aver descritto un particolare frattale tridimensionale noto come “spugna di Menger”.
L’ormai popolare riferimento alla figura del “commesso viaggiatore” nel nome classico del problema fu un’intuizione del matematico americano Hassler Whitney.

Per cercare di risolvere il problema del commesso viaggiatore (o “travelling salesman problem”, TSP, all’inglese), fino agli anni ‘50 del secolo scorso si utilizzò sempre il cosiddetto metodo di “forza bruta”, cioè l’enumerazione esaustiva di tutti i percorsi possibili e la comparazione delle rispettive lunghezze: ciò rendeva del tutto impensabile la risoluzione del problema con un numero di nodi appena superiore a una decina.
Nel 1954 i matematici americani George Dantzig, Ray Fulkerson e Selmer Johnson proposero un metodo alternativo, basato sulla tecnica dei piani di taglio, per risolvere il problema in modo più efficiente: così facendo riuscirono a trovare un percorso ottimale attraverso le 48 capitali degli Stati Uniti (Alaska e Hawaii non erano ancora diventati Stati a tutti gli effetti) più Washington, capitale federale.
La soluzione migliore, come scoprirono i tre matematici, era quella illustrata in figura.

Nel 1962, la Procter & Gamble lanciò un concorso tra i suoi clienti: per aggiudicarsi il premio in palio, si doveva risolvere il problema del commesso viaggiatore su una rete con 33 città.
Ulteriori progressi vennero ottenuti nei decenni successivi, sfruttando la crescente potenza dei computer ma soprattutto le tecniche via via più raffinate che i ricercatori riuscirono a sviluppare. Si cominciò così a risolvere il problema anche con molte migliaia di nodi.

Nel numero 187 di Coelum, la rubrica Moebius ha rivestito il classico problema del commesso viaggiatore di un’ambientazione al tempo stesso interplanetaria e natalizia: la sfida consisteva nell’aiutare Babbo Natale a trovare un percorso ottimale per portare regali a tutti i bambini buoni del Sistema Solare.
Più precisamente, il contesto fantascientifico da me ipotizzato prevedeva cinque mondi abitati: la Terra, la Luna, Marte, Cerere e Ganimede. I mondi sono tra di loro connessi da speciali collegamenti, e ogni rotta che congiunge due mondi può essere percorsa dall’astroslitta di Babbo Natale in un certo numero di ore, il medesimo nelle due direzioni. In questo particolare problema del commesso viaggiatore (o meglio, del Babbo Natale interplanetario), al posto delle città abbiamo quindi i cinque pianeti, e ogni arco del grafo è etichettato non da una lunghezza in chilometri, ma da un tempo di percorrenza in ore.
Cito dall’articolo:

Precisamente, Marte dista due ore e mezza dalla Terra, ma la stessa distanza lo separa anche dalla Luna e da Ganimede. Tra la Terra e la Luna c’è un’ora di volo, mentre il nostro satellite dista tre ore e mezza da Ganimede. Terra e Cerere sono lontani quattro ore, e due ore separano il pianeta nano da Ganimede e anche da Marte.

Il compito del lettore consisteva pertanto nel trovare il tragitto più veloce, non il più breve. Ma non solo. Il percorso ottimale doveva soddisfare anche un ulteriore, fondamentale vincolo: ogni bambino del Sistema Solare doveva ricevere un regalo. Si ipotizza infatti che ciascuno dei pianeti abitati ospiti un certo numero di bambini e un magazzino con una data quantità di giocattoli. All’arrivo su ogni pianeta, Babbo Natale può caricare sul suo fantastico veicolo volante i giocattoli presenti nel magazzino. Nella tabella seguente sono indicati il numero di bimbi e di giochi presenti su ogni mondo.

Pianeta	Numero bambini	Numero giocattoli
Terra	1 miliardo	1,1 miliardi
Luna	100 milioni	100 milioni
Marte	400 milioni	200 milioni
Ganimede	200 milioni	400 milioni
Cerere	100 milioni	0

In conclusione, il percorso ottimale deve permettere a Babbo Natale di partire dalla Terra, visitare ognuno degli altri quattro pianeti, ciascuno esattamente una volta, e ritornare al punto di partenza, utilizzando i collegamenti indicati e riuscendo a portare un regalo a ogni bambino. Semplice, no?

Qualche lettore appassionato di fantascienza si sarà forse ricordato che il titolo dell’articolo di dicembre, “Natale su Ganimede”, è lo stesso di un racconto dell’amatissimo (sicuramente da me, ma non solo) scrittore e divulgatore scientifico Isaac Asimov.
Il racconto fu pubblicato nel 1942 sulla rivista Startling Stories. In una sua autobiografia, Asimov rivelò che si era sforzato di scrivere una storia soprattutto divertente, cosa che, a suo parere, è una delle più difficili in assoluto per uno scrittore. Curiosamente, anche il racconto di Asimov tira in ballo Babbo Natale. La storia, com’è facile immaginare, è ambientata sul satellite gioviano Ganimede, per l’occasione popolato da strane creature simili a struzzi, chiamati ossies e utilizzate dalla Ganymedan Products Corporation come forza lavoro. Un giorno qualcuno racconta agli ossies di Babbo Natale, e loro decidono di scioperare finché il barbuto portatore di doni non si recherà in visita su Ganimede. L’azienda entra in una grave crisi, e ciò costringe gli abitanti umani di Ganimede a inscenare una finta visita di Babbo Natale. Tutto sembra risolto, quando gli ossies richiedono che Babbo Natale vada a trovarli ogni anno. Peccato che l’anno ganimediano, cioè il periodo di rivoluzione di Ganimede attorno a Giove, dura soltanto sette giorni terrestri…

La risoluzione del problema richiedeva un po’ di attenzione. Partendo dalla Terra, Babbo Natale può caricare sulla sua astroslitta 1,1 miliardi di regali, ma dovrà consegnarne 1 miliardo prima di lasciare il pianeta. Decollerà quindi con un carico di “soli” 100 milioni di giocattoli, cosa che gli impedirà di atterrare su Marte, visto che sul pianeta rosso ci sono 400 milioni di bambini ma soltanto 200 milioni di giocattoli. La sua seconda tappa potrà quindi essere Cerere oppure la Luna.
Nel primo caso, dopo il pianeta nano sarà sicuramente la volta di Ganimede, perché Marte risulta ancora off limits per motivi di eccedenza di bambini rispetto ai doni disponibili. Dopo Ganimede Babbo Natale deve raggiungere la Luna e Marte, in uno dei due ordini possibili, per poi fare ritorno sulla Terra.
Anche nel secondo caso, la successiva tappa dopo la Luna deve essere per forza di cose Ganimede, seguito da Marte e Cerere, in entrambe le sequenze possibili, e infine la Terra.
I quattro percorsi ammessi sono di conseguenza:

Terra Cerere Ganimede Luna Marte Terra

Terra Cerere Ganimede Marte Luna Terra

Terra Luna Ganimede Marte Cerere Terra

Terra Luna Ganimede Cerere Marte Terra

I tempi di percorrenza dei quattro tragitti sono, rispettivamente: 14,5 ore, 12 ore, 13 ore, 11 ore.
Il percorso ottimale, quindi, risulta il seguente:

Terra Luna Ganimede Cerere Marte Terra

Carnevale della Matematica #103 su Maddmaths!

Com'è giusto che sia, Mr. Palomar torna a celebrare i Carnevali della Matematica. L'edizione di novembre, centotreesima della lunga e gloriosa storia del Carnevale, è stato ospitato dal prestigioso sito MaddMaths!, e il tema suggerito era "Donne in matematica".
Come sottolineano gli autori di MaddMaths!:

Se ne è parlato tanto di recente, e vorremmo aggiungere che se ne è parlato soprattutto perché ci sono tante donne che fanno parlare di sé per i loro successi matematici.

Il post carnevalesco è opportunamente (e piacevolmente) adornato da una lunga serie di fotografie di illustri donne matematiche, a dimostrazione che la scienza di Euclide ed Eulero non è femminile soltanto di nome, ma anche di fatto.
Questa edizione si distingue per la numerosità dei blogger partecipanti e dei contributi, alcuni dei quali a tema e altri no. Per fortuna le consuetudini carnevalizie sono benevole, e ogni post di argomento matematico viene accolto: perfino quelli di Mr. Palomar, che per questo mese ha contribuito con due post completamente fuori tema, sul machine learning e sulle tecniche di memorizzazione dei numeri (a ben vedere, il primo aveva a che vedere con i generi, e il secondo tirava in ballo divinità pagane femminili come Mnemosine e Urania: va bene, la smetto di arrampicarmi sugli specchi).
Complimenti a tutti i partecipanti e a MaddMaths!, in particolare Roberto Natalini che ha allestito questa ricca edizione. Come è già accaduto l'anno scorso, il Carnevale di dicembre uscirà su queste pagine. Il motto gaussiano di questa edizione pre-natalizia sarà “canta allegro, canta, canta”, e il tema... be', il tema lo svelerò prossimamente. Evviva il Carnevale!

Gli enigmi di Coelum: Le parole per dirlo

La divinità Mnemosine in un
dipinto di Dante Gabriel Rossetti

Vi sono sequenze di nomi, parole o cifre che è molto difficile riuscire a imparare a memoria senza un qualche ausilio. Al giorno d’oggi tendiamo a coltivare meno di un tempo le potenzialità mnemoniche del nostro cervello: forse perché ci possiamo affidare alla disponibilità di memorie artificiali, che ci permettono di immagazzinare enormi quantità di dati in spazi trascurabili e di reperire le informazioni desiderate in tempi brevissimi.
Nel passato, invece, e in particolare nell’antichità, alla capacità di ricordare veniva attribuita un’importanza fondamentale. Non possiamo tralasciare che a causa dell’alto tasso di analfabetismo la maggior parte della conoscenza veniva tramandata oralmente: saper ricordare, quindi, era a maggior ragione importante.
Celebri maestri di oratoria come Cicerone e Quintiliano riconobbero come in questa particolare arte il “trucco” più efficace risieda nell’associazione: per mandare qualcosa a memoria conviene cioè escogitare un qualche legame con oggetti concreti, o immaginare di collocare in luoghi familiari ciò che si deve ricordare. La grande rilevanza che gli antichi assegnavano alla memoria è testimoniata anche dal fatto che Mnemosine, una delle divinità dell’Olimpo, era la personificazione di questa facoltà della mente umana. Figlia di Urano e della Terra, fu amata da Zeus e divenne madre delle Muse, le nove divinità che rappresentavano le arti: in particolare la storia, la poesia lirica, la poesia amorosa, la poesia epica commedia, la tragedia, la danza, il mimo e, strano a dirsi, l’astronomia.

Urania, in una statua conservata
ai Musei Vaticani

Urania, musa dell’astronomia, era quindi figlia di Mnemosine, cioè della memoria: evidentemente già gli antichi erano consapevoli della grande difficoltà di tenere a memoria l’intera conoscenza delle cose celesti.
E figuriamoci nei tempi più recenti, quando le conoscenze astronomiche si sono fatte via via più vaste.
Ecco quindi le filastrocche alle quali accennavo nell’articolo del numero 181, inventate per ricordare più facilmente certe sequenze di interesse astronomico, come le principali classi spettrali delle stelle (“Oh, Be A Fine Girl: Kiss Me!”, “On Betelgeuse Astronomers Find Galactic Kings Making Lovely Tangerine Yogurts”) o i pianeti del sistema solare (“My Very Excellent Mother Just Sent Us Nine Pies”).

Oltre agli studenti di astronomia, anche quelli di altre discipline scientifiche possono trovare utili le tecniche di memorizzazione: ad esempio quelli di medicina, sempre alle prese con lunghissime litanie di tessuti, organi e apparati dai nomi complicati.
Tuttavia è forse la matematica l’ambito scientifico nel quale sono state ideate le tecniche mnemoniche più interessanti e sfoggiati i risultati più sorprendenti.
Vi sono per esempio alcuni numeri “speciali”, particolarmente degni di nota per i matematici, e per questo meritevoli di essere conosciuti e magari “imparati a memoria”. Sfortunatamente questi numeri non sono interi. Non solo, ma dopo la virgola hanno addirittura un numero infinito di cifre. I tre numeri più famosi di questa “famiglia” sono il pi greco, cioè π, pari a 3,141592653…, il numero di Eulero e, uguale a 2,718281828…, e il rapporto aureo φ, uguale a 1,618033988…
Ognuno di questi numeri ha un buon motivo per essere celebre. Ad esempio, π è il rapporto tra la lunghezza di una circonferenza e quella del corrispondente diametro. Questo rapporto è uguale per tutti i cerchi, siano essi grandi o piccoli. Il bello è che questo numero salta fuori non soltanto in geometria, ma anche in innumerevoli teoremi di analisi matematica, teoria dei numeri, calcolo della probabilità, statistica, fisica, che non hanno alcuna parentela evidente con i cerchi né con qualsiasi altra figura geometrica.

Leonhard Euler, spesso italianizzato in Eulero, in una banconota svizzera

Anche il numero di Eulero e rappresenta una costante fondamentale della matematica, in particolare nella branca nota come analisi matematica. Prende il nome dallo svizzero Leonhard Euler, uno dei più grandi matematici di ogni epoca.
Il rapporto aureo φ, detto anche sezione aurea, corrisponde al rapporto tra due lunghezze tali per cui la più grande sta alla più piccola come quest’ultima sta alla differenza tra le due.
Sia π che e compaiono nell’identità di Eulero, che viene spesso definita la più bella formula della matematica:

e^iπ + 1 = 0

dove i è l’unità immaginaria, pari alla radice quadrata di -1. La bellezza di questa formula risiede nel fatto che stabilisce un sorprendente ponte tra tutti i numeri e tutte le operazioni fondamentali della matematica: i due speciali numeri π ed e, l’unità immaginaria i, lo zero (elemento neutro per l’addizione), l’uno (elemento neutro per la moltiplicazione), l’addizione, la moltiplicazione, l’elevamento a potenza, l’uguaglianza.

Pi greco, il numero di Eulero e il rapporto aureo sono tutti numeri irrazionali: in altri termini, non sono uguali al rapporto tra due numeri interi. Se π fosse esattamente uguale a 22 diviso 7, sarebbe un numero molto meno affascinante di quello che è. I numeri razionali, uguali al quoziente tra due interi, si dividono in due categorie: quelli della prima categoria hanno un numero finito di cifre decimali (ad esempio 22 diviso 8 è uguale a 2,75), mentre quelli della seconda categoria hanno infinite cifre decimali, ma in realtà si tratta di una sequenza finita di cifre che si ripete indefinitamente (questo è il caso di 22 diviso 7, che è pari a 3,142857 142857 142857…).
Pitagora era convinto che esistessero soltanto numeri razionali, ma si sbagliava di grosso. Gran parte del fascino di pi greco, del numero di Eulero e del rapporto aureo, dipende dal fatto che si tratta di numeri irrazionali, dotati di un corteo davvero infinito di cifre decimali, prive di ripetizioni.
Proprio per questo motivo si tratta di numeri estremamente inafferrabili: ogni tentativo di indicarne il valore è destinato a essere soltanto un’approssimazione. Ecco perché questi numeri hanno rappresentato a lungo, e rappresentano tuttora, una straordinaria palestra per chi pratica le tecniche mnemoniche.
La cosiddetta “conversione fonetica” è particolarmente indicata per memorizzare numeri di questo tipo: per prima cosa si utilizza una tabella standardizzata come la seguente per convertire ogni cifra in una particolare famiglia di consonanti.

Poi si aggiungono delle vocali tra una consonante e l’altra, allo scopi di comporre delle parole che possano essere facilmente ricordate. Il metodo fu ideato dal matematico tedesco Stanislaus Mink von Wennsshein e fu divulgato dal grande matematico e filosofo tedesco Gottfried Wilhelm von Leibniz.

Il matematico e scrittore inglese Lewis Carroll

Il matematico Charles Lutwidge Dodgson, più noto come Lewis Carroll, famoso autore di “Le avventure di Alice nel paese delle meraviglie”, utilizzò la conversione fonetica per memorizzare le prime 71 cifre decimali di π.

Provate voi stessi a “tradurre” π secondo il metodo della conversione fonetica. Tenendo conto di 32 cifre decimali (3,14159265358979323846264338327950) potreste ottenere qualcosa del genere (in maiuscolo le consonanti corrispondenti alle cifre, in minuscolo le vocali interposte, in corsivo le parti del discorso aggiunte per chiarezza espositiva):

Una TRoTa aLPiNa voleva volare fino in CieLo, ma prima di partire si mise la MaGLia, perché aveva paura del freddo: una vera FoBia. Arrivata in quota incontrò un’oCa, dalla cui coda mancavano delle PiuMe. Gliele aveva strappate uno GNoMo VoRaCe, che quando non mangia oche si sazia divorando NoCi, noci che coglie dai RaMi coperti di MUFFA, sporcandosi la MaNiCa vicino al PoLSo.

È proprio π il numero sul quale maggiormente si sono sbizzariti gli esperti di tecniche mnemoniche. In inglese esiste addirittura un termine specifico, “piphilology”, che indica l’utilizzo di metodi di questo tipo per ricordare le cifre di π.
A parte la conversione fonetica, l’altro metodo per trasformare le cifre decimali di numeri come π in frasi di senso compiuto è quello che utilizza una parola per ogni cifra, scegliendo la lunghezza della parola in modo che sia pari alla cifra stessa. Da qui espressioni come “Ave o Roma o madre gagliarda di latine virtù che tanto luminoso splendore prodiga spargesti con la tua saggezza”, oppure “Già: è bene e utile ricordare le dodici cifre del greco parametro”, o ancora “Non è dato a tutti ricordare il numero aureo del sommo filosofo Archimede. Certuni sostengon che si può ricordare tale numero, ma questi poi non recitano che un centone insensato”.
Questo gioco ha un dominatore indiscusso, l’ingegnere informatico americano Mike Keith, che nel 1996 compose un poema basato sulle prime 3835 cifre di π. Il poema, intitolato “Cadaeic Cadenza”, è decisamente uno degli esempi più impressionanti di piphilology. A quanto pare Keith non si è accontentato del suo poema, se è vero che nel 2010 ha scritto addirittura un libro intero, dal titolo “Not a wake: a dream embodying π’s digits fully for 10000 decimals”, che codifica le prima 10.000 cifre di π!

Il cinese Lu Chao

Se da una parte esistono i poeti di π, che forniscono i testi adatti alla memorizzazione delle sue cifre, dall’altra esistono i recordmen dello sport dell’apprendimento mnemonico. L’attuale detentore del primato è il cinese Lu Chao, che nel 2006, in una stupefacente performance, riuscì a recitare a memoria ben 67.890 cifre decimali del numero di Archimede, impiegando 24 ore e 4 minuti: secondo quanto riferì, aveva imparato a memoria le prime 100.000 cifre, ma alla 67.891-esima commise un fatale errore, dicendo “5” anziché “0”.

Il problema del numero 181 di Moebius consisteva nel trovare il frammento dello stesso articolo in cui erano rappresentate, mediante la tecnica del numero di lettere contenute in ogni parola, le prime cifre di uno dei numeri famosi della matematica. Come molti lettori erano riusciti a scoprire, il frammento incriminato era il seguente:
“Il sistema è efficace: si utilizza l’iniziale di ciascuna…”.
Se contate le lettere di ognuna di queste parole, e mettete una virgola dopo la prima cifra, ottenete infatti 2,71828182, che rappresenta l’inizio del numero di Eulero e, base dei logaritmi naturali.

Macchine che imparano #2: l'importanza dei vicini

Ricordate il problema della determinazione del genere di un autore? Ne avevo parlato nel primo post di questa serie dedicata alle tecniche di apprendimento automatico (in inglese, machine learning), interrotta sul nascere per molti mesi, che da oggi riprenderà tuttavia a camminare con maggiore regolarità.

Qualche volta vi sarà forse capitato di leggere un articolo, un racconto, o un qualsiasi testo, e non conoscendo nome e cognome dell'autore, vi sarete chiesti perlomeno se si tratti di un uomo o di una donna. Certo, questa attribuzione può diventare banale qualora il testo contenga indicazioni autoreferenziali: se a un certo punto si legge qualcosa come "il tale giorno mi sono recata nella tale città" è evidente che a scrivere è una donna e non un uomo. Ma in molti altri casi è molto più difficile determinare il sesso dell'autore, e per farlo ci si deve basare su elementi poco oggettivi e di dubbia interpretazione, come lo stile, la frequenza di certe parole, l’utilizzo di costrutti sintattici.

Può sembrare strano, ma c’è chi si è occupato in modo scientifico di questo tipo di determinazioni. Da alcuni studi, condotti su diverse lingue (non soltanto l'inglese ma, per esempio, anche lo spagnolo), risulta per esempio che gli uomini utilizzano le preposizioni in misura maggiore rispetto alle donne. Una spiegazione psicologica che viene fornita a supporto di questo dato è che gli uomini hanno più bisogno di categorizzare gerarchicamente gli oggetti all'interno dell'ambiente. Viceversa, le donne sembrano adoperare più interiezioni, più pronomi, più determinanti (cioè articoli, pronomi dimostrativi e in certe lingue come l'inglese e il francese anche i possessivi) rispetto agli uomini, probabilmente perché sono più interessate alle relazioni sociali.

Alcune ricerche suggeriscono che le donne si esprimono mediante un linguaggio più emotivamente connotato, e per questo impiegano più aggettivi e più avverbi degli uomini. Inoltre sembra che gli uomini commettano più errori grammaticali delle donne e si servano più spesso di quantificatori. Un paio di articoli su questa area della ricerca sono questo e questo.

Mi piace l’idea di utilizzare il curioso problema della determinazione del genere di un autore come esempio di applicazione delle tecniche di apprendimento automatico. Supponiamo di avere una raccolta di 50 racconti: dei primi 49 conosciamo con certezza il genere dell’autore, ma per il cinquantesimo no. Come possiamo affrontare il problema? Potremmo provare a concentrarci su un insieme ristretto di indicatori che riteniamo significativi per il nostro compito di attribuire un genere all’autore misterioso. Immaginiamo di considerarne soltanto due, per esempio il numero di aggettivi e il numero di determinanti ogni 1000 parole.

A ognuno dei 49 racconti già classificati possiamo assegnare una coppia di numeri, corrispondenti agli indicatori che abbiamo scelto. Per esempio, il primo racconto potrebbe essere costituito complessivamente da 5450 parole, e contenere 409 aggettivi e 703 determinanti. Ciò significa che, mediamente, questo testo contiene circa 75 aggettivi e 129 determinanti ogni 1000 parole. La coppia di numeri da attribuire al primo racconto è quindi (75, 129). 

Potrebbe venire quasi spontaneo, a questo punto, pensare di rappresentare ciascuno dei racconti come un punto sul piano cartesiano, le cui coordinate (x, y) corrispondono ai due numeri caratterizzanti. Il risultato sarà un diagramma costellato di 49 punti, uno per ogni racconto già classificato. Potremmo pensare di rappresentare gli autori maschili come pallini gialli e le scrittrici come pallini viola. A questo punto analizziamo il cinquantesimo racconto, quello scritto dall'autore senza volto, e determiniamo i due indicatori. Il punto che disegneremo sul piano cartesiano avrà una collocazione ben precisa, ma non possiamo sapere se sia un pallino giallo o un pallino viola: il nostro obiettivo è proprio decidere il colore di questo cinquantesimo pallino.

Sgombriamo il campo da un dubbio: la tecnica che descriverò può sperare di risolvere il problema della determinazione del genere, ma è soggetta all'errore. Non c'è alcuna certezza nel successo di questo algoritmo, perché si tratta di una metodologia di predizione incerta per definizione.

L'idea è la seguente: si traccia una circonferenza attorno al pallino senza colore, in modo da comprendere al suo interno un numero prestabilito k di pallini colorati, ovvero di racconti di autore noto. La nostra predizione deve basarsi sul genere prevalente presente tra i k pallini racchiusi dalla circonferenza.

Per esempio, considerando la figura a fianco, con k = 3, abbiamo due pallini viola e un pallino giallo, cioè prevalgono le autrici. In base alla tecnica descritta, dobbiamo prevedere che l'autore del cinquantesimo racconto sia una donna. Che l'algoritmo sia per definizione incerto è dimostrato dal fatto che scegliendo, in alternativa, k = 6, i pallini considerati diventano 4 gialli e 2 viola: elementi che ci guiderebbero ad azzardare una predizione maschile per il cinquantesimo racconto.
Dove sta l'apprendimento automatico in questa procedura? Nella fase di acquisizione delle informazioni relative ai 49 punti associati ai racconti di autore noto: l'algoritmo, infatti, apprende, per ciascuno di questi punti, il genere dell'autore, e questi dati divengono la base di conoscenza su cui si basa la predizione relativa al cinquantesimo racconto. Si dice anche che questi 49 punti sono esempi noti che l'algoritmo utilizza per addestrarsi, in modo da costruire una sua descrizione interna (cioè un modello) del fenomeno, e quindi formulare predizioni.

L'esempio mostrato in figura ci fa osservare che lo stesso algoritmo può portare a predizioni diverse a seconda del valore scelto di k. Variando di poco il valore di k, infatti, cambia totalmente la predizione. Tale fenomeno si verifica perché sono stati scelti, per semplicità, valori molto bassi di k, mentre è evidente che, nella maggior parte dei casi, valori più alti di questo parametro possono garantire accuratezze migliori.

Inoltre, il problema scelto è un problema di classificazione binaria, perché la predizione può consistere esclusivamente in due opzioni: autore maschio o autore femmina. In problemi di tal genere, quando la predizione cambia, cambia di brutto (nel nostro esempio, da maschio a femmina, o viceversa), mentre in problemi di classificazione a più valori i cambiamenti possono essere meno radicali.

Altri due elementi molto importanti per il successo dell'algoritmo sono il numero di indicatori utilizzati e la quantità di dati di esempio impiegati per la fase di addestramento.

Utilizzando più di due indicatori, o, come si dice nel gergo tecnico, features, si può sperare di ottenere predizioni più accurate. Questo non è assicurato, tuttavia, perché se si includono nel modello features non significative, cioè grandezze che non influenzano il valore che si vuole predire, allora l'aumento del numero di features non aumenta la qualità delle predizioni. Aumentare il numero di features significa muoversi non più sul piano cartesiano, ma su un iperspazio a n dimensioni, dove n è il numero delle features selezionate.

Poter disporre di un numero il più alto possibile di esempi già classificati da cui apprendere, invece, è quasi sempre buona cosa. Non a caso il mondo dell'apprendimento automatico è strettamente imparentato con quello dei cosiddetti big data: questo non significa che avere grandi moli di dati sia di per sè sufficiente per costruire modelli vincenti grazie agli algoritmi di machine learning, ma che, al contrario, quasi mai si riesce a predire con buona precisione quando i dati a disposizione sono pochi.

Per inciso, l'algorimo che ho descritto si chiama "k-Nearest Neighbors" (kNN), ed è uno dei più famosi nel campo delle tecniche di classificazione basate sull'apprendimento automatico. Nel prossimo articolo della serie scopriremo un altro algoritmo che può essere impiegato per risolvere problemi simili.

Mr. Palomar torna a giocare a dadi (al Festival della Statistica 2016)

Ricordate il gioco musicale dei dadi di Mozart?
Ebbene, se volete giocare anche a voi, e contribuire a comporre un vero valzer in forma di minuetto, con battute firmate nientemeno che dal grande Wolfgang Amadeus, dovete venire a Treviso, domenica 9 ottobre alle ore 16, e partecipare allo spettacolo "Un, due, ...re! Giocando a dadi con Mozart".
Questo appuntamento musical-matematico mi vedrà protagonista, assieme al valente pianista Giancarlo Panizzo, e fa parte del programma ufficiale del Festival della Statistica e della Demografia "StatisticAll", in programma a Treviso dal 7 al 9 ottobre prossimi.
Il pubblico potrà lanciare i dadi e comporre un valzer che sarà eseguito a prima vista da Giancarlo Panizzo: un'esecuzione mozartiana che, statisticamente, sarà in prima assoluta mondiale!
Ma non ci sarà soltanto il gioco dei dadi: molte altre sorprese di carattere musicale e matematico vi aspettano!
Il giorno prima, sabato 8 ottobre alle ore 17.30, proporremo un'anteprima dello spettacolo, e anche in quella occasione comporremo un valzer con i dadi!
Non mancate, e passate parola!

Gli enigmi di Coelum: "Quadranti galattici"

Nel 1907 Henry Dudeney, grande creatore di rompicapi e giochi matematici, propose il seguente problema: “Fate accomodare le stesse n persone a una tavola rotonda (n-1)(n-2)/2 diverse volte, in modo che nessuna persona abbia per più di una volta gli stessi due vicini”.
L’enigma venne pubblicato, assieme a molti altri, nel libro “The Canterbury Puzzles”, uno dei grandi classici della matematica ricreativa.

L’immagine della tavola rotonda richiama subito alla mente i cavalieri della corte di re Artù, menzionati nelle leggende del ciclo bretone. Nelle diverse versioni, il numero di questi nobili personaggi varia molto, da 12 a oltre 150.
A noi, però, non importa quanti fossero i cavalieri: ci basta chiamare questo numero n.

Il problema di Dudeney suggerisce che esistano (n-1)(n-2)/2 diversi modi di accomodare i cavalieri a tavola, rispettando il vincolo per cui nessuno di loro ritroverà per più di una volta la stessa coppia di colleghi ai suoi due lati. Perché proprio (n-1)(n-2)/2?
Lo possiamo comprendere facilmente.
In quanti modi possiamo riempire il posto alla destra di re Artù? Naturalmente in n-1 modi, perché possiamo collocare chiunque degli n cavalieri tranne lo stesso sovrano. E una volta occupato quel posto, quanti modi abbiamo di piazzare un commensale alla sinistra di Artù? Ovvio: n-2, perché a questo punto abbiamo già escluso 2 persone. Quindi esistono (n-1)(n-2) modi di riempire i due posti vicini all’illustre sovrano.

Ma facciamo attenzione all’esatta formulazione del problema: ciascun cavaliere non deve ritrovarsi più volte la stessa coppia di vicini, indipendentemente dal fatto che siano scambiati di posto. Di conseguenza contando (n-1)(n-2) modi abbiamo in realtà contato ogni configurazione due volte: il numero giusto è quindi (n-1)(n-2)/2.
Per fortuna la matematica è democratica, per cui il ragionamento condotto per re Artù si applica pari pari a tutti i cavalieri. Possiamo allora concludere che il numero di configurazioni proposto da Dudeney è corretto.
Il numero (n-1)(n-2)/2 può essere ricavato anche attraverso un procedimento appena diverso. Il numero di possibili disposizioni degli n cavalieri corrisponde infatti al numero di modi in cui possiamo estrarre 2 elementi da un insieme di n-1 elementi.
Chi mastica un po’ di matematica sa che questo numero è espresso dal coefficiente binomiale “n su 2”, cioè:

Per fortuna abbiamo ritrovato lo stesso numero di prima!
Vabbè: ma adesso, che ce ne facciamo di questo bel numerino? Sapere quanti sono i modi di far sedere i cavalieri non significa conoscere nel dettaglio tutte queste disposizioni.
D’altra parte la determinazione di queste configurazioni costituisce il vero rompicapo di Dudeney.
Il problema è stato risolto per qualsiasi n pari, ma non ha una soluzione generale se n è dispari. Ai tempi di Dudeney (che morì nel 1930), per esempio, non era nota alcuna soluzione per il caso n = 13, che richiama alla memoria l’ultima cena di Gesù.
Lo stesso matematico inglese descrisse in dettaglio tutte le soluzioni dell’enigma per n compreso tra 3 (numero minimo di commensali per il quale il problema ha senso) e 12.
Ad esempio, la figura seguente illustra le soluzioni (uniche) per n uguale a 3, 4, e 5.

  Dagli anni Sessanta in poi, il problema venne preso in grande considerazioni da diversi matematici e risolto per valori più alti di n, anche sfruttando algoritmi informatici.
Ad oggi, il valore più basso di n per il quale non è nota alcuna soluzione è 41: si sa che le configurazioni in questo caso sono (41-1)(41-2)/2 = 780, ma nessuno sa quali siano di preciso.

Anche se ambientato in un contesto fantascientifico e non nello scenario delle leggende anglosassoni, l’enigma del numero 180 di Moebius era una riformulazione del classico problema di Dudeney.
Al posto della tavola rotonda c’è la Via Lattea, e i commensali sono sostituiti dai settori galattici amministrati da altrettanti governatori. 

 

Con i quattro quadranti alla Star Trek la soluzione è semplice: anzi, l’avete già vista nella figura precedente.
Con n = 4 abbiamo (n-1)(n-2)/2 = (4-1)(4-2)/2 = 3 disposizioni possibili.
Ad esempio, se i governatori sono A, B, C e D, lo schema di rotazione che risolve il problema è il seguente:

A B C D

A B D C

A C B D

Si noti che in ciascuna disposizione l’ultimo governatore (quello indicato a destra) sarà vicino al primo (quello più a sinistra). Questo significa che ad esempio la prima configurazione A B C D può indifferentemente essere scritta anche come B C D A, oppure C D A B, oppure D A B C.
Tenendo conto di questo fatto, potrete constatare che con n = 4 non vi sono altre soluzioni del problema.
Con sei settori, la faccenda si fa più complicata.
Maurizio Carlino, affezionato lettore della rubrica nonché abilissimo risolutore di enigmi, ha inviato un’analisi dettagliata del problema, corredata dalla soluzione e da una spiegazione approfondita del procedimento adottato per ottenerla.
Come si risolve la parte difficile del problema, cioè lo schema di rotazione dei 6 governatori? In questo caso le possibili configurazioni sono (6-1)(6-2)/2 = 10, ma quali sono?
Trovarle “a mano” era possibile, ma non semplice. Un programma informatico sicuramente rappresentava una via più agevole, e non a caso questo è stato il procedimento scelto da Carlino.
Identificando i governatori con le prime 6 lettere dell’alfabeto, la soluzione proposta dal lettore-risolutore è la seguente:

A B C D E F

A B D C F E

A B E D F C

B D E A F C

B D F A C E

A D B F C E

A C D F B E

D C E F B A

C B E F D A

C B F A D E

Nella tabella seguente, inviataci dal nostro lettore, vengono evidenziate le coppie di vicini di ogni governatore in ciascuna delle 10 configurazioni.

Naturalmente questa è una delle molte soluzioni possibili del problema con n = 6: a differenza del caso con n = 4, infatti, la soluzione non è affatto unica.
Non contento di aver comunque risolto il problema “base”, Carlino ha analizzato il numero di spostamenti necessari per passare da una configurazione a quella successiva.
Nella soluzione esposta sopra, questo numero è sempre 3, tranne che per il primo passaggio, nel quale sono necessari 4 spostamenti. Il numero totale di spostamenti è quindi pari a 28.

Scrive Carlino:
Non sono riuscito a trovare una soluzione che presenti un numero inferiore di spostamenti, ma non dispongo di una dimostrazione matematica del fatto che 28 sia il valore minimo. Sarà molto interessante scoprire se qualcun altro è stato capace di produrre una soluzione a ‘costo’ inferiore; al momento posso solo dire che il mio algoritmo non ha trovato soluzioni inferiori a 28 con il vincolo di usare ad ogni passo una nuova configurazione che differisse dalla precedente di al più 4 spostamenti. In particolare non sono riuscito a trovare soluzioni con costo totale = 27 in cui tutte le 9 configurazioni avessero un costo pari a 3 e neppure almeno una soluzione in cui compaia una configurazione di costo 2 seppur teoricamente compatibile con i vincoli del problema.
 
Giro l’interessante sfida ai lettori e ai visitatori.

Gli enigmi di Coelum: Moebius dentro Moebius

Con molta calma e lentezza, continuo a ripubblicare su questo blog i miei giochi matematici che trovarono spazio nella prestigiosa rivista Coelum Astronomia.
Dato che per la rubrica era stato scelto il titolo "Möbius", a un certo punto ritenni appropriato dedicare uno degli enigmi al celebre nastro.
Ebbene, questo semplice quanto sconcertante oggetto, di cui ho già raccontato su queste pagine, deve il suo nome ad August Ferdinand Möbius, matematico e astronomo tedesco nato nel 1790. Appassionato di matematica, fisica e astronomia fin da ragazzo, nel 1813 August Ferdinand andò a studiare nella prestigiosa università di Gottinga, dove ebbe il grande Carl Friedrich Gauss come insegnante. Solo tre anni Möbius dopo divenne professore di astronomia e meccanica superiore a Lipsia, dove rimase fino alla morte, avvenuta nel 1868.

Il suo contributo alla matematica è molto notevole, e spazia tra la topologia, la geometria proiettiva e la teoria dei numeri. Pare che abbia affrontato il problema della colorazione delle carte geografiche prima di Francis Guthrie, che di solito viene considerato come il pioniere in questo campo. D’altra parte, il famoso anello di Möbius non è stato descritto per la prima volta da Möbius ma da un altro matematico, Johann Benedict Listing, anche lui allievo di Gauss a Gottinga.

Costruire un nastro di Möbius è semplicissimo: basta prendere una striscia di carta e unirne le estremità dopo aver sottoposto una delle due a un mezzo giro di torsione.
Lo strano oggetto che si ottiene gode di alcune caratteristiche del tutto peculiari. Se si percorre il nastro con un pennarello, partendo da un punto qualsiasi, si scopre di poter percorrere l’intera superficie. L’anello ha quindi una sola faccia! Com’è possibile? Dopo aver percorso un giro attorno al nastro, ci si ritrova dalla parte opposta.
Ma parlare di parte opposta è fuori luogo, perché di facce ce n’è una sola. Dopo aver percorso due giri ci ritroviamo al punto di partenza.

E non basta: se si prova a seguire il bordo della striscia con un dito, ci si ritrova, dopo un giro, sul bordo “opposto”. E anche qui si ha un analogo “paradosso”: non ci sono due bordi, ma un bordo unico.
La caratteristica più sorprendente del nastro di Möbius si scopre tagliando la striscia a metà, in senso longitudinale, cioè parallelamente al bordo. Ci si aspetterebbe forse di ottenere due anelli di Möbius separati, mentre ci si ritrova con un unico anello, caratterizzato però da una torsione intera, e quindi da due bordi e due superfici diverse. Con un secondo taglio si ottengono poi due nastri con torsione intera, l’uno intrecciato all’altro.
Se proviamo a tagliare la striscia a un terzo della sua larghezza, è possibile fare due giri: alla fine si ottengono due anelli concatenati, il primo caratterizzato da una torsione intera e grande la metà del secondo, che invece è un vero nastro di Möbius, con mezza torsione.
Queste meravigliose stranezze giustificano l’interesse che questo oggetto geometrico ha suscitato, non solo tra i matematici, ma anche tra gli artisti.
L’incisore olandese Maurits Cornelis Escher ha spesso utilizzato la superficie di Möbius come fonte di ispirazione per le sue opere.


L’anello di Möbius è presente anche in molte opere letterarie e cinematografiche.
Nel 2006 il divulgatore americano Clifford Pickover ha pubblicato un libro intitolato “Il nastro di Möbius” (Apogeo 2006), interamente dedicato a questa superficie geometrica, mostrandone le innumerevoli connessioni con ogni ambito dello scibile umano.
Una curiosità: fin dall’inizio degli anni Settanta il simbolo universale del riciclo è un nastro di Möbius.

E veniamo all’enigma. Come abbiamo visto, il matematico che ha dato il nome alla nostra bizzarra superficie era anche un astronomo. Ma soprattutto, se parliamo di anelli, non vi vengono in mente quelli di Saturno?
Da un punto di vista geometrico, il sistema di anelli di Saturno assomiglia a una corona circolare, in cui il bordo interno è più corto di quello esterno. Topologicamente, però, la superficie equivale alla superficie laterale di un cilindro, cioè un anello ottenuto a partire da una striscia unendo le estremità senza torsioni.
Se potessimo camminare sull’anello di Saturno, potremmo stare o sulla faccia superiore o su quella superiore, ma per passare da una all’altra dovremmo per forza attraversare uno dei bordi: poco importa che l’anello sia visualizzato com’è in realtà, cioè con un bordo più vicino al pianeta e uno più lontano, oppure come la superficie laterale di un cilindro, in cui c’è una faccia rivolta verso il pianeta e un’altra faccia esposta nel verso opposto.

Ben diversa, invece, diventa la situazione se l’anello viene chiuso effettuando la fatidica mezza torsione di una estremità: si ottiene un mostruoso nastro di Möbius attorno a Saturno, che è possibile percorrere in tutta la sua superficie senza mai attraversare il bordo.

Il citato libro di Clifford Pickover racconta di come sia possibile giocare a scacchi su un nastro di Möbius. Le regole del gioco rimangono invariate, ma occorre fare un po’ più di attenzione, perché diventano possibili alcune mosse a sorpresa: occorre immaginare infatti che uno dei lati della scacchiera sia confinante con il lato opposto, ma in modo speculare.
Pickover rivela le stranezze di un simile modo di giocare a scacchi, e descrive anche la variante (più semplice) della scacchiera ripiegata ad anello ma senza torsione.

Sulle scacchiere e con i pezzi degli scacchi si possono fare partite, ma si possono anche risolvere rompicapi. Uno di questo è famoso come “giro di cavallo”. Su una scacchiera tradizionale 8×8, si tratta di muovere un cavallo partendo da una casella qualsiasi e rispettando le regole del gioco, con l’obiettivo di visitare tutte le caselle della scacchiera, ciascuna una volta sola. Il giro del cavallo può essere chiuso, se, alla fine del suo peregrinare, il quadrupede riesce a tornare alla casella di partenza. Altrimenti il giro viene considerato aperto.
Il problema del giro di cavallo è celebre nel mondo dei rompicapi che possono essere affrontati per via algoritmica, cioè addestrando un programma informatico a risolvere l’enigma. Ad oggi, nessuno sa di preciso quanti diversi giri di cavallo aperti siano possibili su una scacchiera tradizionale.
Si può provare a risolvere il problema anche su scacchiere “esotiche”, ad esempio rettangolari, o anche su scacchiere di Möbius.

L’enigma da me proposto consiste appunto nel trovare un simile percorso su una scacchiera di Möbius di dimensioni 4 x 7, dove il lato corto (di lunghezza 4) è quello che costituisce l’estremità che si torce di mezzo giro e si unisce al lato opposto.
Come ha argutamente osservato Maurizio Carlino, uno dei lettori della rivista che seppero risolvere il problema:

(…) una scacchiera di Möbius 4 x 7 mantiene l’alternanza bianco/nero delle caselle: è un dato che non ho usato esplicitamente per risolvere il problema, ma comunque vale per una scacchiera con un numero di colonne dispari. In altri termini, ogni singola mossa cambia colore alla casella di partenza, proprio come avviene in una scacchiera classica.
Come conseguenza, dopo un numero di mosse dispari, un cavallo che si muova su una scacchiera di Möbius di ordine dispari si troverà su una casella di colore opposto di quella da cui è partito, mentre dopo un numero di mosse pari sarà su una casella di colore identico a quello di partenza.

Nel suo libro Clifford Pickover afferma che una scacchiera di Möbius di dimensioni m x n (con m file e n colonne) consente un giro di cavallo se vale almeno una delle seguenti condizioni:

    m = 1 e n > 0 oppure n = 1 e m = 3, 4 o 5
    m = 2 e n pari, oppure m = 4 e n dispari
    n = 4 e m = 3

Nella nostra scacchiera 4 x 7 abbiamo m=4 e n=7: rientriamo quindi nel caso 2) e il giro di cavallo è possibile. Una delle possibili soluzioni è illustrata nella figura seguente:

Il già citato Carlino, invece, ha affrontato il problema servendosi di un programma in linguaggio C da lui stesso sviluppato, che calcola tutti i possibili giri di cavallo su una scacchiera di dimensione m x n (con m e n non maggiori di 8) a partire da una qualsiasi posizione della scacchiera, sia essa di tipo Möbius o no. L’algoritmo è basato sulla tecnica del “backtracking”, cioè tenta di individuare le soluzioni del problema esplorando tutte le mosse raggiungibili da una certa configurazione e tornando sui propri passi nel caso incontri ostacoli insormontabili. L’approccio sfrutta il meccanismo della ricorsione, ben noto agli informatici. La complessità dell’algoritmo è esponenziale, il che significa che il tempo di calcolo aumenta molto rapidamente al crescere della scacchiera, fino a diventare inservibile sopra una certa soglia di dimensioni.

Una delle soluzioni trovate da Carlino è riportata nella figura qui a fianco.
Il suo programma  ha trovato ben 13.209.800 diverse soluzioni. Modificando l’algoritmo per farlo funzionare su una scacchiera 4 x 7 non di Möbius, le soluzioni sono solo 1.682: dato che una scacchiera classica è un caso particolare della scacchiera di Möbius, queste 1.682 soluzioni sono incluse in quelle precedenti.
Come osserva Carlino, il numero di soluzioni “classiche” molto basso rispetto a quelle möbiussiane si spiega considerando il fatto che, nella maggior parte delle posizioni su una scacchiera classica, le possibili successive mosse di un cavallo sono meno numerose di quelle che può compiere su una scacchiera di Möbius.
Riporto infine un’altra interessante osservazione di Carlino:

Per indagare le proprietà di una scacchiera di Möbius ho provato a individuare almeno una soluzione diversa per ogni possibile posizione di partenza. Ho così scoperto che il programma da me elaborato non è in grado di trovare una soluzione se il cavallo parte dalla seconda o dalla terza riga (posizioni bj e cj con j=1..7) sia nel caso di una scacchiera di Möbius che nel caso classico.
Al momento non so dire se si tratta di un’imperfezione del programma o di una caratteristica intrinseca del problema.
Riporto nel seguito una tabella che riassume il numero di soluzioni trovate con il mio algoritmo per ogni posizione di partenza, per una scacchiera di Möbius 4 x 7 e per quella classica. Mi propongo di continuare a studiare il problema variando le dimensioni della scacchiera e cercando di approfondire la questione sulle posizioni di partenza che sembrano non garantire una soluzione.

Come si vede il numero di soluzioni nel caso di una scacchiera di Möbius è lo stesso a prescindere dalla posizione iniziale, nel caso delle righe 1 e 4 (aj e dj con j=1..7): la situazione è diversa nel caso della scacchiera classica, fermo restando la condizione di simmetria.

La questione posta da Carlino sulle posizioni iniziali “sfortunate” sembra molto interessante: varrebbe la pena di studiarla per capire se si tratti di una caratteristica intrinseca e generale di questo tipo di problema.