martedì 8 ottobre 2024

Settantasette

No, non si tratta del settantasettesimo post (è il 382esimo). E oggi non è nemmeno il mio settantasettesimo compleanno (se mai ci arriverò, mi manca quasi un quarto di secolo). Come appresi anni fa da un brano intitolato Urna, settantasette, nella smorfia napoletana, rappresenta le gambe delle donne (o, in alternativa, il diavolo). Ed è pure il numero dell'armadietto situato al terzo piano dell'edificio in cui insegno quest'anno (il cosiddetto Palazzetto delle scienze, brutalista e bruttarello) in cui conservo per lo più le bottigliette d'acqua minerale che trangugio per rimandare almeno di un po' la prossima crisi di calcoli renali (quella del matematico messo KO da un calcolo è una battuta che ho già ampiamente sfruttato). 

Settantasette è però anche il più grande numero non strettamente egizio (o strettamente non egizio?), cioè non esprimibile come somma di numeri differenti la cui somma dei reciproci è pari a uno. Quest'affermazione, curiosa anche se forse non proprio epocale, fa da incipit al paper intitolato A Theorem on Partitions, pubblicato dal celebre matematico e jongleur Ron Graham nel 1963 (le partizioni e le frazioni egizie furono un tema ricorrente nei primi lavori di Graham, discepolo prediletto del grande Paul Erdös). Strettamente egizio lo è ad esempio il numero $11$: difatti vale $11=2+3+6$, e

$$\frac{1}{2}+\frac{1}{3}+\frac{1}{6}=1 \; .$$

Un piccolo trucco, documentato nel paper di Graham, permette di estendere la famiglia egizia: scrivendo

$$1 = \frac{1}2+\frac{1}{2} = \frac{1}{2}+\frac{1}{4}+\frac{1}{6}+\frac{1}{12}$$

concludiamo che pure $24=2+2\cdot11$ è suddito di Cleopatra; analogamente lo saranno $50=2+2 \cdot 24$, e poi $104$, $210$ e così via (notando, tra l'altro, che nessuna delle estensioni produce partizioni non strette, cioè contenenti addendi ripetuti). Ciò permette di estendere ad libitum la famiglia. Ed è con una tecnica analoga che Graham dimostra l'egizità (si scriverà così? Non credo...) di ogni numero superiore a 77, partendo da una tabella invero piuttosto corposa, che non dev'essere stato facile produrre nel 1963 (ma forse i Bell Labs, presso cui era impiegato Graham, in un'epoca in cui le grosse aziende non disdegnavano la ricerca di base in matematica, disponevano di infrastrutture all'avanguardia).

Bello, ma mi era rimasto un dubbio: cosa succede prima del 78? Settantasette è un'eccezione? E quante ce ne sono? È abbastanza facile mostrare che il primo numero strettamente egizio è 11, dal momento che le partizioni strette dei numeri piccoli sono poche. Ma tra 11 e 24 la situazione si complica già considerevolmente. Non è difficile concepire un algoritmo che passi al setaccio tutte le partizioni di un numero, ma le mie limitate competenze informatiche mi avrebbero richiesto parecchio lavoro per la sua implementazione. Però queste cose chatgpt le sa fare benissimo: gli ho quindi chiesto di programmare in Python una procedura per costruire le partizioni di un dato numero, scartare a priori quelle con cifre 1 o cifre ripetute, ed elencare quelle che soddisfano il criterio. L'ho poi copia/incollata in un compilatore online (come questo)... et voilà:

Qui c'è l'elenco completo delle partizioni fino a $n=89$; tra 11 e 24 non ce ne sono, e effettivamente 77 non ne possiede.

domenica 22 settembre 2024

Sei livelli...

Durante l'ormai lontano (e, speriamo, irripetibile) periodo pandemico, mi ero dilettato con un'app (non ricordo più quale) per la produzione di filmati in stop motion. In particolare, avevo animato la soluzione del gioco delle Torri di Hanoi in alcuni casi. Il caso a quattro livelli l'ho inserito nel post precedente, come .gif animata. Il caso a sei livelli è qui, e richiede 63 passaggi (la risoluzione può essere nuovamente ricondotta a una successione di Gray codes; la sequenza è riportata nel post precedente): 

giovedì 19 settembre 2024

Torri Vietnamite, codici binari e ipercubi

 


Non ricordo quando sentii parlare per la prima volta del gioco delle torri di Hanoi, il celeberrimo rompicapo inventato e commercializzato nel 1883 dal matematico Edouard Lucas, noto per le sue generalizzazioni dei numeri di Fibonacci, per il test di primalità oggi noto come Lucas-Lehmer e, appunto, per la sua passione per i rompicapi matematici, che sfociò nella pubblicazione dei quattro volumi delle Récréations mathematiques (due dei quali usciti, ahimè, postumi). Lucas dà una descrizione del gioco delle torri nel terzo volume delle Récréations, attribuendone la scoperta al fantomatico N. Claus de Siam, anagramma di Lucas d'Amiens (sua città d'origine). Ne possiedo alcune versioni, acquistate qua e là, che suscitano immancabilmente la curiosità degli studenti quando li invito a cimentarsi con il gioco. Curiosità che, ahimè, scema non appena cerco di matematizzarne le caratteristiche. Perché di matematica, con le torri di Hanoi, se ne può fare parecchia.

A un livello ancora elementare, può essere interessante ragionare sulla natura ricorsiva del gioco: in effetti la strategia ottimale per la sua risoluzione può essere riassunta dalla frase "per completare la torre a $n+1$ livelli sul terzo piolo, realizzo una torre a $n$ livelli sul secondo, sposto la base sul terzo e ci ricostruisco sopra la torre a $n$ livelli". Da qui si intuisce facilmente la formula $m(n)=2^n-1$ che permette di calcolare il numero minimo di mosse necessarie a completare gli $n$ livelli, facilmente dimostrabile per induzione. L'animazione seguente, un esperimento un po' maldestro di stop motion che risale al periodo pandemico, mostra cosa succede se $n=4$:


Un po' più stimolante è la relazione con i cosiddetti codici Gray, e in particolare con il cosiddetto reflected binary code, brevettato dal fisico dei Bell labs Frank Gray nel 1953. Si tratta di una codifica binaria dei numeri naturali, alternativa a quella "classica", non posizionale ma con un vantaggio tecnico interessante nella trasmissione dei dati: nel passaggio da $n$ a $n+1$ i codici si differenziano solo in una posizione. Eccola per i numeri da 0 a 63 (l'ho ottenuta, come tabella LaTeX, istruendo a dovere chatgpt):


La creazione dei codici si può descrivere in questo modo: partendo da $0...0$, si inverte (cioè si cambia da 0 a 1 oppure da 1 a 0)  la prima posizione partendo da destra che non riproduce un codice già usato. Quindi, per quanto riguarda ad esempio i codici a due cifre, $00$ è seguito da $01$, poi da $11$ e $10$.

Il Gray code rappresenta la strategia risolutiva nel senso seguente: ad ogni posizione del codice, da sinistra a destra, è associato un livello della torre, dal più ampio al più stretto; ad ogni transizione, si sposta (ciclicamente: $1\to2\to3\to1$ oppure $1\to3\to2\to1$) sul primo piolo disponibile il disco corrispondente alla cifra che cambia, verso destra se $n$ (l'altezza della torre) è pari, verso sinistra se è dispari.
Illustriamo il caso $n=4$, corrispondente all'animazione (le cifre sono colorate più o meno in modo corrispondente ai livelli):
 
(spostiamo (verso destra, perché $n=4$ è pari) dapprima il verde (ultima posizione), poi il blu (penultima), poi di nuovo il verde (ultima), poi il rosso (seconda), e così via).

L'uso dei Gray codes permette di scoprire un'altra, affascinante, connessione tra le torri di Hanoi e la matematica (citando l'incipit del sesto capitolo della raccolta Hexaflexagons, Probability Paradoxes, and the Tower of Hanoi, dell'inimitabile Martin Gardner, fonte primaria di ispirazione per questo post, to a mathematician few experiences are more exciting than the discovery that two seemingly unrelated mathematical structures are really closed linked): identificando un codice binario con le coordinate di un punto di $\mathbb R^n$, la successione dei codici descrive un percorso che tocca esattamente una volta ogni vertice di un $n$-cubo (un quadrato per $n=2$, un cubo per $n=3$, un tesseract per $n=4$ ecc.), senza percorrere più di una volta ogni spigolo. In altre parole, un cammino Hamiltoniano sul grafo definito dai vertici e dagli spigoli. I casi $n=2,3$ sono abbastanza immediati e banali, e per quanto riguarda l'ipercubo (che corrisponde al caso con quattro livelli) il disegno seguente (trovato online) permette di seguire il cammino da $0000$ a $1000$:


Ai Grey codes e alle loro applicazioni in campo ludico Gardner dedicò la rubrica Matematical games del numero di agosto 1972 di Scientific American (da qualche parte lo si trova in .pdf, ma non ricordo dove), soffermandosi però soprattutto su un altro popolare rompicapo. Forse un giorno (non appena avrò capito come funziona) ne parlerò anche qui.

giovedì 18 luglio 2024

Letture...

  • Sofia Kovalevskaja - Vita e rivoluzioni di una matematica geniale. Una graphic novel scritta e disegnata dalla fumettista Alice Milani, autrice anche delle biografie di Marie Curie, Wislawa Szymborska e di don Lorenzo Milani (prozio dell'autrice, tra l'altro). Il tratto e lo stile volutamente "young adult" nascondono un'opera senz'altro degna di nota, in cui è evidente la ricerca seria e documentata. La lettura rappresenta un modo non convenzionale per approcciarsi ad una delle più notevoli figure di matematiche, la cui importanza è seconda forse soltanto a quella dell'immensa Emmy Noether. Il risultato più noto della Kovalevskaja è senz'altro il Teorema di Cauchy-Kovalevskaja, fondamentale per giustificare esistenza e unicità della soluzione di un sistema di equazioni alle derivate parziali (Cauchy ne dimostrò soltanto un caso particolare), la cui formulazione originale può essere apprezzata qui in tutta la sua genialità.
  • Il Teorema di Pitagora, di Paolo Zellini. È incredibile quanto si possa scrivere a proposito dell'enunciato probabilmente più noto e scontato dell'intera geometria. Qui l'autore è convincente nel mostrarci come il "teorema" per antonomasia abbia navigato nel flusso di idee che, prendendo le mosse (almeno) dalla matematica babilonese e vedica, l'hanno condotto fino ai giorni nostri attraversando la matematica egizia, greca, cinese e indo/araba, in un ciclo continuo di riscoperta e re-interpretazione. Zellini, che di formazione è matematico ma nelle sue opere ama soffermarsi sull'evoluzione del pensiero scientifico, anche in questo caso affianca a considerazioni di carattere più tecnico (che sconfinano nella teoria dei numeri e soprattutto nell'analisi numerica, il suo campo d'indagine primario) digressioni di carattere più filosofico, in particolare relativi al crescere e al divenire, e quindi all'infinito, tema già al centro di altre sue opere divulgative.
  • Mathematics and Its History, di John Stillwell. Parlarne in poche righe è quasi offensivo per un'opera di questa portata. Un libro monumentale, di matematica più che di storia della matematica. Tecnicamente si tratta di un Undergraduate Text, e può essere letto con competenze matematiche abbastanza standard, ma forse può essere apprezzato veramente solo da chi la materia l'ha già almeno un po' approfondita. Va percorso con calma, magari solo a sprazzi, o su un arco di tempo abbastanza lungo (l'ho centellinato nel corso di alcuni mesi), magari anche dando un'occhiata agli esercizi (che, confesso, io ho risolto solo in minimissima parte, già soddisfatto dal contenuto del libro). Ogni capitolo può essere letto singolarmente, e rappresenta un "mini-saggio" a se' stante. È praticamente impossibile riassumerne il contenuto, dal momento che tocca tutti i principali momenti della matematica, dalle "terne Pitagoriche" (ancora loro) della matematica babilonese alla teoria di Ramsey. Insomma, un libro che ogni cultore della matematica dovrebbe leggere.
  • MANIAC, di Benjamin Labatut. Un sorta di sequel di Quando abbiamo smesso di capire il mondo,  a mio avviso ben più riuscito, perché in questo caso l'autore evita i voli di fantasia che avevano contraddistinto l'opera precedente. Il libro si apre con un brevissimo saggio dedicato alla tragica vicenda di Paul Ehrenfest, che mise fine alla sua vita e a quella del figlio disabile, tormentato dalla depressione e dall'ascesa del nazismo. I capitoli centrali, che costituiscono un libro a se', sono tutti dedicati a John von Neumann ("l'essere umano più intelligente del novecento", per alcuni). Lo stile adottato è quello della narrazione da parte di una serie di testimoni della sua inarrestabile ascesa, dai suoi familiari più stretti a esponenti della cultura (o di una delle due?) novecentesca, tra cui spiccano Eugene Wigner (quello dell'irragionevole efficacia), Richard Feynman e Oskar Morgestern. Un piccolo spazio è pure dedicato al tormentato Nils Barricelli, pioniere nel campo degli algoritmi genetici i cui contribuiti sono per lo più caduti nel dimenticatoio. Il MANIAC che dà il titolo al libro è il pionieristico calcolatore costruito seguendo l'architettura progettata da Von Neumann. Impiegato principalmente nello studio dei processi termonucleari, fu anche la prima macchina a sconfiggere un essere umano a scacchi, anche se in una versione limitata (6x6, senza alfieri). Ben più bruciante fu invece la sconfitta patita a go, gioco ben più complesso degli scacchi, da parte del campionissimo Lee Sedol, il protagonista dell'ultima parte del libro, contro un algoritmo basato sull'IA, AlphaGo, sviluppato dai laboratori DeepMind. Si trattò di un evento clamoroso, che se da un lato stimolò lo sviluppo di nuovi stili per l'antichissimo gioco, dall'altro iniziò a far intravedere la portata della rivoluzione innescata dall'inarrestabile ascesa dell'IA.

venerdì 21 giugno 2024

Jack Reacher e il barone di Münchhausen

Sembra quasi che la matematica mi insegua anche quando cerco di starle lontano.

A volte, specialmente in periodi un po' estenuanti come quello appena trascorso, per dare un po' di tregua a qualche neurone, metto al bando la suspension of disbelief e mi immergo nella lettura di qualche "romanzo di genere". Fra gli autori che più frequento c'è l'inglese Lee Child, che con il personaggio di Jack Reacher ha ideato una figura di eroe/antieroe non proprio credibile ma quasi (tra l'altro, ben resa dall'imponente Alan Ritchson nella serie prodotta da Amazon, e un po' meno dal più mingherlino Tom Cruise, a cui mancano una ventina di centimetri per essere credibile nel ruolo). La saga conta al  momento 29 volumi, gli ultimi dei quali scritti da Child in collaborazione con il fratello minore Andrew, destinato a breve a prendere definitivamente in mano le redini del personaggio.

Al di là di qualche aspetto caratteriale un po' borderline, a Jack Reacher non manca proprio nulla: è intelligentissimo, fortissimo e resistente, imbattibile nel corpo a corpo, generoso, amatore sopraffino, non puzza nonostante non si lavi quasi mai, ha una sorta di orologio interno incorporato che gli permette in ogni istante di conoscere l'ora esatta, e ne capisce pure di matematica. Già; anche di matematica; infatti, leggendo il diciannovesimo romanzo (Punto di non ritorno, fonte di ispirazione per il secondo dei due lungometraggi), mi sono imbattuto in quanto segue:


In effetti, è facile verificare che
$$3^3+4^4+3^3+5^5=3435 \quad.$$

Joseph Madachy (che in realtà fu proprietario, editore e direttore del Recreational Mathematics Magazine, ma soltanto editore del successivo Journal of Recreational Mathematics) menzionò questo fatto in un articolo contenuto nella raccolta Mathematics on Vacation (non difficilissima da reperire online) dedicato a quelli che lui battezzò numeri narcisisti (ossia innamorati di se stessi).
Il numero 3435 fa parte della (minuscola) successione dei numeri di Münchhausen (OEIS A046253) che elevano se stessi ("raise themselves"), come fece il personaggio creato dalla penna di Rudolf Eric Raspe nel 1785 (ispirato a un nobile tedesco realmente esistito), che nel romanzo a lui dedicato liberò se stesso e il suo cavallo da una palude grazie soltanto alla forza delle sue braccia, sollevandosi per la treccia dei suoi capelli.
Ah, e inoltre vale $34+35=69$, come ci spiega Ariana Grande nell'omonimo, scandalosissimo brano omonimo (contenuto, guarda un po', in un album intitolato Positions; più esplicito di così...)