Cuadros de torneo: byes, cabezas de serie y por qué los números deben ser potencias de dos

El cuadro se parte en dos, así que debe empezar en una potencia de dos

Una ronda de eliminación empareja a todos y manda a casa a la mitad. Empieza con 16 y obtienes 8, luego 4, luego 2, luego 1: cuatro rondas, sin restos, nadie parado. Empieza con 12 y la segunda ronda tiene 6, la tercera 3, y ahora tres jugadores no se pueden emparejar. La estructura solo cierra si cada ronda tiene un número par de supervivientes hasta el final, y los únicos números con esa propiedad son las potencias de dos. No es una convención que eligieran los organizadores; es lo que hace la división por dos repetida, y por eso todo cuadro publicado que hayas visto tiene 8, 16, 32, 64 o 128 huecos.

El número de rondas sale del mismo argumento. Si el cuadro alberga 2^r inscritos, hacen falta r divisiones por dos para llegar a un único ganador, así que r es log2 del tamaño del cuadro, y para un número de inscritos n cualquiera el tamaño del cuadro es la menor potencia de dos no inferior a n. Escrito: rondas = techo(log2 n), tamaño = 2^techo(log2 n). Doce inscritos juegan por tanto un cuadro de 16 en 4 rondas; 100 inscritos un cuadro de 128 en 7; 129 inscritos un cuadro de 256 en 8. Ese último salto resume todo el problema: el inscrito número 129 no añade un partido al calendario, le añade una ronda entera.

Los byes son exactamente el hueco hasta la siguiente potencia de dos

Si el cuadro tiene 2^techo(log2 n) huecos y solo n están ocupados por inscritos reales, los huecos restantes no albergan a nadie. Cada hueco vacío se enfrenta a un inscrito real, que por tanto avanza sin jugar: eso es un bye. Así que el número de byes es la resta y nada más: byes = 2^techo(log2 n) − n. Veintitrés inscritos en un cuadro de 32 dan 9 byes; 48 en un cuadro de 64 dan 16; 100 en un cuadro de 128 dan 28. El número es máximo justo por encima de una potencia de dos y nulo exactamente en una, y por eso 129 inscritos producen 127 byes — más byes que personas que juegan de verdad en la primera ronda.

La primera ronda es más pequeña que la mitad del cuadro en exactamente la misma cantidad. Si b inscritos reciben bye, los otros n − b juegan, y juegan (n − b)/2 partidos; sustituyendo b = 2^r − n queda partidos de primera ronda = n − 2^(r − 1), es decir n menos la mitad del cuadro. Para 100 inscritos son 100 − 64 = 36 partidos, y la comprobación cierra: 36 × 2 = 72 personas juegan, 28 descansan, 72 + 28 = 100, y 36 + 28 = 64 supervivientes entran en la segunda ronda — exactamente la mitad del cuadro, que es donde la estructura de potencia de dos se reanuda limpia. Desde la segunda ronda ya no hay bye alguno, porque el plantel vuelve a ser una potencia de dos por construcción.

El orden de cabezas de serie sale de una recursión, no de una lista memorizada

Empieza con un cuadro de uno: el orden de cabezas es [1]. Para duplicarlo, toma cada cabeza s de un cuadro que va a tener tamaño m y sustitúyela por la pareja (s, m + 1 − s). Una duplicación da [1, 2]. Dos dan [1, 4, 2, 3]. Tres dan [1, 8, 4, 5, 2, 7, 3, 6]. Cuatro dan 1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11. Cinco dan 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. Nada se memoriza y nada se consulta; la recursión son cuatro líneas de código y produce el orden estándar para cualquier tamaño de cuadro.

Lee la línea de dieciséis cabezas como ocho partidos de primera ronda y el patrón salta a la vista: 1 c. 16, 8 c. 9, 4 c. 13, 5 c. 12, 2 c. 15, 7 c. 10, 3 c. 14, 6 c. 11. Cada emparejamiento suma 17, que es el tamaño del cuadro más uno, porque eso es exactamente lo que impone la sustitución s por (s, m + 1 − s). Es la misma regla en cada nivel del árbol, así que la mejor cabeza restante de un bloque se enfrenta siempre a la más débil restante, en cada ronda, sin que nadie tenga que escribir una segunda regla.

Lo que el sorteo por cabezas garantiza de verdad, comprobado en vez de afirmado

Pasa el orden generado por unas cuantas aserciones y el diseño se revela. Parte el orden de dieciséis cabezas en bloques y todo bloque del mismo tamaño suma el mismo número: 17 por pareja, 34 por cuarto, 68 por mitad, 136 para el cuadro entero — siempre el tamaño del bloque por (n + 1) dividido entre 2. Toma la mejor cabeza de cada bloque y recuperas el orden de un cuadro de la mitad de tamaño: los bloques de dos dan 1, 8, 4, 5, 2, 7, 3, 6, que es el orden de ocho cabezas; los bloques de cuatro dan 1, 4, 2, 3. El cuadro es autosemejante, que es justo lo que una recursión por duplicación debe producir.

La garantía que de verdad importa se sigue de inmediato. Las cabezas 1 y 2 ocupan mitades opuestas, así que si ambas siguen ganando no pueden verse antes de la final; las cabezas 1, 2, 3 y 4 ocupan cuatro cuartos distintos, así que dos de ellas no pueden encontrarse antes de las semifinales. Rastrear los rivales posibles más tempranos de la cabeza 1 en el cuadro de dieciséis da 16 en la primera ronda, 8 o 9 en la segunda, uno de 4, 5, 12, 13 en semifinales y 2 o 3 solo en la final. Ese es el sentido exacto del sorteo por cabezas: no protege al favorito de rivales fuertes, los aplaza, para que los mejores partidos del torneo caigan al final y no en la ronda inaugural.

El sorteo por cabezas también reparte los byes sin regla aparte. Llena un cuadro de 128 con los inscritos 1 a 100 e inscritos fantasma 101 a 128, genera el orden con la recursión y lee qué inscritos reales quedan emparejados con fantasmas: son exactamente las cabezas 1 a 28, contiguas y en orden. Nadie tuvo que decidir que los byes fueran a las mejores cabezas — la misma sustitución que empareja s con m + 1 − s coloca las cabezas más altas frente a los huecos de número más alto, que son justamente los vacíos. Conviene comprobarlo en la herramienta que uses, porque un generador que reparte byes a inscritos arbitrarios ha roto el sorteo por cabezas, no solo los byes.

Total de partidos: n − 1, para todo n, en una línea

Cada partido de un torneo de eliminación directa elimina exactamente a un inscrito — eso es lo que significa eliminación directa. Al final, exactamente un inscrito no ha sido eliminado, así que exactamente n − 1 lo han sido. Una eliminación por partido significa por tanto exactamente n − 1 partidos, sea cual sea el tamaño del cuadro, sean cuales sean los byes, sea cual sea el sorteo. Veintitrés inscritos juegan 22 partidos; 100 inscritos juegan 99; 129 inscritos juegan 128. Nunca hace falta sumar las rondas, y los byes no entran en el cálculo en absoluto, porque un bye no es un partido y no elimina a nadie.

El mismo argumento de conteo pone precio a los demás formatos. En doble eliminación todos menos el campeón han de perder dos veces, así que hay que producir 2(n − 1) derrotas, y como cada partido produce exactamente una, el calendario necesita 2n − 2 partidos. Si el finalista salido del cuadro de perdedores gana la gran final, le ha endosado al jugador hasta entonces invicto su primera derrota, y se juega un partido de reinicio para darle una segunda — 2n − 1 partidos en ese caso. Ambas cifras son exactas, y cuál toca se decide el mismo día. El todos contra todos es otra bestia: cada pareja se enfrenta una vez, así que el recuento es C(n,2) = n(n − 1)/2, que crece de forma cuadrática. Con 100 inscritos son 4 950 partidos frente a 99 de una eliminación directa, un factor de exactamente 50.

Elegir un formato a partir de los números

Los tres formatos cambian partidos por información. La eliminación directa es el torneo más barato posible — n − 1 partidos, techo(log2 n) rondas — y produce exactamente un hecho fiable: la identidad del ganador. Todo lo que hay por debajo del primer puesto es un artefacto del sorteo: los semifinalistas perdedores no quedan ordenados entre sí, y un inscrito fuerte que se cruza con el campeón en la segunda ronda acaba de forma indistinguible de uno débil. La doble eliminación compra una segunda oportunidad por aproximadamente el doble de partidos y en torno a una ronda más, y elimina el peor modo de fallo: un buen inscrito eliminado por un solo mal día.

El todos contra todos da una clasificación completa y la cobra de forma cuadrática. Doce inscritos juegan 66 partidos en vez de 11; 23 juegan 253 en vez de 22; 48 juegan 1 128 en vez de 47. Necesita además n − 1 rondas cuando n es par y n rondas cuando n es impar, porque con un plantel impar alguien descansa cada ronda. El compromiso práctico que usa la mayoría de los eventos grandes es una fase de grupos seguida de un cuadro: el todos contra todos dentro de grupos pequeños produce una clasificación defendible barata, y la eliminación directa cuesta después un partido por clasificado eliminado. Elijas lo que elijas, calcula el número de partidos antes de reservar la sede — la diferencia entre 99 y 4 950 no es un detalle de planificación.

Preguntas frecuentes

¿Cuántos byes necesita un torneo con 23 inscritos?

Nueve. El tamaño del cuadro es la menor potencia de dos no inferior a 23, que es 32, y el número de byes es eso menos el número de inscritos: 32 − 23 = 9. La fórmula es general — byes = 2^techo(log2 n) − n — y es una resta, no una regla aproximada. La primera ronda tiene entonces n menos la mitad del cuadro, es decir 23 − 16 = 7 partidos, y la aritmética cierra: 7 × 2 = 14 personas juegan, 9 reciben bye, 14 + 9 = 23, y 7 + 9 = 16 supervivientes entran en la segunda ronda, que es exactamente la mitad del cuadro. A partir de ahí no hay más byes, porque el plantel vuelve a ser una potencia de dos. El torneo entero son 5 rondas y 22 partidos.

¿Cuál es el orden estándar de cabezas de serie en un cuadro de 16?

1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11 — leído como ocho partidos de primera ronda, es 1 c. 16, 8 c. 9, 4 c. 13, 5 c. 12, 2 c. 15, 7 c. 10, 3 c. 14, 6 c. 11. En vez de memorizarlo, genéralo: parte de la lista [1] y sustituye repetidamente cada cabeza s por la pareja (s, m + 1 − s), donde m es el tamaño que la lista va a alcanzar. Cuatro duplicaciones dan el orden de arriba; cinco dan el orden de 32 cabezas, y así sucesivamente. El resultado es verificable en vez de creído — cada emparejamiento de primera ronda suma 17, cada cuarto de la lista suma 34 y cada mitad 68, las cabezas 1 y 2 caen en mitades opuestas, y las cabezas 1 a 4 en cuatro cuartos distintos.

¿Por qué se emparejan las mejores cabezas con las últimas?

Para empujar los encuentros entre inscritos fuertes lo más tarde posible. Emparejar 1 con 16 y 2 con 15 no busca dar a los favoritos un debut fácil; es la única manera de colocarlos de modo que no puedan verse pronto. La recursión que produce el orden pone las cabezas 1 y 2 en mitades opuestas y las cabezas 1, 2, 3, 4 en cuatro cuartos distintos: la cabeza 1 solo puede enfrentarse a 2 o 3 en la final y no puede cruzarse con ninguna de 4, 5, 12 o 13 antes de semifinales. Rastrea los rivales posibles más tempranos de la cabeza 1 en un cuadro de 16 y obtienes 16 en la primera ronda, 8 o 9 en la segunda, uno de 4, 5, 12, 13 en semis y 2 o 3 en la final. El objetivo de diseño es un torneo cuyos mejores partidos ocurren al final, y sale automáticamente de una única regla de sustitución.

¿Cuántos partidos necesitará mi torneo?

Para eliminación directa, n − 1, y no hay nada que consultar. Cada partido elimina exactamente a un inscrito, al final queda exactamente uno, así que han ocurrido exactamente n − 1 eliminaciones y por tanto n − 1 partidos. Los byes no cambian nada, porque un bye no es un partido. La doble eliminación exige que todos menos el campeón pierdan dos veces, o sea 2(n − 1) derrotas y por tanto 2n − 2 partidos; si el inscrito que viene del cuadro de perdedores gana la gran final, se juega un partido de reinicio y el total es 2n − 1. El todos contra todos hace jugar a cada pareja una vez, o sea C(n,2) = n(n − 1)/2 partidos, en n − 1 rondas si n es par y n rondas si n es impar. Para 100 inscritos, los tres formatos cuestan respectivamente 99, 198 o 199, y 4 950 partidos.

¿Deben ir los byes a las mejores cabezas de serie?

Ya lo hacen, si construyes el cuadro correctamente — nunca tienes que decidirlo aparte. Completa el cuadro hasta su tamaño en potencia de dos con inscritos fantasma numerados por encima de los reales, genera el orden con la recursión de duplicación y lee quién se enfrenta a un fantasma. Para 100 inscritos en un cuadro de 128 resultan ser exactamente las cabezas 1 a 28, contiguas y en orden, porque la misma sustitución que empareja s con m + 1 − s coloca las cabezas más altas frente a los huecos de número más alto, que son justamente los vacíos. Se siguen dos consecuencias. Primera, el número de byes y la identidad de quienes los reciben salen de una sola construcción, no de dos reglas que pueden discrepar. Segunda, un generador que dispersa los byes entre inscritos arbitrarios ha roto también el sorteo por cabezas, y merece ser reemplazado.