Solución del problema de Octubre, 2009

El problema:

PM89: Octubre 2009 Un torneo por eliminación es una competencia que consiste en multiples rondas. En cada ronda juegan dos competidores; el ganador pasa a la siguiente ronda, y el perdedor queda eliminado. Cuando un competidor no tiene rival asignado, se le da un pase, lo que significa que pasa directamente a la siguiente ronda. Nos interesa saber cuál es el mínimo número de pases en un torneo que tiene n competidores. Por ejemplo, cuando hay 6 participantes, el torneo puede tener dos pases en la primera ronda, o puede no tener pases en la primera ronda y tener uno en la segunda; entonces el mínimo número de pases para un torneo de 6 competidores es uno. ¿Cuál es el número mínimo de pases en un torneo por eliminación con 2010 participantes? Por diversos problemas solamente pudieron competir 1025 participantes. ¿Cuántos pases debe haber en el nuevo cuadro?

Respuestas correctas:
	Recibimos soluciones correctas de Claudio Baiocchi (Italia) Omran Kouba (Siria) Halima  Abdalla  Bashier (Regina) Tannie Lau Bojan Basic (Serbia) Matthew Lim (USA) José Borges (Portugal) Jeff Lindstrom (Ontario) Lou Cairoli (USA) John T. Robinson (USA) Dan Dima (Rumania) Uwe Schaefer (Alemania) Sébastien Dumortier (Francia) Nutheti Shivdeep (India) Magnus Jakobsson (Suecia) Albert Stadler (Suiza)

La solución:

Parece casi obvio que para obtener el número mínimo de pases en un torneo deberemos tener exactamente un pase en cualquier ronda con número impar de participantes, y ninguno en rondas con número par de participantes. Por otro lado, como el número de pases en una ronda afecta la cantidad de participantes en la siguiente, parece posible que pases extras en una ronda produzcan ahorros más adelante. Pero no es así: utilizar más que el mínimo de pases en una ronda siempre incrementa el número total de pases. En efecto, si la ronda r tiene un número par de participantes c, el número de pases en esa ronda, digamos b, también será par,  el número de participantes que pasan a la ronda  r + 1 será . Si tanto c/2 como b/2 son impares (lo que implica b ≥ 2), entonces no habría pases en esa ronda, lo que representa un ahorro de a lo sumo un pase en la ronda r + 1; pero hubo por lo menos dos pases de más en la ronda r de manera que el número total de pases aumenta. Entonces, para ronda con número par de participantes, usar más de b = 0 pases incrementa el número de pases en el torneo. Un argumento similar lleva a la misma conclusión cuando el número de participantes es impar (donde el número de pases será necesariamente impar). Mostraremos un argumento alternativo al final, pero coincidamos por ahora en que

Cuando hay c participantes en una ronda y c es par, entonces no habrá pases en esa ronda y c/2 participantes pasarán a la ronda siguiente; cuando c es impar habrá un pase en esa ronda y (c + 1)/2 participantes pasarán a la siguiente ronda.

Se sigue que el número mínimo para el torneo por eliminación con 2010 participantes sera de 3 pases ; en cada ronda el número será

2010, 1005, 503, 252, 126, 63, 32, 16, 8, 4, 2.

Hemos marcado las tres rondas en las que hay pase. De modo similar, habrá 10 pases cuando el torneo comience con 1025 participantes, un pase en cada ronda hasta llegar a la última. El número de participantes en cada ronda será

1025, 513, 257, 129, 65, 33, 17, 9, 5, 3, 2.

La mayoría de las respuestas notaron la conexión entre la regla para encontrar en número mínimo de pases y el algoritmo para convertir un número de base-10 a binario. Resulta que el número mínimo de pases en un torneo con n participantes es igual a la cantidad de ceros de la representación de n – 1 en base 2.  Dima y Robinson citaron la enciclopedia de sucesiones de enteros,
http://www.research.att.com/~njas/sequences/A080791.
Lamentablemente no hay explicación en la página web. Una manera más agradable de calcular este número es tomar h como el menor entero tal que 2^h  ≥ n.  Entonces

El número mínimo de pases en un torneo con n participantes es igual al número de unos en la representación de 2^h  – n en base 2.

Por supuesto que ambas reglas producen el mismo resultado: 2^h  – 1 es un número cuya representación en base 2 consiste de todos unos, de manera que 2^h  – n = 2^h  – 1 – (n – 1) es un número binario que tiene un uno precisamente en la posiciones donde (n – 1)₂ tiene un cero. Por ejemplo
2010 – 1 = 2009 = 11111011001₂tiene tres 0s;
2¹¹ – 2010 = 2048 – 2010 = 38 = 100110₂tiene tres 1s..
Kouba mostró otros ejemplos simples:  

            Para mostrar por qué funciona esta regla combinaremos los argumentos de Jakobsson y Dumortier con ideas de Baiocchi, Cairoli y Kouba.  Introducimos la noción de participante imaginario (por oposición a real) para redondear el número de participantes a la potencia de dos inmediata siguiente. Los participantes imaginarios juegan partidos imaginarios: el número de partidos en un torneo con n participantes es n-1 (porque todos salvo el campeón pierden una vez). Recordemos que h es el menor entero tal que 2^h  ≥ n.  Definimos

C_r el número de participantes reales en la ronda r (o sea que C₁ = n),
I_r = 2^h–r+1 – C_r el número de participantes imaginarios en la ronda r,
M_r el número de partidos reales en la ronda r,
IM_r el número de partidos imaginarios jugados entre jugadores imaginarios,
H_r el número de partidos híbridos (entre participante real e imaginario).

He aquí los números para el torneo con n = 2010 participantes utilizando la regla de que en cada ronda hay a lo sumo un partido híbrido.

Asumimos que en los partidos híbridos siempre gana el participante real; en ese caso H_r representa el número de pases en la ronda r.  El número de participantes en la siguiente ronda satisface

C_r+1 = H_r + M_r.

Este es el argumento prometido más arriba: para mantener el total en la columna H_r ta pequeño como se pueda, ponemos un partido híbrido solamente cuando es necesario: el número de partidos híbridos en cada ronda es igual al número total al número total de partidos de la ronda restado de 2^h–r (donde 2^h–r es la mitad del número total de participantes reales e imaginarios en la ronda).  Por lo tanto el número de partidos M_r + IM_r  + H_r = 2^h–r de cada ronda: si M_r decrece en k, también IM_r, y H_r  se incrementa en 2k.  Como el total en la columna M_r siempre es uno menos que el total de participantes, tenemos que para obtener el número mínimo de pases tenemos que maximizar el número de partidos imaginarios; esto es, H_r  a lo sumo 1 para cada r.

según I_r sea par o impar. 
           La tabla debería dejar en claro cómo el número de pases (que es la suma de los números en la columna H_r) se relaciona con la representación binaria de I₁ = 2^h – C₁.  En efecto, la columna H_r nos da los dígitos de I₁ en orden inverso (comenzando con las unidades): 38 = 100110₂.  En general, I_r dividido por 2 es igual a I_r+1 con resto H_r, de maner que H_r es le dígito en la posición 2^r–1 de la representación binaria de I₁.

Comentario adicional. No está claro que haya alguna ventaja en particular en desarrollar un torneo que tenga el mínimo posible de pases. La mayoría de los torneos se organizan d manera que todos los pases estén en la primera ronda (en el lenguaje de arriba, esto es decir que cada jugador imaginario juega contra un jugador real en la primera ronda, de manera que hay I_r partidos híbridos en la primera ronda y ninguno en las demás). De esta manera los organizadores controlan quiénes reciben los pases. Tal vez es más justo tener el número mínimo de pases en el sentido de que minimiza la cantidad de veces en que se enfrentan participantes que han jugado un número diferente de partidos.