Un compañero de trabajo es un gran fan de Sumo. Hace poco vino a verme con un problema que se preguntaba desde hace años:
En un torneo de sumo profesional hay 42 luchadores. Un torneo dura 15 días. Cada luchador pelea una vez al día. Cada combate es con un oponente diferente. No se repiten los combates. Cada combate se salda con una victoria o una derrota, no hay empates. Cada luchador terminará con un registro de victorias y derrotas que sume 15 (por ejemplo, 15-0, 0-15, 8-7, 7-8).
¿Cuál es el número máximo de luchadores de los 42 que pueden terminar con un récord ganador (8-7 o mejor )? ¿Cuál es el número máximo que puede terminar con un récord perfecto de 15-0?
Para el propósito de este problema, ignoraremos las diferencias de habilidad y asumiremos que todos los luchadores son iguales entre sí. En realidad, es casi seguro que el luchador número 1 ganará siempre al número 42. Para simplificar, trataremos los combates como si fueran lanzamientos de moneda al azar. Además, los emparejamientos exactos pueden ser aleatorios. En un torneo real, los luchadores sólo luchan contra otros luchadores de su mismo rango; el nº 1 nunca tendría que sufrir la indignidad de luchar contra el nº 42. Como estamos ignorando la habilidad, este hecho también puede pasarse por alto. También debemos asumir que ningún luchador abandona el torneo antes de que terminen los 15 días.
Estoy bastante seguro de que la respuesta a la segunda parte de sus preguntas es n/2 o 21. Si después del primer día todos los ganadores siguen luchando contra los perdedores y siguen ganando, entonces creo que el torneo terminará antes de que se agoten todos los partidos. Sin embargo, no estoy seguro de cómo probar esto.
En cuanto a la primera parte del problema, no sé ni por dónde empezar. He podido encontrar algo de información sobre la programación eficiente de torneos parciales de ida y vuelta, pero nada sobre la caracterización de sus resultados.
