Nel labirinto delle pile di monete: il viaggio inatteso del teorema di Erdős | Festina Lente - Notizie, recensioni e approfondimenti sull’intelligenza artificiale | Turtles AI

Una sequenza astratta di pile di monete, un antico teorema su sottosequenze monotone, un’interpretazione in termini di “gioco” Alice–Bob: la congettura che la frazione garantita fosse esattamente 1/√n — o più precisamente c(k²)=1/k — ha attraversato decenni di intuizioni e calcoli, per emergere ora grazie al dialogo tra ricercatori, letteratura e strumenti di AI.

Punti chiave:

• Il punto di partenza è il classico Erdős–Szekeres theorem: ogni sequenza sufficientemente lunga di numeri reali distinct contiene una sottosequenza monotona crescente o decrescente.
• Il problema “1026” interpreta quell’idea in chiave ponderata: dare una sequenza di “pile” di monete (x₁, …, xₙ), Alice le distribuisce, Bob prende una sottosequenza monotona e cerca di massimizzare il numero di monete raccolte  definendo così c(n).
• Costruzioni “campione” (pile quasi uguali, disposte in modo tale da forzare sottosequenze corte) mostrano che c(n) ≤ (1+o(1))/√n; d’altra parte, argomenti legati a decomposizioni in sequenze monotone (come la variante di Hanani) danno un limite inferiore c(n) ≥ (1/√2 − o(1))/√n. 
• La recente (presunta) risoluzione della congettura c(k²)=1/k — tramite uno strumento di AI che formalizza la dimostrazione in linguaggio da theorem prover — testimonia come la combinazione di idee classiche, letteratura, collaborazione aperta e automazione possa riattivare questioni “dormienti”.

Immagina di trovarsi di fronte a un gioco antico eppure ancora aperto: Alice e Bob, una pila di monete, e la libertà di sistemarle in gruppi di dimensioni a piacere. Alice cerca di disperdere il valore, Bob cerca di raccoglierne una buona frazione. Il problema, in apparenza semplice, è: quanto può Bob essere sicuro di raccogliere, in funzione di quante pile (n) vengono create?

Negli anni, era noto che se la sequenza di pile risultante è abbastanza lunga e più precisamente almeno k² + 1 elementi  allora il famoso teorema di Erdős–Szekeres assicura che esiste una sottosequenza monotona di lunghezza k+1: monotona cioè crescente o decrescente. Ma tale risultato non basta per dire molto su quanto “peso” (somma delle x_i) si possa garantire per Bob: qui entra in gioco un’interpretazione ponderata del problema.

Nella reinterpretazione, le x_i rappresentano le dimensioni delle pile di monete: la somma delle x_i è N, il totale di monete. Bob sceglie una sottosequenza monotona e prende tutte le monete in quelle pile. Se Alice è scaltra, come deve distribuire le monete per minimizzare quello che Bob può garantire? E quanto vale la frazione c(n) = min₍distribuzioni₎ max₍sottosequenze monotone₎ (monete raccolte) / N ?

Alcune costruzioni mostrano che, dividendo in ~k² pile in modo quasi uniforme e alternando ordinamenti, Alice può costringere Bob a prendere non più di una frazione ~1/k = 1/√n delle monete. In questo modo si ottiene c(n) ≤ (1 + o(1))/√n. Contemporaneamente, grazie a risultati di tipo decomposizione in sottosequenze monotone, da un’idea attribuita anche a Hanani, si può dimostrare che c(n) ≥ (1/√2 − o(1))/√n. 

Per decenni, la crescita esatta di c(n)  o almeno il limite asintotico di √n · c(n)  è rimasta aperta, un po’ per il carattere ambiguo dell’interpretazione combinata con ponderazioni, un po’ per la complessità intrinseca: le possibili partizioni in sottosequenze monotone crescono rapidamente, e un’analisi esaustiva sembrava impraticabile. Alcuni valori di c(n) furono calcolati a mano per n piccoli: ad esempio c(1)=1, c(2)=1, c(3)=2/3, e così via; per n piccoli, Bob può garantirsi le due pile più grandi, ma oltre un certo punto il gioco diventa “disperdente”.

Poi, nel dicembre 2025, secondo il racconto, la vicenda ha conosciuto un’improvvisa accelerazione. Un ricercatore, usando un sistema di AI addestrato per analisi matematica formale, ha codificato il problema: ha interpretato la congettura c(k²)=1/k come equivalente a un problema di “impacchettamento di rettangoli”. In tale versione, le pile diventano rettangoli  o più precisamente intervalli proporzionali alle x_i  e la ricerca di una sottosequenza monotona corrisponde a scegliere un insieme di rettangoli “non intersecanti” monotonicamente ordinati. In quella forma, la congettura si prestava a metodi geometrici ed analitici.

Questa traduzione nel linguaggio della geometria e dell’impacchettamento, pur ricordando una vecchia dimostrazione del 1959 del teorema di Erdős–Szekeres data da A. Seidenberg  che già usava argomenti di tipo “pigeonhole” o “impacchettamento discreto” per derivare il teorema classico., assume ora una forma nuova e più potente: rettangoli dove le aree e le altezze riflettono le x_i originali, e un ordine che ben rappresenta la monotonicità.

In questa veste, la congettura originale diventa assai più trattabile: l’AI produsse una dimostrazione formale (nel linguaggio di un theorem prover) che c(k²)=1/k. In parallelo, uno dei partecipanti al progetto ha riscoperto una versione “classica” del ragionamento: partendo dal teorema di Erdős–Szekeres, un’operazione di “blow-up” (espansione) delle pile  trasformando ogni x_i in molte pile più piccole ma proporzionali  consente di recuperare, al limite, il rapporto 1/√n.

Ma la storia non si ferma al solo output automatico. Gli autori del “nuovo” risultato hanno grattato tra le pagine della letteratura, e scoperto che un lavoro del 2016  riguardante problemi analoghi  conteneva già, con varianti e in contesti diversi, il risultato c(n) ≥ 1/√n, ispirato a un contributo precedente di Wagner. Ciò suggerisce che la “congettura” fosse, almeno in qualche forma, già implicita in studi antecedenti, benché non formalizzata con la precisione richiesta.

Così, in un arco di 48 ore, l’ipotesi incarnata nel “problema 1026 di Erdős”  una domanda aperta da decenni almeno implicitamente  ha ricevuto risposta: attraverso un cocktail di intuizioni classiche, automatizzazione, riscoperta di lavori preesistenti e collaborazione aperta. Lo sviluppo ricorda la costruzione di un mosaico: tessera dopo tessera  teoria combinatoria, geometria, algoritmi, AIsi compone un disegno coerente.

Questo racconto  fatto di monete immaginarie, pile, monotonia, rettangoli e automi deduttivi  illustra quanto a volte sia necessario guardare “attraverso” il linguaggio originale: le domande possono cambiare volto, assumere forme nuove, e riemergere con forza proprio quando strumenti e vie di ragionamento si evolvono.

E in fondo, quando la matematica si apre a nuovi alleati  fatti di codice, di geometria, di intuizione collettiva  anche ciò che sembrava “ambiguo” può essere reinterpretato, ridotto, e forse un giorno ufficialmente sancito.