Quadros de torneio: byes, cabeças de série e porque os números têm de ser potências de dois

O quadro divide-se em dois, portanto tem de começar numa potência de dois

Uma ronda de eliminação emparelha toda a gente e manda metade para casa. Comece com 16 e obtém 8, depois 4, depois 2, depois 1: quatro rondas, sem restos, ninguém parado. Comece com 12 e a segunda ronda tem 6, a terceira 3, e agora três jogadores não podem ser emparelhados. A estrutura só fecha se cada ronda tiver um número par de sobreviventes até ao fim, e os únicos números com essa propriedade são as potências de dois. Não é uma convenção que os organizadores tenham escolhido; é o que a divisão por dois repetida faz, e é por isso que todo o quadro publicado que já viu tem 8, 16, 32, 64 ou 128 lugares.

O número de rondas sai do mesmo argumento. Se o quadro alberga 2^r inscritos, são precisas r divisões por dois para chegar a um único vencedor, portanto r é log2 do tamanho do quadro, e para um número de inscritos n qualquer o tamanho do quadro é a menor potência de dois não inferior a n. Escrito: rondas = teto(log2 n), tamanho = 2^teto(log2 n). Doze inscritos jogam assim um quadro de 16 em 4 rondas; 100 inscritos um quadro de 128 em 7; 129 inscritos um quadro de 256 em 8. Esse último salto resume o problema todo: o inscrito número 129 não acrescenta um jogo ao calendário, acrescenta-lhe uma ronda inteira.

Os byes são exatamente a diferença até à potência de dois seguinte

Se o quadro tem 2^teto(log2 n) lugares e só n estão ocupados por inscritos reais, os lugares restantes não albergam ninguém. Cada lugar vazio defronta um inscrito real, que por isso avança sem jogar: isso é um bye. Portanto o número de byes é a subtração e nada mais: byes = 2^teto(log2 n) − n. Vinte e três inscritos num quadro de 32 dão 9 byes; 48 num quadro de 64 dão 16; 100 num quadro de 128 dão 28. O número é máximo logo acima de uma potência de dois e nulo exatamente numa, e por isso 129 inscritos produzem 127 byes — mais byes do que pessoas que jogam realmente na primeira ronda.

A primeira ronda é menor do que metade do quadro exatamente na mesma quantidade. Se b inscritos recebem bye, os outros n − b jogam, e jogam (n − b)/2 jogos; substituindo b = 2^r − n fica jogos da primeira ronda = n − 2^(r − 1), ou seja n menos metade do quadro. Para 100 inscritos são 100 − 64 = 36 jogos, e a verificação fecha: 36 × 2 = 72 pessoas jogam, 28 descansam, 72 + 28 = 100, e 36 + 28 = 64 sobreviventes entram na segunda ronda — exatamente metade do quadro, que é onde a estrutura em potência de dois retoma limpa. A partir da segunda ronda não há bye nenhum, porque o plantel volta a ser uma potência de dois por construção.

A ordem das cabeças de série sai de uma recursão, não de uma lista decorada

Comece com um quadro de um: a ordem das cabeças é [1]. Para o duplicar, tome cada cabeça s de um quadro que vai passar a ter tamanho m e substitua-a pelo par (s, m + 1 − s). Uma duplicação dá [1, 2]. Duas dão [1, 4, 2, 3]. Três dão [1, 8, 4, 5, 2, 7, 3, 6]. Quatro dão 1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11. Cinco dão 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 é decorado e nada é consultado; a recursão são quatro linhas de código e produz a ordem padrão para qualquer tamanho de quadro.

Leia a linha de dezasseis cabeças como oito jogos de primeira ronda e o padrão salta à 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 emparelhamento soma 17, que é o tamanho do quadro mais um, porque é exatamente isso que a substituição s por (s, m + 1 − s) impõe. É a mesma regra em cada nível da árvore, portanto a melhor cabeça restante de um bloco defronta sempre a mais fraca restante, em cada ronda, sem que ninguém tenha de escrever uma segunda regra.

O que a distribuição por cabeças garante mesmo, verificado em vez de afirmado

Passe a ordem gerada por algumas asserções e o desenho revela-se. Corte a ordem de dezasseis cabeças em blocos e todo o bloco do mesmo tamanho soma o mesmo número: 17 por par, 34 por quarto, 68 por metade, 136 para o quadro inteiro — sempre o tamanho do bloco vezes (n + 1) dividido por 2. Tome a melhor cabeça de cada bloco e recupera a ordem de um quadro de metade do tamanho: os blocos de dois dão 1, 8, 4, 5, 2, 7, 3, 6, que é a ordem de oito cabeças; os blocos de quatro dão 1, 4, 2, 3. O quadro é autossemelhante, que é exatamente o que uma recursão por duplicação deve produzir.

A garantia que realmente interessa decorre de imediato. As cabeças 1 e 2 ocupam metades opostas, portanto se ambas continuarem a ganhar não se podem encontrar antes da final; as cabeças 1, 2, 3 e 4 ocupam quatro quartos diferentes, portanto duas delas não se podem encontrar antes das meias-finais. Traçar os adversários possíveis mais precoces da cabeça 1 no quadro de dezasseis dá 16 na primeira ronda, 8 ou 9 na segunda, um de 4, 5, 12, 13 na meia-final, e 2 ou 3 só na final. É esse o sentido exato da distribuição por cabeças: não protege o favorito de adversários fortes, adia-os, para que os melhores jogos do torneio caiam no fim e não na ronda inaugural.

A distribuição por cabeças também reparte os byes sem regra à parte. Encha um quadro de 128 com os inscritos 1 a 100 e inscritos fantasma 101 a 128, gere a ordem pela recursão e leia que inscritos reais ficam emparelhados com fantasmas: são exatamente as cabeças 1 a 28, contíguas e por ordem. Ninguém teve de decidir que os byes iriam para as melhores cabeças — a mesma substituição que emparelha s com m + 1 − s põe as cabeças mais altas em frente aos lugares de número mais alto, que são justamente os vazios. Vale a pena verificar isto na ferramenta que usar, porque um gerador que dá byes a inscritos arbitrários partiu a distribuição por cabeças, não só os byes.

Total de jogos: n − 1, para todo o n, numa linha

Cada jogo de um torneio de eliminação direta elimina exatamente um inscrito — é isso que eliminação direta significa. No fim, exatamente um inscrito não foi eliminado, portanto exatamente n − 1 foram. Uma eliminação por jogo significa então exatamente n − 1 jogos, seja qual for o tamanho do quadro, sejam quais forem os byes, seja qual for a distribuição. Vinte e três inscritos jogam 22 jogos; 100 inscritos jogam 99; 129 inscritos jogam 128. Nunca é preciso somar as rondas, e os byes não entram no cálculo de todo, porque um bye não é um jogo e não elimina ninguém.

O mesmo argumento de contagem põe preço aos outros formatos. Na dupla eliminação todos menos o campeão têm de perder duas vezes, portanto há que produzir 2(n − 1) derrotas, e como cada jogo produz exatamente uma, o calendário precisa de 2n − 2 jogos. Se o finalista saído do quadro de perdedores ganhar a grande final, entregou ao jogador até então invicto a sua primeira derrota, e joga-se um jogo de reposição para lhe dar uma segunda — 2n − 1 jogos nesse caso. Ambos os números são exatos, e qual deles calha decide-se no próprio dia. O todos contra todos é outro animal: cada par encontra-se uma vez, portanto a contagem é C(n,2) = n(n − 1)/2, que cresce de forma quadrática. Com 100 inscritos são 4 950 jogos contra 99 de uma eliminação direta, um fator de exatamente 50.

Escolher um formato a partir dos números

Os três formatos trocam jogos por informação. A eliminação direta é o torneio mais barato possível — n − 1 jogos, teto(log2 n) rondas — e produz exatamente um facto fiável: a identidade do vencedor. Tudo o que fica abaixo do primeiro lugar é um artefacto do sorteio: os meias-finalistas derrotados não ficam ordenados entre si, e um inscrito forte que cruza o campeão na segunda ronda acaba de forma indistinguível de um fraco. A dupla eliminação compra uma segunda oportunidade por cerca do dobro dos jogos e cerca de uma ronda a mais, e elimina o pior modo de falha: um bom inscrito eliminado por um único mau dia.

O todos contra todos dá uma classificação completa e cobra-a de forma quadrática. Doze inscritos jogam 66 jogos em vez de 11; 23 jogam 253 em vez de 22; 48 jogam 1 128 em vez de 47. Precisa ainda de n − 1 rondas quando n é par e n rondas quando n é ímpar, porque com um plantel ímpar alguém descansa em cada ronda. O compromisso prático que a maioria dos grandes eventos usa é uma fase de grupos seguida de um quadro: o todos contra todos dentro de grupos pequenos produz uma classificação defensável a baixo custo, e a eliminação direta custa depois um jogo por apurado eliminado. Escolha o que escolher, calcule o número de jogos antes de reservar o recinto — a diferença entre 99 e 4 950 não é um detalhe de planeamento.

Perguntas frequentes

Quantos byes precisa um torneio com 23 inscritos?

Nove. O tamanho do quadro é a menor potência de dois não inferior a 23, que é 32, e o número de byes é isso menos o número de inscritos: 32 − 23 = 9. A fórmula é geral — byes = 2^teto(log2 n) − n — e é uma subtração, não uma regra prática. A primeira ronda tem então n menos metade do quadro, ou seja 23 − 16 = 7 jogos, e a aritmética fecha: 7 × 2 = 14 pessoas jogam, 9 recebem bye, 14 + 9 = 23, e 7 + 9 = 16 sobreviventes entram na segunda ronda, que é exatamente metade do quadro. A partir daí não há mais byes, porque o plantel volta a ser uma potência de dois. O torneio inteiro são 5 rondas e 22 jogos.

Qual é a ordem padrão das cabeças de série num quadro de 16?

1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11 — lido como oito jogos de primeira ronda, é 1 c. 16, 8 c. 9, 4 c. 13, 5 c. 12, 2 c. 15, 7 c. 10, 3 c. 14, 6 c. 11. Em vez de o decorar, gere-o: parta da lista [1] e substitua repetidamente cada cabeça s pelo par (s, m + 1 − s), onde m é o tamanho que a lista vai atingir. Quatro duplicações dão a ordem acima; cinco dão a ordem de 32 cabeças, e assim por diante. O resultado é verificável em vez de acreditado — cada emparelhamento da primeira ronda soma 17, cada quarto da lista soma 34 e cada metade 68, as cabeças 1 e 2 caem em metades opostas, e as cabeças 1 a 4 em quatro quartos diferentes.

Porque é que as melhores cabeças são emparelhadas com as últimas?

Para empurrar os encontros entre inscritos fortes o mais tarde possível. Emparelhar 1 com 16 e 2 com 15 não visa dar aos favoritos um início fácil; é a única forma de os colocar de modo que não se possam encontrar cedo. A recursão que produz a ordem põe as cabeças 1 e 2 em metades opostas e as cabeças 1, 2, 3, 4 em quatro quartos diferentes: a cabeça 1 só pode defrontar 2 ou 3 na final e não pode cruzar nenhuma de 4, 5, 12 ou 13 antes da meia-final. Trace os adversários possíveis mais precoces da cabeça 1 num quadro de 16 e obtém 16 na primeira ronda, 8 ou 9 na segunda, um de 4, 5, 12, 13 na meia e 2 ou 3 na final. O objetivo de desenho é um torneio cujos melhores jogos acontecem no fim, e sai automaticamente de uma única regra de substituição.

Quantos jogos vai o meu torneio precisar?

Para eliminação direta, n − 1, e não há nada para consultar. Cada jogo elimina exatamente um inscrito, no fim resta exatamente um, portanto ocorreram exatamente n − 1 eliminações e logo n − 1 jogos. Os byes não mudam nada, porque um bye não é um jogo. A dupla eliminação exige que todos menos o campeão percam duas vezes, ou seja 2(n − 1) derrotas e portanto 2n − 2 jogos; se o inscrito vindo do quadro de perdedores ganhar a grande final, joga-se um jogo de reposição e o total é 2n − 1. O todos contra todos faz cada par jogar uma vez, ou seja C(n,2) = n(n − 1)/2 jogos, em n − 1 rondas se n for par e n rondas se n for ímpar. Para 100 inscritos, os três formatos custam respetivamente 99, 198 ou 199, e 4 950 jogos.

Os byes devem ir para as melhores cabeças de série?

Já vão, se construir o quadro corretamente — nunca tem de o decidir à parte. Complete o quadro até ao seu tamanho em potência de dois com inscritos fantasma numerados acima dos reais, gere a ordem pela recursão de duplicação e leia quem defronta um fantasma. Para 100 inscritos num quadro de 128 são exatamente as cabeças 1 a 28, contíguas e por ordem, porque a mesma substituição que emparelha s com m + 1 − s põe as cabeças mais altas em frente aos lugares de número mais alto, que são justamente os vazios. Seguem-se duas consequências. Primeira, o número de byes e a identidade de quem os recebe vêm de uma só construção, não de duas regras que podem divergir. Segunda, um gerador que espalha os byes por inscritos arbitrários partiu também a distribuição por cabeças, e vale a pena substituí-lo.