Dopo 150 anni si risolve il famoso problema posto da Kirkman (ma anche da Steiner): adesso sappiamo che le soluzioni esistono, ma non sappiamo trovarle. Ci viene in aiuto l’ottimizzazione combinatorica.
Nel 1850 il Reverendo Thomas Kirkman, noto matematico inglese del suo secolo nonché rettore di una parrocchia nel Lancashire, propose sul periodico di giochi matematici “Lady’s and Gentleman’s Diary” il seguente quesito:
“Ogni giorno della settimana, quindici giovani ragazze della stessa scuola camminano insieme in 5 file di 3 persone ciascuna. È possibile creare ogni giorno le triplette di ragazze in modo che nessuna coppia di ragazze sia nella stessa tripletta per più di una volta a settimana?”
Il rompicapo, così semplicemente descritto, risultò molto difficile da risolvere e appassionò a lungo i lettori della rivista, diventando molto popolare nell’Inghilterra vittoriana. Ovviamente stimolò l’interesse di alcuni matematici del tempo, che proposero diverse soluzioni all’enigma.
Una volta trovata una soluzione al problema posto da Kirkman, venne naturale considerarne una generalizzazione. La più famosa è dovuta al matematico svizzero Jacob Steiner, che nel 1853 fece comparire, in due pagine pubblicate sul Crelle’s Journal, una descrizione astratta e ben formalizzata del problema dei “gruppi di ragazze”. Da allora i gruppi di sottoinsiemi di dimensione k di un insieme di dimensione n, tali che ogni sottoinsieme di dimensione t compaia esattamente in un sottoinsieme di dimensione k, si chiamano proprio “Steiner System” e si indicano con la notazione S(t,k,n). Nella fattispecie, il problema di Kirkman può essere chiamato anche S(2,3,15) o, più sinteticamente, una sistema di triple di Steiner di dimensione 15.
Due le domande fondamentali da porsi: esistono delle regole che permettono di determinare se un sistema definito dai 3 valori (t,k,n) esista? Quali relazioni devono intercorrere tra i tre parametri affinché esista almeno una soluzione? Certamente esistono delle condizioni di divisibilità tra t, n, e k che permettono di stabilire con certezza che alcune triplette (t,k,n) definiscono un problema senza soluzione; ma cosa accade quando queste condizioni non sono soddisfatte?
I problemi definiti in questo modo furono ribattezzati come “design problems”; il notevole interesse verso questa classe di problemi e’ motivato dal fatto che essi permettono di modellare altri problemi rilevanti provenienti da applicazioni molto diverse tra loro: per esempio, alcune strutture matematiche possono essere descritte in termini di design problems per determinate terne di parametri (t,k,n), e lo stesso vale per problemi di crittografia.
Per anni si è pensato che non potesse esserci una risposta definitiva al problema di ammissibilità. Dopo ben 150 dalla pubblicazione dell’enigma di Kirkman, nel 2014, il matematico Peter Keevash ha dimostrato che se determinate condizioni di divisibilità sono soddisfatte, allora il problema ammette soluzione. La dimostrazione del teorema, valida a meno di un numero finito di eccezioni, combina la combinatorica con la teoria della probabilità.
Questo risultato ha rappresentato una svolta epocale nella conoscenza del problema, pur lasciando aperte alcune questioni centrali da affrontare per risolvere il problema nella pratica: come gestire le eccezioni per una particolare configurazione (t,k,n) di interesse? Con quale algoritmo è possibile determinare le soluzioni di un certo problema? Quale è il tempo di calcolo di questo algoritmo?
La popolarità del problema posto da Kirkman contribuì senz’altro alla notorietà del Calcolo Combinatoriale, che si occupa di contare tutte le possibili occorrenze di un evento. Se piuttosto che contare si vuole identificare la migliore occorrenza – migliore rispetto a una particolare funzione di merito – allora si parla di Ottimizzazione Combinatoria; tale branca della matematica, che tipicamente richiede lo sviluppo di algoritmi di soluzione – oggi applicata in problemi di logistica, trasporti, crittografia, telecomunicazioni – viene in aiuto anche in diversi problemi di matematica ricreativa simili a quello posto da Kirkman, come per esempio il problema della tavola rotonda. Supponiamo di avere n ospiti da accomodare attorno ad una tavola rotonda. Ogni ospite esprime, tramite un valore, il gradimento che ha nel sedere accanto a ognuno degli altri ospiti (0 = nessun gradimento, 10 = massimo gradimento). Il problema consiste nel far accomodare gli ospiti massimizzando il gradimento totale. Il Calcolo Combinatoriale ci dice che il numero di disposizioni diverse è uguale ad n! (n x (n-1) x …. x 2 x 1). L’ottimizzazione combinatoriale ci consente di identificare, tra tutte queste numerosissime alternative, la soluzione migliore, ovvero quella che massimizza il gradimento totale.
Un caso simile si è verificato per un altro noto quesito di matematica ricreativa proposto da M. Gardner nel 1966: è possibile inserire i 24 quadrati di lato 1, 2, 3,…, 24 dentro un unico quadrato di lato 70 senza sovrapporli? Anche in questo caso, il problema in esame può essere ricondotto a un problema di ottimizzazione combinatoria e risolto tramite un algoritmo. Per ottenere una risposta definitiva questa volta si sono dovuti aspettare solo 38 anni. A darla è stato il computer scientist della UCLA Richard Korf, tramite un algoritmo enumerativo. Ma la risposta, questa volta, è “no”.
Michele Monaci
Università degli Studi di Padova
Associazione Italiana di Ricerca Operativa
