Skip to content

Solución: torneos

by en 09/06/2013

¡Hola!

Todavía en fase de recuperación de la “resaca” de ProgramaMe, aquí estamos un domingo más para resolver el acertijo de la semana pasada.

Pero antes de eso, queremos agradecer a todos los asistentes al concurso del viernes su presencia allí, y felicitarles por su actuación. ¡Y enhorabuena a Ángel, lector del blog y “comentador habitual”, por su fantástico tercer puesto con 6 problemas resueltos!

Y, ahora sí, vamos a por el acertijo. Os preguntábamos cuántos “partidos” debían jugarse en torneos en los que participaran un número variado de jugadores, y en cada “partido” se enfrentaran simultáneamente varios de ellos.

La primera pregunta era para un torneo de 10 participantes, en los que competían de 4 en 4, con un único clasificado en cada uno de esos “partidos”. En los comentarios, David ¡acertó! Efectivamente, el número de “partidos” es 3. En la primera fase se organizan 2 enfrentamientos con un total de 8 participantes. Los 2 restantes (de los 10) pasan a la final sin competir, junto con los ganadores de cada uno de los enfrentamientos de la primera fase. Esa final, que hace el tercer “partido”, decide el ganador.

Un torneo similar pero con 11 participantes resulta imposible, pues no hay manera de conseguir cuadrar los partidos. ¡Siempre sobrará un participante!

El siguiente torneo consistía en 100 participantes compitiendo de 10 en 10. Como antes, David también acertó. El número de enfrentamientos es de 11, con una fase inicial de 10 partidos donde compiten todos, que nos proporciona 10 ganadores que compiten en la final.

Por último os preguntábamos el número de enfrentamientos para un torneo de 999 personas compitiendo de 32 en 32. David se aventuró a decir que era imposible y ¡acertó también! Pero, ¿por qué?

En realidad, para sistematizar la manera de contar el número de enfrentamientos es mejor olvidarse de que hay diferentes fases (final, semifinales, cuartos de final, etcétera), y pensar de manera “lineal”. Si tenemos P participantes al principio, y en cada enfrentamiento compiten C (de “competidores”), entonces tras un único partido nos quedarán P-(C-1) participantes; el -1 es importante, pues de los C que han competido uno se mantiene en el torneo por ser el ganador.

Tras el siguiente enfrentamiento, quedarán en el torneo P-(C-1)-(C-1) participantes. Fijáos que el acertijo no nos preguntaba quién tenía que jugar con quién; sólo el número de enfrentamientos. Es razonable pensar que, normalmente, en el segundo “partido” no participará el ganador del primero, por haber pasado a la siguiente ronda. Pero en realidad ¡eso da lo mismo! Lo que nos interesa es cuántos partidos hay, y las personas concretas que juegen no son importantes.

Con este patrón, es fácil darse cuenta que tras n partidos nos quedarán P-n·(C-1). ¿No os recuerda esto a algo? ¡¡Es muy parecido al acertijo “Cigarros gratis“!! Al final, lo que queremos es que quede un único ganador, de manera que, conociendo C y P, queremos saber si hay algún n (número de enfrentamientos) tal que:

P – n·(C-1) = 1

o, dicho de otra forma si existe un n entero (sin decimales) tal que:

n = (P-1) / (C-1)

Además, ese n será precisamente el número que estamos buscando.

En la primera pregunta, P era 10 y C 4. Fijáos que (P-1)/(C-1) es precisamente 3, tal y como dedujimos. Sin embargo, con P=11 y C=4, la división no sale justa, por lo que el torneo era imposible.

Con P=100 y C=10, también sale justo, con n=99/9 = 11. La última pregunta, con P=999 y C=32, sin embargo, no da división exacta pues 998/31 es 32.19 y, por tanto, como dijo David el torneo es imposible.

Como siempre, si os entretiene programar, podéis probar vuestra solución aquí. ¡Es fácil después de haberos contado cómo es! 🙂

¡Hasta la próxima!

Anuncios

From → Soluciones

Dejar un comentario

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: