Torneo eliminatorio: poda de equipos después de cada ronda

Question

Supongamos que voy a empezar con $N$ equipos ($N$ es incluso) que están emparejados de forma aleatoria uno con el otro en la primera ronda. $\frac N2$ equipos de progreso a la siguiente ronda. Quiero que este proceso se repite hasta que queda un equipo. Pero esto es problemático si tenemos un número impar de equipos que quedan después de una ronda concluye. Mis preguntas:

• Si el número de equipos es impar después de una ronda concluye, ¿cómo debo ajustar el número de equipos? Obviamente yo sólo podía eliminar un equipo extra, pero hay una manera más eficiente de manejar, así que no tienes que mantener la eliminación de los equipos después de cada ronda? Supongo que tendría que intentar conseguir $N$ sobre la vía de $(1,2,4,8,16,\dots)$?

• Dada la poda enfoque que adopten, ¿cómo puedo derivar el número de rondas en el torneo?

Answer 1

Supongamos $2^{m-1}< N \le 2^m$. La forma usual que los torneos de manejar esto es, dando a los equipos de las despedidas, es decir, que continuará automáticamente a la siguiente ronda. Esto es equivalente a suponer que no se $2^m$ de los equipos, con $N$ real de los equipos y $2^m-N$ imaginario de los equipos que siempre pierden cuando juegan (byes). El número de rondas será exactamente $m$ en este enfoque, con el número total de equipos (real e imaginario), al ser dividido por 2 en cada paso.

El enfoque propuesto de la eliminación de equipos, incluso cuando se ganó la ronda anterior, resultaría impopular con los miembros de ese equipo. :-)

Answer 2

Hay toda una gran variedad de matemáticas de la literatura acerca de los torneos, va de nuevo, creo, de Charles Lutwidge Dodgson (mejor conocido como Lewis Carroll). Probablemente encontrarás la mayoría de ella, en estos días, bajo el título de "ciencias de la computación", donde es un concepto clave de "clasificación". Como tal, usted puede ser mejor hacer esta pregunta en el CS StackExchange sitio. El número mínimo de juegos es en realidad sólo es conocida por un número muy limitado de torneo tamaños.

Edit: yo sabía lo que me estaba olvidando de algo. Aunque la clasificación se refiere a los torneos, la selección es más directa. Algoritmos de selección de responder a preguntas como "¿Qué equipo es el mejor?" "¿Cuáles son los dos mejores equipos, en orden?" "Lo que el equipo está en el medio?". Buscar, por ejemplo "la mediana de las medianas algoritmo".