Tabelloni di torneo: bye, teste di serie e perché i numeri devono essere potenze di due

Il tabellone si dimezza, quindi deve partire da una potenza di due

Un turno a eliminazione accoppia tutti e ne manda a casa la metà. Parti da 16 e ottieni 8, poi 4, poi 2, poi 1: quattro turni, nessun resto, nessuno fermo. Parti da 12 e il secondo turno ne ha 6, il terzo 3, e ora tre giocatori non si possono accoppiare. La struttura si chiude solo se ogni turno ha un numero pari di superstiti fino in fondo, e gli unici numeri con quella proprietà sono le potenze di due. Non è una convenzione scelta dagli organizzatori: è ciò che fa il dimezzamento ripetuto, ed è per questo che ogni tabellone pubblicato che tu abbia mai visto ha 8, 16, 32, 64 o 128 posti.

Il numero di turni discende dallo stesso argomento. Se il tabellone contiene 2^r iscritti, servono r dimezzamenti per arrivare a un unico vincitore, quindi r è il logaritmo in base 2 della dimensione del tabellone, e per un numero di iscritti n qualsiasi la dimensione è la più piccola potenza di due non inferiore a n. Per esteso: turni = arrotondamento superiore di log2 n, dimensione = 2 elevato a quello. Dodici iscritti giocano dunque un tabellone da 16 su 4 turni; 100 iscritti un tabellone da 128 su 7; 129 iscritti un tabellone da 256 su 8. Quell'ultimo salto è tutto il problema in una riga: il 129º iscritto non aggiunge una partita al calendario, gli aggiunge un turno intero.

I bye sono esattamente il divario fino alla potenza di due successiva

Se il tabellone ha 2 elevato all'arrotondamento superiore di log2 n posti e solo n sono occupati da iscritti reali, i posti restanti non contengono nessuno. Ogni posto vuoto fronteggia un iscritto reale, che quindi avanza senza giocare: quello è un bye. Perciò il numero di bye è la sottrazione e nulla più: bye = dimensione del tabellone meno n. Ventitré iscritti in un tabellone da 32 danno 9 bye; 48 in uno da 64 ne danno 16; 100 in uno da 128 ne danno 28. Il numero è massimo appena sopra una potenza di due e nullo esattamente su una, ed è per questo che 129 iscritti producono 127 bye — più bye che persone che giocano davvero al primo turno.

Il primo turno è più piccolo di metà tabellone esattamente della stessa quantità. Se b iscritti ricevono un bye, gli altri n − b giocano, e giocano (n − b)/2 partite; sostituendo b = dimensione meno n si ottiene partite del primo turno = n − 2^(r − 1), cioè n meno metà del tabellone. Per 100 iscritti sono 100 − 64 = 36 partite, e la verifica chiude: 36 × 2 = 72 persone giocano, 28 riposano, 72 + 28 = 100, e 36 + 28 = 64 superstiti entrano nel secondo turno — esattamente metà tabellone, dove la struttura a potenza di due riprende pulita. Dal secondo turno in poi non ci sono bye affatto, perché il campo è di nuovo una potenza di due per costruzione.

L'ordine delle teste di serie nasce da una ricorsione, non da un elenco memorizzato

Parti da un tabellone da uno: l'ordine delle teste è [1]. Per raddoppiarlo, prendi ogni testa s in un tabellone che sta per avere dimensione m e sostituiscila con la coppia (s, m + 1 − s). Un raddoppio dà [1, 2]. Due danno [1, 4, 2, 3]. Tre danno [1, 8, 4, 5, 2, 7, 3, 6]. Quattro danno 1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11. Cinque danno 1, 32, 16, 17, 8, 25, 9, 24, 4, 29, 13, 20, 5, 28, 12, 21, 2, 31, 15, 18, 7, 26, 10, 23, 3, 30, 14, 19, 6, 27, 11, 22. Nulla è imparato a memoria e nulla è cercato altrove: la ricorsione sono quattro righe di codice e produce l'ordine standard per qualsiasi dimensione di tabellone.

Leggi la riga a sedici teste come otto partite di primo turno e lo schema salta agli occhi: 1 c. 16, 8 c. 9, 4 c. 13, 5 c. 12, 2 c. 15, 7 c. 10, 3 c. 14, 6 c. 11. Ogni accoppiamento somma 17, cioè la dimensione del tabellone più uno, perché è esattamente ciò che impone la sostituzione s con (s, m + 1 − s). È la stessa regola a ogni livello dell'albero, quindi la testa più forte rimasta in un blocco affronta sempre la più debole rimasta, a ogni turno, senza che nessuno debba scrivere una seconda regola.

Che cosa garantisce davvero la distribuzione delle teste, verificato invece che affermato

Fai passare l'ordine generato attraverso qualche asserzione e il disegno si rivela. Dividi l'ordine a sedici teste in blocchi: ogni blocco della stessa dimensione somma allo stesso numero — 17 per coppia, 34 per quarto, 68 per metà, 136 per l'intero tabellone — sempre la dimensione del blocco per (n + 1) diviso 2. Prendi la testa migliore di ogni blocco e ritrovi l'ordine di un tabellone grande la metà: i blocchi da due danno 1, 8, 4, 5, 2, 7, 3, 6, cioè l'ordine a otto teste; i blocchi da quattro danno 1, 4, 2, 3. Il tabellone è autosimile, che è esattamente ciò che una ricorsione per raddoppio deve produrre.

La garanzia che interessa davvero segue immediatamente. Le teste 1 e 2 stanno in metà opposte, quindi se entrambe continuano a vincere non possono incontrarsi prima della finale; le teste 1, 2, 3 e 4 stanno in quattro quarti diversi, quindi due di esse non possono incontrarsi prima delle semifinali. Tracciare gli avversari possibili più precoci della testa 1 nel tabellone da sedici dà 16 al primo turno, 8 o 9 al secondo, uno fra 4, 5, 12, 13 in semifinale, e 2 o 3 solo in finale. È questo il senso preciso della distribuzione delle teste: non protegge il favorito dagli avversari forti, li rimanda, così che le partite migliori del torneo cadano alla fine e non al turno d'apertura.

La distribuzione delle teste alloca anche i bye senza una regola separata. Riempi un tabellone da 128 con gli iscritti da 1 a 100 e iscritti fantasma da 101 a 128, genera l'ordine con la ricorsione e leggi quali iscritti reali risultano accoppiati a fantasmi: sono esattamente le teste da 1 a 28, contigue e in ordine. Nessuno ha dovuto decidere che i bye andassero alle teste migliori — la stessa sostituzione che accoppia s con m + 1 − s mette le teste più alte di fronte ai posti di numero più alto, che sono proprio quelli vuoti. Vale la pena verificarlo nello strumento che usi, perché un generatore che assegna i bye a iscritti arbitrari ha rotto la distribuzione delle teste, non solo i bye.

Totale partite: n − 1, per ogni n, in una riga

Ogni partita di un torneo a eliminazione diretta elimina esattamente un iscritto — è questo che significa eliminazione diretta. Alla fine, esattamente un iscritto non è stato eliminato, quindi esattamente n − 1 lo sono stati. Un'eliminazione per partita significa perciò esattamente n − 1 partite, qualunque sia la dimensione del tabellone, qualunque siano i bye, qualunque sia la distribuzione delle teste. Ventitré iscritti giocano 22 partite; 100 iscritti ne giocano 99; 129 iscritti ne giocano 128. Non devi mai sommare i turni, e i bye non entrano affatto nel calcolo, perché un bye non è una partita e non elimina nessuno.

Lo stesso argomento di conteggio dà il prezzo agli altri formati. Nella doppia eliminazione tutti tranne il campione devono perdere due volte, quindi vanno prodotte 2(n − 1) sconfitte, e poiché ogni partita ne produce esattamente una, il calendario richiede 2n − 2 partite. Se il finalista uscito dal tabellone dei perdenti vince la finalissima, ha inflitto al giocatore fino ad allora imbattuto la prima sconfitta, e si gioca una partita di azzeramento per dargliene una seconda — 2n − 1 partite in quel caso. Entrambe le cifre sono esatte, e quale valga si decide il giorno stesso. Il girone all'italiana è un'altra bestia: ogni coppia si incontra una volta, quindi il conteggio è C(n,2) = n(n − 1)/2, che cresce in modo quadratico. Con 100 iscritti sono 4 950 partite contro 99 di un'eliminazione diretta, un fattore di esattamente 50.

Scegliere un formato a partire dai numeri

I tre formati scambiano partite con informazione. L'eliminazione diretta è il torneo più economico possibile — n − 1 partite, arrotondamento superiore di log2 n turni — e produce esattamente un fatto affidabile: l'identità del vincitore. Tutto ciò che sta sotto il primo posto è un artefatto del sorteggio: i semifinalisti sconfitti non sono ordinati fra loro, e un iscritto forte che incrocia il campione al secondo turno finisce in modo indistinguibile da uno debole. La doppia eliminazione compra una seconda possibilità per circa il doppio delle partite e circa un turno in più, e rimuove il peggior modo di fallimento: un buon iscritto eliminato da una sola giornata storta.

Il girone all'italiana dà una classifica completa e la fa pagare in modo quadratico. Dodici iscritti giocano 66 partite invece di 11; 23 ne giocano 253 invece di 22; 48 ne giocano 1 128 invece di 47. Richiede inoltre n − 1 turni quando n è pari e n turni quando n è dispari, perché con un campo dispari qualcuno riposa a ogni turno. Il compromesso pratico che la maggior parte dei grandi eventi adotta è una fase a gironi seguita da un tabellone: il girone dentro gruppi piccoli produce a basso costo una classifica difendibile, e l'eliminazione diretta costa poi una partita per qualificato eliminato. Qualunque cosa scegli, calcola il numero di partite prima di prenotare la sede — la differenza fra 99 e 4 950 non è un dettaglio di pianificazione.

Domande frequenti

Quanti bye servono a un torneo con 23 iscritti?

Nove. La dimensione del tabellone è la più piccola potenza di due non inferiore a 23, cioè 32, e il numero di bye è quello meno il numero di iscritti: 32 − 23 = 9. La formula è generale — bye = dimensione del tabellone meno n — ed è una sottrazione, non una regola empirica. Il primo turno contiene allora n meno metà tabellone, cioè 23 − 16 = 7 partite, e l'aritmetica chiude: 7 × 2 = 14 persone giocano, 9 ricevono un bye, 14 + 9 = 23, e 7 + 9 = 16 superstiti entrano al secondo turno, che è esattamente metà tabellone. Da lì in poi non ci sono più bye, perché il campo è di nuovo una potenza di due. L'intero torneo dura 5 turni e 22 partite.

Qual è l'ordine standard delle teste di serie in un tabellone da 16?

1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11 — letto come otto partite di primo turno, è 1 c. 16, 8 c. 9, 4 c. 13, 5 c. 12, 2 c. 15, 7 c. 10, 3 c. 14, 6 c. 11. Invece di impararlo a memoria, generalo: parti dalla lista [1] e sostituisci ripetutamente ogni testa s con la coppia (s, m + 1 − s), dove m è la dimensione che la lista sta per raggiungere. Quattro raddoppi danno l'ordine qui sopra; cinque danno l'ordine a 32 teste, e così via. Il risultato è verificabile invece che creduto — ogni accoppiamento del primo turno somma 17, ogni quarto della lista somma 34 e ogni metà 68, le teste 1 e 2 finiscono in metà opposte, e le teste da 1 a 4 in quattro quarti diversi.

Perché le teste migliori sono accoppiate con le ultime?

Per spingere gli incontri fra iscritti forti il più tardi possibile. Accoppiare 1 con 16 e 2 con 15 non serve a regalare ai favoriti un esordio facile; è l'unico modo di collocarli in modo che non si possano incontrare presto. La ricorsione che produce l'ordine mette le teste 1 e 2 in metà opposte e le teste 1, 2, 3, 4 in quattro quarti diversi: la testa 1 può affrontare 2 o 3 solo in finale e non può incrociare nessuna fra 4, 5, 12 o 13 prima della semifinale. Traccia gli avversari possibili più precoci della testa 1 in un tabellone da 16 e ottieni 16 al primo turno, 8 o 9 al secondo, uno fra 4, 5, 12, 13 in semifinale e 2 o 3 in finale. L'obiettivo di progetto è un torneo le cui partite migliori accadono alla fine, e nasce automaticamente da un'unica regola di sostituzione.

Quante partite servirà al mio torneo?

Per l'eliminazione diretta, n − 1, e non c'è nulla da cercare. Ogni partita elimina esattamente un iscritto, alla fine ne resta esattamente uno, quindi sono avvenute esattamente n − 1 eliminazioni e perciò n − 1 partite. I bye non cambiano nulla, perché un bye non è una partita. La doppia eliminazione richiede che tutti tranne il campione perdano due volte, cioè 2(n − 1) sconfitte e quindi 2n − 2 partite; se l'iscritto proveniente dal tabellone dei perdenti vince la finalissima, si gioca una partita di azzeramento e il totale è 2n − 1. Il girone all'italiana fa giocare ogni coppia una volta, cioè C(n,2) = n(n − 1)/2 partite, su n − 1 turni se n è pari e n turni se n è dispari. Per 100 iscritti i tre formati costano rispettivamente 99, 198 o 199, e 4 950 partite.

I bye devono andare alle teste di serie migliori?

Ci vanno già, se costruisci il tabellone come si deve — non devi mai deciderlo a parte. Completa il tabellone fino alla sua dimensione in potenza di due con iscritti fantasma numerati sopra quelli reali, genera l'ordine con la ricorsione per raddoppio e leggi chi affronta un fantasma. Per 100 iscritti in un tabellone da 128 risultano esattamente le teste da 1 a 28, contigue e in ordine, perché la stessa sostituzione che accoppia s con m + 1 − s mette le teste più alte di fronte ai posti di numero più alto, che sono proprio quelli vuoti. Ne seguono due conseguenze. Primo, il numero di bye e l'identità di chi li riceve nascono da un'unica costruzione, non da due regole che possono contraddirsi. Secondo, un generatore che sparpaglia i bye fra iscritti arbitrari ha rotto anche la distribuzione delle teste, e vale la pena sostituirlo.