Archivi categoria: matematica_light

Wordle: teoria e pratica

which could be the solution?

Forse Wordle non ha più l’hype di un paio d’anni fa, ma continua a esserci un nutrito gruppo di fedeli giocatori. Ed è ovvio che i giocatori si interrogano su quale sia la strategia migliore di gioco. Così il New York Times, che si è comprato i diritti del gioco, ha creato Wordlebot, che analizza la partita che abbiamo giocato e mostra come lui avrebbe fatto di meglio. Tra l’altro, con il 2024 Wordlebot ha cambiato la parola iniziale da lui usata: non più SLATE ma TRACE.

Però Wordlebot non usa tutte le possibili parole inglesi di cinque lettere, 12974, ma solo un loro sottoinsieme che comprende quelle che sono effettivamente soluzioni possibili (2309) oltre a un paio di migliaia di altri termini. In Wordle infatti l’elenco delle soluzioni contiene solo quelle che dovrebbero essere le parole inglesi più comuni: che sia vero o no non lo so, posso solo dire che a volte devo cercare sul vocabolario il significato del risultato. Cosa succederebbe se il bot avesse a disposizione tutte le parole possibili e dovesse cercare una soluzione? Qui ci viene in aiuto la teoria dell’informazione, che ci permette di dare una misura quantitativa (l’entropia) alla nostra conoscenza. Più l’entropia è alta, più informazione abbiamo in media. La prima scelta migliore pare essere SOARE (arcaico per “giovane falco”), che ha circa 5,89 bit di entropia. Questo valore significa che dopo averla giocata il numero medio di possibili soluzioni si riduce di un fattore 25,89, anche se c’è chi afferma che ROATE sia meglio. Mi stupisce solo che questo acronimo sia presente tra le possibili parole inglesi… Da qua si può andare avanti a cercare una seconda parola. Se non possiamo sapere in anticipo il nostro punteggio con il primo tentativo, dopo SOARE si dovrebbe usare THILK (altra parola arcaica che può significare “this” o “that”) che aggiunte 4,11 bit di entropia; ma a questo punto esistono altre coppie leggermente migliori – so che una comincia con SLANE ma non so qual è la seconda parola.

Tutto bellissimo, ma c’è un ma. Un computer non ha problemi a scegliere quelle parole e verificare a una a una le scelte rimanenti. Noi esseri umani non vogliamo certo ricordarci a memoria tutto l’albero di combinazioni possibili a seconda del risultato del primo nostro tentativo; quindi sceglieremo una parola diversa, subottimale ma più semplice da gestire. Al momento per esempio il mio primo tentativo è STARE, che non sarà il massimo ma è abbastanza buona. La morale di tutto ciò? Ricordarsi che va bene la competizione, ma dovremmo ricordarci che in fin dei conti stiamo giocando, e non val la pena perdere tutto il divertimento!

AlphaGeometry

una dimostrazione di AlphaGeometry (dal sito di Google DeepMind) A quanto pare, DeepMind ha colpito ancora. Il progetto di ricerca sull’intelligenza artificiale di Google ha costruito un software, AlphaGeometry, in grado di risolvere i problemi delle Olimpiadi di geometria quasi a livello delle medaglie d’oro assegnate (quindi, se non vado errato, al livello del 10% migliore dei partecipanti).

La cosa più interessante è però almeno a mio parere l’approccio scelto: AlphaGeometry non usa un linguaggio naturale ma uno altamente specializzato che da un lato è più facilmente parsificabile da un computer e dall’altro è leggibile (da un matematico, claro). Questo vuol dire che non solo ha spesso dato le risposte corrette (25 su 30 problemi del test), ma che le ha date in modo “matematico” e non tirando a indovinare come spesso pare capitare nei sistemi di AI. È vero, come si legge per esempio nell’articolo che gli sviluppatori hanno pubblicato su Nature, che il dominio della geometria piana euclidea è molto specifico e quindi è più facile trovare un modello che dia risposte corrette, ma credo che questo sia un passo avanti molto importante nel creare software davvero intelligenti.

(immagine dal sito di DeepMind)

Esistono oscillatori di tutti i periodi in Life

Immagino e spero che conosciate tutti Life: il “gioco” (uso le virgolette perché non c’è nessun vero giocatore: una volta decisa la configurazione di partenza il prosieguo è ) ideato da John Horton Conway in cui si vede evolvere una configurazione di caselle in un campo quadrettato infinito. Ciascuna “cella” (quadretto) può essere “viva” (colorata di nero) o “morta” (colorata di bianco), e ha otto vicini (le celle che hanno almeno un punto di contatto con quella di partenza). A ogni “generazione” le celle che hanno meno di due oppure più di tre vicini muoiono; quelle con due o tre vicini continuano a vivere, e nelle posizioni con esattamente tre vicini vivi nasce una nuova cella. In Life si può costruire praticamente di tutto: è stato infatti dimostrato che è equivalente a una macchina di Turing.

blocco in Life  oscillatore in Life  ape operaia in Life

Alcune configurazioni hanno la caratteristica che ritornano allo stato iniziale dopo un certo numero di generazioni; la configurazione viene detta oscillatore e il numero di generazioni che riporta alla configurazione iniziale è detto periodo dell’oscillatore. Qui sopra vedete un blocco (che ha banalmente periodo 1), un semaforo (periodo 2: a ogni generazione ci sono tre celle vive, o in orizzontale o in verticale), e un’ape operaia (periodo 9). Se cliccate sui link potete vedere come le configurazioni evolvono.

Una domanda che ci si può porre è se esistano oscillatori di un qualunque periodo. Dovrebbe essere evidente che basta verificare la cosa per i periodi che sono una potenza di un numero primo: se un numero è esprimibile come il prodotto di due fattori primi tra loro basta partire con le due configurazioni corrispondenti poste sufficientemente lontane tra di loro perché non interagiscano. Resta comunque un numero infinito di configurazioni originali da trovare: la situazione si sbloccò nel 1996, quando David Buckingham mostrò che era possibile trovare un oscillatore che poteva essere modificato per generare un qualunque periodo maggiore o uguale a 61. Nel 2013 il limite è sceso a 43, grazie a Mike Playle e al suo Snark Loop che poteva essere banalmente modificata per generare un qualunque periodo maggiore o uguale a 43.

Restavano dunque da riempire solo alcuni buchi, e lo scorso dicembre alcuni ricercatori hanno pubblicato un articolo dove mostrano gli ultimi due oscillatori mancanti, di periodo 19 e 41. Tutto questo è stato reso possibile dalla teoria – nuovi metodi di ricerca – e dalla pratica, vale a dire computer molto veloci per testare le configurazioni. È sempre bello quando un problema viene risolto definitivamente, no?

(immagini da Conway’s Life)

Ultimo aggiornamento: 2024-02-09 10:16

Meglio perdere che vincere?

un podioSei amiche (Ada, Bea, Cleo, Dina, Eli, Fede) giocano spesso a tennis nel campetto del condominio dove abitano. Dato che la loro forma fisica varia nel tempo e non sempre possono esserci tutte, hanno ideato un metodo per stilare una classifica relativa che si aggiorna a ogni gara. Partendo dall’ultima partita giocata e andando a ritroso, si prepara un ordine parziale dato dalle partite giocate: se una di queste partite non è coerente con l’ordine finora trovato viene scartata perché rispecchia un momento passato. Per fare un esempio pratico, immaginiamo che ci siano solo quattro amiche e le partite giocate siano state nell’ordine le seguenti, dove le lettere corrispondono alle amiche e la prima nella coppia dica chi ha vinto: CD, CA, BD, BC, AB. Andando a ritroso, abbiamo le seguenti classifiche parziali: AB, ABC, la coppia ABC / ABD (non sappiamo ancora ordinare C e D), una partita non considerata perché A è davanti a C, ABCD. Supponiamo che la partita successiva sia B contro D; se B vince non succede nulla, se vince D passerà davanti a B e si ricalcolerà tutta la classifica.

Questo metodo di stabilire una gerarchia è forse un po’ scomodo, ma parrebbe abbastanza equo, oltre ad avere il vantaggio di essere indipendente dal numero di partite giocate. Ma esistono dei casi in cui a una delle amiche conviene perdere una partita per migliorare la propria posizione in graduatoria, come Stan Wagon ha mostrato in uno dei suoi Problem of the Week!

Immaginiamo che siano state giocate le seguenti partite, sempre con la stessa convenzione che la vincitrice è la prima indicata nella coppia: BC, FA, BD, AB, FD, DE, CD, CF, EF. Calcoliamo ora l’ordine, partendo sempre dall’ultima partita e indicando tra parentesi qual è la partita considerata:

  • (EF) EF
  • (CF) EF e CF
  • (CD) EF, CF, CD
  • (DE) CDEF
  • (FD) partita scartata
  • (AB) CDEF e AB
  • (BD) CDEF e ABDEF
  • (FA) partita scartata
  • (BC) ABCDEF

Supponiamo ora che la partita successiva sia C contro E. Se C vince, la classifica rimane la stessa, e C resta terza. Cosa succede se E vince? La striscia di partite è ora BC, FA, BD, AB, FD, DE, CD, CF, EF, EC. Ricalcoliamo la classifica:

  • (EC) EC
  • (EF) EC e EF
  • (CF) ECF
  • (CD) ECD e ECF
  • (DE) partita scartata
  • (FD) ECFD
  • (AB) ECFD e AB
  • (BD) ECFD e ABD
  • (FA) ECFABD

Come vedete, anche se Cleo ha perso è passata in seconda posizione! Meglio ancora: Fede, che era ultima in classifica e non ha giocato l’ultima partita, è balzata in terza posizione… Morale della favola: ogni classifica totale distorce i valori in campo, ma ce ne sono alcune che li distorcono di più!

(immagine di firkin, da OpenClipArt, CC0)

Il principio dei cassetti – risposte ai problemi

La scorsa settimana ho parlato del principio dei cassetti e vi ho lasciato tre problemi. Se non siete riusciti a risolverli ecco qua come si fa.

I 15 cavalieri della tavola rotonda hanno pasteggiato un po’ troppo prima di sedersi a discutere, e quando si sono seduti nessuno di essi era seduto al proprio posto. Dimostrate che è possibile ruotare la tavola in modo che ci siano almeno due persone al posto corretto.

Per ciascun cavaliere calcoliamo di quanti posti in senso orario è spostato rispetto alla posizione che dovrebbe avere. Visto che sappiamo che nessuno è al suo posto, a ciascuno di loro sarà assegnato un numero da 1 a 14. Ma i cavalieri sono 15: per il principio dei cassetti due cavalieri devono avere lo stesso numero. Basterà allora ruotare la tavola in senso antiorario di quel numero di posizioni perché loro due siano al loro posto.

Se scegliete sei numeri interi tra 1 e 999 ce ne saranno almeno due la cui differenza è un multiplo di 5.

In questo caso il 999 è una falsa pista: quello che conta è che i numeri sono interi. Calcolate i resti modulo 5 dei sei numeri: possono essere solo 0, 1, 2, 3 e 4. Essendoci sei numeri e cinque possibili resti, per il principio dei cassetti due di essi devono avere lo stesso resto, e quindi la loro differenza sarà un multiplo di 5.

Avete una bilancia a due piatti e 28 monete, una delle quali è più pesante delle altre. Dimostrate che non è possibile trovare quale sia la moneta più pesante con tre pesate.

In questo caso si usa il principio dei cassetti in una forma leggermente diversa da quella standard. Ogni pesata ha tre esiti possibili: il braccio sinistro è più pesante, il braccio destro è più pesante, la bilancia resta in equilibrio. Qualunque combinazione di monete si scelga di pesare ci sarà la possibilità che la moneta più pesante sia in un gruppo di almeno dieci monete; nell’ipotesi migliore 27 monete possono essere assegnate a nove a nove ai tre esiti, ma la ventottesima creerà un gruppo da 10. Con lo stesso ragionamento la seconda pesata lascerà la possibilità che la moneta più pesante sia in un gruppo da 4, ed evidentemente la terza pesata non potrà trovare con certezza la moneta pesante perché gli esiti possibili sono solo tre. Attenzione: questo ragionamento non dimostra che sia sempre possibile trovare la moneta pesante in un gruppo da 27 (nella pratica lo è, ma occorre trovare un modo per suddividere le possibilità in modo uniforme tra i tre esiti), ma è semplicemente una dimostrazione di impossibilità.

Ultimo aggiornamento: 2024-01-06 17:15

Il principio dei cassetti

Il principio dei cassetti è uno degli strumenti più usati nei giochi matematici, ma anche nella matematica “seria”. La sua formulazione, almeno per come viene di solito riportata in Italia (anche Wikipedia lo definisce così) è la seguente: “se abbiamo una cassettiera con n cassetti, in qualunque modo ci mettiamo dentro n+1 oggetti possiamo essere certi che almeno un cassetto conterrà almeno due oggetti”.

Dimostrare il principio dei cassetti è così facile che sembra che ci sia qualcosa sotto. Numeriamo gli oggetti da 1 a n+1, prendiamo i primi n e li mettiamo in un cassetto, evitando di metterne due nello stesso cassetto sennò abbiamo perso. Alla fine l’ultimo oggetto rimasto deve andare da qualche parte, ma tutti i cassetti sono occupati.

Uno dei problemi più noti che sfruttano il principio dei cassetti è quello di mostrare come a Roma ci siano due persone con lo stesso numero di capelli. La dimostrazione consiste nello stimare il massimo numero di capelli che può avere in testa una persona, verificare che è minore del numero di abitanti nella capitale, e applicare il principio dei cassetti. Questo è però un classico caso di problema malposto: la soluzione è anche corretta, ma basta passarsi la mano in testa e con ogni probabilità vi rimarrà qualche capello (a meno che non siate calvi…) e quindi non esiste un momento in cui si possa stabile quali siano le due persone co-tricotiche. Ma anche nome e attribuzione del problema fanno una certa confusione!

Peter Gustav Lejeune Dirichlet usò il principio in un suo lavoro del 1842 sulle equazioni di Pell (equazioni quadratiche di cui si cercano le soluzioni intere), e in molte nazioni soprattutto nell’Europa dell’est si parla infatti di principio di Dirichlet oppure di principio dei cassetti di Dirichlet. Non che lui gli avesse dato un nome, ritenendo evidentemente la cosa troppo banale; solo in seguito l’ha chiamato “Schubfach Prinzip” che sta appunto per “principio del cassetto” (singolare). Pat Ballew riporta però un’attestazione precedente – e fin qui nulla di strano, vista l’ovvietà del principio – in un’opera inaspettata: i Portraits littéraires di Charles Augustin Sainte-Beuve, che riporta l’esempio dei capelli e lo fa risalire a Pierre Nicole, giansenista contemporaneo di Pascal che a sua volta l’avrebbe preso da Jean Leurechon.

Nel mondo anglosassone la parola “Schubfach” (o l’equivalente francese “tiroir”) è stata resa con “pigeonhole” perché quello era il nome delle strutture con tanti piccoli spazi dove mettere le buste, che magari avete ancora visto alla reception di un vecchio albergo. Solo che poi chi come noi l’inglese non lo mastica tanto bene ha preso il significato letterale, e adesso si sente parlare del principio della piccionaia. Considerata la quantità di deiezioni dei pennuti, preferisco continuare a parlare di cassetti…

Se volete verificare di aver compreso bene il principio, eccovi tre problemi.

  • I 15 cavalieri della tavola rotonda hanno pasteggiato un po’ troppo prima di sedersi a discutere, e quando si sono seduti nessuno di essi era seduto al proprio posto. Dimostrate che è possibile ruotare la tavola in modo che ci siano almeno due persone al posto corretto.
  • Se scegliete sei numeri interi tra 1 e 999 ce ne saranno almeno due la cui differenza è un multiplo di 5.
  • Avete una bilancia a due piatti e 28 monete, una delle quali è più pesante delle altre. Dimostrate che non è possibile trovare quale sia la moneta più pesante con tre pesate.

Un’ultima cosa. Naturalmente il principio dei cassetti non vale se i cassetti sono infiniti: se abbiamo una fila infinita di cassetti numerati 1, 2, 3, 4, … e prendiamo gli ℵ0+1 numeri pari con in più 1, possiamo lasciare quanti buchi vogliamo. Ma c’è anche chi ha affermato che il principio è violato nella fisica quantistica, e possiamo avere tre particelle in due scatole senza che nessuna particella contenga più di una particella. Si direbbe ovvio che uno degli autori del paper faccia di cognome Colombo :-). Purtroppo però a quanto pare l’interpretazione data dagli autori di quell’articolo sembra errata…

(immagine da FreeSVG)

Un LLM più bravo degli umani nei problemi matematici?

Il mio amico Ugo mi segnala questo articolo di Nature con il titolo piuttosto allarmistico “DeepMind AI outdoes human mathematicians on unsolved problem”. Ho letto l’articolo e direi che l’affermazione è un po’ esagerata, o meglio non è poi una novità così importante. Come mai?

Comincio a spiegare di cosa si sta parlando. Set, anzi SET, è un gioco di carte, con un mazzo di 81 carte (34) che hanno immagini con quattro caratteristiche (numero elementi, forma, colore, riempimento), ciascuna presente in tre versioni diverse. Un set è un insieme di tre carte dove ogni caratteristica è presente sempre nella stessa versione oppure in tutte e tre le versioni possibili. Nella figura abbiamo tre numeri, tre colori, tre forme e tre riempimenti e quindi c’è un set; ma se i rombi e i rettangoli arrotondati fossero stati due anziché 1 e 3 rispettivamente avremmo comunque avuto un set.

Ora, è stato dimostrato che se si prendono 21 carte si è certi di trovare almeno un set, ma con 20 carte potremmo non averne alcuno; pertanto 21 è il numero minimo di carte necessarie. Come sapete, i matematici amano generalizzare le domande, e quindi si sono chiesti qual è il numero minimo di carte necessario in un (teorico…) mazzo con n caratteristiche, e quindi 3n carte. (L’articolo scrive “3n” perché nessuno sta lì a controllare che non si perdano gli esponenti). Questa domanda in generale non ha ancora risposta per n>6, e sono solo noti limiti superiori e inferiori (in parole povere: sappiamo che per un certo n il numero minimo di carte è maggiore o uguale a un certo k e minore o uguale a un altro K, con k<K). Cosa hanno fatto quelli di Google DeepMind? Hanno addestrato un LLM, chiamato FunSearch (il “Fun” non sta per “divertimento” ma per “funzione”: insomma l’LLM lavora sullo spazio delle funzioni) e gli hanno chiesto di scrivere dei brevi programmi di computer che generano insiemi di carte per cui non è possibile costruire un set. Molti di questi programmi non possono girare perché hanno errori di sintassi, ma essi vengono eliminati da un altro programma; quelli “buoni” sono stati fatti girare e hanno trovato un insieme di carte 8-dimensionale che è più grande del limite inferiore noto fino ad ora. Insomma, l’LLM ha generato un risultato matematico nuovo.

(Per chi vuole qualche informazione in più, dal paper si legge che il compito è stato riscritto in modo equivalmente come una proprietà di grafi; direi che la scelta di avere un programma generatore è legata al fatto che in questo modo la complessità della generazione di una configurazione cresce molto più lentamente al crescere di n e quindi è trattabile algoritmicamente. Infine, è chiaro che per quanto il risultato finale sia importante non c’è nessuna garanzia che quanto trovato sia il valore esatto, e nessuno se lo sarebbe aspettato.)

Qual è il mio pensiero al riguardo? Per prima cosa sgombro il campo da un possibile equivoco: che l’LLM di suo generi programmi non eseguibili è un non-problema, fintantoché esiste un modulo automatico distinto che se ne accorge e li butta via (e moduli come questo sono a disposizione da una vita). Anch’io se dovessi scrivere un programma su carta rischio di fare errori di sintassi :-) La parte che trovo davvero interessante nell’approccio proposto è proprio quella: avere un sistema integrato che riceva un input in linguaggio naturale e controlli automaticamente la validità delle proprie risposte. Potrebbe anche essere interessante il fatto che l’LLM abbia generato tra le tante euristiche per trovare questi set qualcuna che non era mai venuta in mente agli esseri umani. Però resto sempre dubbioso sul definirlo un breakthrough e non semplicemente un miglioramento sulle tecniche che si usano da decenni, come per esempio gli algoritmi genetici che hanno anch’essi un comportamento impredicibile a priori. Certo, gli autori dell’articolo si affrettano ad aggiungere che a differenza dei soliti LLM qui abbiamo un’idea (il programma generato) di come abbia lavorato l’algoritmo, ma di nuovo mi sembra che stiamo mischiando due livelli diversi.

In definitiva, io aspetterei ancora un po’ prima di gioire o fasciarmi la testa…

(Immagine di carte SET di Miles, su Wikimedia Commons, Public Domain)

Ultimo aggiornamento: 2024-01-06 17:23

La base fattoradicale (II)

permutazioni di quattro elementi come codice di Lehmer

La settimana scorsa abbiamo visto come si scrive la base fattoradicale. Un paio dei miei ventun lettori si è chiesto come mai si usa anche la posizione relativa a 0!, che tanto è sempre 0 e quindi non porta informazione. In effetti potete trovare anche la rappresentazione senza questa cifra; ma ho preferito lasciarla per poter ampliare il conto ai numeri frazionari. L’estensione ha comunque qualche problema, perché (-1)!, (-2)! e così via non sono definiti; quello che si fa in pratica è usare gli inversi dei fattoriali, 1/1, 1/2, 1/6, 1/24, …, 1/n!, …; chiaramente anche la prima cifra dopo la virgola è sempre zero, e quindi se avete proprio bisogno di spazio potete toglierla insieme alla cifra immediatamente a sinistra. Basta che avvisiate. Già che ci sono, aggiungo un’altra notazione: come potete immaginare, numeri molto grandi (o numeri frazionari molto lunghi) possono usare cifre maggiori di 10. Per evitare di inventare simboli, si possono usare i numeri in base 10 e separare le “cifre” con un “:”; pertanto 2441010! si può anche scrivere come 2:4:4:1:0:1:0!.

La conversione in base fattoradicale permette anche di numerare in ordine intelligente le permutazioni di n elementi. Qual è per esempio la 2023-ma permutazione di sette elementi? Scriviamo gli elementi come {0,1,2,3,4,5,6} e leggiamo da sinistra a destra 2441010!. La prima cifra è un 2; contiamo fino a due (partendo da zero, qui siamo informatici più che matematici) e tiriamo fuori il numero trovato, che è 2. I nostri elementi restano quindi {0,1,3,4,5,6}. Proseguiamo in questo modo: dalla nuova lista contiamo da 0 a 4, troviamo 5 e lasciamo {0,1,3,4,6}; poi prendiamo 6 e lasciamo {0,1,3,4}, prendiamo 1 e lasciamo {0,3,4}, prendiamo 0 e lasciamo {3,4}, prendiamo 4 e lasciamo {3} e infine prendiamo 3. (Visto che avere la posizione zero può servire?). Mettendo insieme i numeri otteniamo la permutazione {2,5,6,1,0,4,3). L’unicità della rappresentazione fattoradicale ci assicura che in questo modo troveremo tutte e sole le permutazioni possibili.

Un altro esempio di uso dei numeri fattoradicali (stavolta senza la cifra finale) è dato dai codici di Lehmer; come vedete nella pagina di Wikipedia relativa, questi codici tanto per cambiare codificano le permutazioni di n elementi, ma questa volta lo fanno per mezzo delle inversioni, cioè gli scambi di due elementi. Se date un’occhiata alla tabella, le colonne le r consistono proprio nei numeri fattoradicali scritti da destra a sinistra, e la somma delle “cifre” è proprio il numero di inversioni necessarie per partire dalla permutazione di base {1,2,3,4} per arrivare a quella voluta.

Evelyn Lamb afferma che questo può servire anche per il problema dei bagni chimici ai festival musicali britannici, come da video di Numberphile; a me non sembra, ma tant’è. Ad ogni modo, buon divertimento!

(figura di Tilman Piesk da Wikimedia Commons, CC-BY-SA 3.0)

Ultimo aggiornamento: 2025-07-27 22:42