Il sorteggio che si incastra
Il sorteggio della Champions fatto con le palline nell'urna fallisce 4.998 volte su 5.000. E non fallisce subito: si blocca dopo aver già estratto tre quarti degli accoppiamenti.
- Metodo
- Problema di soddisfacimento di vincoli con oracolo di completabilità
- Strumenti
- Python, Gurobi, HiGHS
- Risultato
- 2 su 5.000 — i sorteggi a mano che arrivano in fondo
Questo caso non propone un miglioramento. Il modello dimostra che come si fa oggi è già la scelta migliore possibile: si legge per capire perché, non per cambiare qualcosa. Gli altri casi già ottimi →
Quasi tutti i problemi di questa rivista chiedono quale sia la soluzione migliore fra tante. Questo ne chiede una più modesta, e più difficile: ne esiste una?
Dal 2024-25 la Champions League non ha più i gironi. Trentasei squadre, divise in quattro fasce da nove, e ognuna ne affronta otto: due per fascia, una in casa e una fuori. Con due regole sulle federazioni — non si incontra mai una squadra del proprio paese, e non se ne incontrano più di due dello stesso paese.
Sono 144 accoppiamenti da fissare. E il modo tradizionale di fissarli — una pallina alla volta, scegliendo a caso fra quello che in quel momento non viola nessuna regola — non funziona.
Su cinquemila sorteggi fatti alla vecchia maniera, con le palline e senza controlli, quanti arrivano in fondo senza incastrarsi?
Prova a dire quanti
Due
Il 99,96% si blocca. E si blocca dopo aver già fissato, in media, 109 accoppiamenti su 144.
01La sfida
Il punto delicato è che una scelta localmente legittima può essere globalmente fatale. Si estrae una pallina, si controlla che l’accoppiamento rispetti tutte le regole, si va avanti. Nessuno ha sbagliato niente. E cento accoppiamenti dopo ci si accorge che a una squadra non è rimasto nessun avversario possibile.
Non c’è modo di accorgersene guardando solo il presente. Bisogna guardare il futuro: prima di accettare un accoppiamento, chiedersi se da lì in poi il sorteggio si può ancora chiudere. Ed è una domanda che non si risponde a occhio.
02Gli ingredienti
- Il calendario vero della Champions 2024-25 dall’archivio aperto openfootball: 189 partite, di cui 144 della fase a campionato. Le sigle delle federazioni stanno nei nomi delle squadre.
- Un dettaglio che ci ha divertiti: il calendario non dice in quale fascia fosse ciascuna squadra. Non serve che lo dica. «Due avversari per fascia» è una condizione così stringente che la divisione in fasce si ricostruisce dal solo elenco delle partite, risolvendo un problema di assegnazione. Il risultato è unico a meno di rinominare le fasce, e la fascia che ne esce come prima contiene Real Madrid, Manchester City, Bayern, Paris Saint-Germain, Liverpool, Inter, Dortmund, Lipsia e Barcellona: la teste di serie della UEFA, nove su nove.
- E una verifica: nel sorteggio vero gli scontri fra connazionali sono zero e nessuna squadra affronta più di due squadre dello stesso paese. Le regole che abbiamo scritto nel modello sono quelle che si sono davvero giocate.
03Il verdetto
Dove muore un sorteggio fatto a mano
Accoppiamenti fissati prima di restare senza opzioni legali, su 5.000 tentativi
Vedi i dati in tabella
| Sorteggi | |
|---|---|
| fino a 60 | 72 |
| 60-80 | 322 |
| 80-100 | 1.102 |
| 100-110 | 1.064 |
| 110-120 | 1.162 |
| 120-130 | 941 |
| 130-143 | 335 |
| 144 (completo) | 2 |
Il blocco non arriva all'inizio, quando sarebbe innocuo: arriva quando quasi tutto è già stato deciso.
Cinquemila sorteggi sequenziali simulati sul campo della Champions 2024-25
Il grafico è la cosa più istruttiva del caso. Il sorteggio a mano non fallisce subito, quando basterebbe ricominciare. Fallisce tardi: la mediana è a 109 accoppiamenti su 144, con tutte le regole rispettate a ogni passo e nessuna possibilità di finire.
Ogni singola mossa era legittima. L’insieme delle mosse, no. È la differenza fra rispettare le regole e restare dentro il gioco.
La riparazione è concettualmente semplice e computazionalmente pesante: prima di accettare un accoppiamento si risolve un problema di ammissibilità che chiede se il sorteggio parziale ammetta ancora un completamento. Con quel controllo dentro il ciclo, trecento sorteggi su trecento arrivano in fondo, usando in media 154 verifiche ciascuno.
È per questo che la cerimonia in televisione è un computer che legge dei risultati, e non una mano che pesca palline.
04Ma legale non vuol dire equo
C’è un prezzo, e vale la pena dirlo. Una procedura che arriva sempre in fondo non è per questo imparziale.
Sui trecento sorteggi guidati, gli accoppiamenti che si sono verificati almeno una volta sono 592. Le loro probabilità vanno da 0,140 a 0,400: un accoppiamento ha quasi tre volte le possibilità di un altro di uscire.
Il motivo è strutturale, non un difetto dell’implementazione. Una squadra di una federazione con molte iscritte ha meno avversari ammissibili di una che arriva da un paese con una sola squadra, e il filtro di ammissibilità spinge sistematicamente il sorteggio lontano dalle scelte che lascerebbero a secco le squadre più vincolate. Non è la casualità a essere sbagliata: è l’insieme dei vincoli a non essere simmetrico.
Le due procedure a confronto
Stesso campo di 36 squadre, stesse regole. Cambia solo cosa si controlla prima di accettare un accoppiamento.
2 su 5.000, con blocco mediano a 109 accoppiamenti
Tutti gli scenari in tabella
| Procedura | Sorteggi completati | |
|---|---|---|
| A mano: basta che sia legale adesso | 0,04% | 2 su 5.000, con blocco mediano a 109 accoppiamenti |
| Guidata: legale e ancora completabile | 100% | 300 su 300, con 154 controlli per sorteggio |
Simulazioni sul campo della Champions League 2024-25
Il modello, per chi vuole la matematica
La ricostruzione delle fasce. Sia ytp ∈ {0,1} l’indicatore che la squadra t stia in fascia p, e N(t) i suoi otto avversari:
Σp ytp = 1 per ogni squadra
Σt ytp = 9 per ogni fascia
Σo ∈ N(t) yop = 2 per ogni squadra e ogni fascia
Fissando una squadra per rompere la simmetria, il modello restituisce esattamente sei soluzioni — cioè 3! = 6 rinomine della stessa partizione. La divisione in fasce è quindi unica.
L’oracolo di completabilità. Sia zab ∈ {0,1} l’indicatore che le squadre a e b si incontrino. Si fissa a 1 quello che è già stato sorteggiato, a 0 le coppie di connazionali e quelle già scartate, e si impone
Σb ∈ fascia p zab = 2 per ogni squadra e ogni fascia
Σb : paese(b) = c zab ≤ 2 per ogni squadra e ogni paese
Un completamento esiste se e solo se questo sistema è soddisfacibile. Non c’è funzione obiettivo: è pura ammissibilità, circa 600 variabili binarie, risolta in millisecondi. Ed è questo che rende il caso diverso da tutti gli altri di questa rivista — qui non si cerca il meglio, si cerca se qualcosa esiste.
Un’osservazione che fa risparmiare molto tempo: scartare è definitivo. Se non esiste un completamento che contiene la coppia (a,b) dato quello che è già stato fissato, non ne esisterà nemmeno dopo che si sarà fissato altro. Le coppie bocciate si possono quindi mettere via una volta per tutte.
05Dove il gioco finisce
La procedura che abbiamo simulato è una ricostruzione plausibile, non l’implementazione della UEFA, che non è pubblica. Noi fissiamo gli accoppiamenti in ordine casuale e accettiamo la prima opzione che tiene in piedi il completamento; la cerimonia vera estrae le squadre in un ordine prestabilito e assegna gli avversari fascia per fascia. Che il sorteggio non sia uniforme è un fatto robusto rispetto a questi dettagli; i numeri precisi no.
Il rapporto di 2,86 fra l’accoppiamento più e meno probabile poggia su trecento sorteggi: le probabilità delle singole coppie hanno un errore di campionamento di qualche punto percentuale, e gli estremi sono la parte meno affidabile.
Abbiamo ignorato del tutto casa e trasferta. Il sorteggio vero decide anche chi ospita chi, con altre regole di bilanciamento: il problema reale è quindi più difficile di quello che abbiamo misurato, non meno.
E abbiamo guardato una stagione sola. Il campo del 2024-25 aveva diciassette federazioni con una certa distribuzione di squadre; un campo più concentrato su pochi paesi si incastrerebbe ancora più spesso.