Skip to content

Solución: cruces en los torneos de tenis

by en 09/02/2014

¡Hola!

Una semana después, llega la hora de dar respuesta a nuestro acertijo del lunes. En él, os preguntábamos en qué eliminatoria se enfrentarían dos jugadores participantes en un torneo de tenis, dados sus números de orden.

Para eso, numerábamos a los participantes empezando por el jugador número 1, hasta 2n, donde n es el número de eliminatorias. Por ejemplo, para un torneo de 8 participantes, el cuadro de enfrentamientos (sin nombres) quedaba así:

Cruces de un torneo de tenis con 8 participantes

En la parte izquierda están nuestros 8 jugadores iniciales, enfrentándose dos a dos. De cada eliminatoria se alza vencedor un único contrincante, que pasa a la siguiente ronda, y se enfrenta con el ganador de otra eliminatoria de la fase previa.

En este contexto, os preguntábamos en qué ronda se enfrentarían, en un torneo de 8 rondas, las parejas de jugadores 5 y 6, 13 y 16, 15 y 18, 100 y 103, y 120 y 130. Gualterio fue el primero en contestar y ¡¡acertó en todas sus respuestas!! Éstas eran las rondas 1, 2, 5, 3 y 8 respectivamente. Además, nos contaba que no había necesitado el número de rondas del torneo para nada. David, poco después añadió una pequeña explicación adicional y su habitual código en Python, que dejaba entrever que la respuesta tenía relación con los números binarios. ¡¡Veamos por qué!!

Para empezar, vamos a remarcar en la figura anterior los enfrentamientos, para crear bloques:

Cruces con los bloques marcados

Vemos que en la primera ronda tenemos 4 enfrentamientos, y que cada uno sale de una pareja consecutiva de participantes. Dicho de otro modo, en la primera fase, hay un partido por cada dos participantes consecutivos.

Por su parte, en la segunda ronda tenemos dos partidos (la mitad que en la primera), y cada uno sale de un grupo de cuatro participantes. Por tanto, los cuatro primeros participantes (del 1 al 4) se enfrentarán, como muy tarde, en la segunda ronda, y los cuatro siguientes (del 5 al 8) también.

Por último, en un torneo de 8 participantes tenemos un único partido en la tercera ronda (la final). Esto es la mitad de partidos que en la ronda anterior y, obviamente, los participantes salen del primer (y único) bloque de 8 participantes iniciales.

¿Veis el patrón? Si el torneo tuviera 16 participantes, entonces la estructura de la figura estaría replicada, formando cada una una semifinal, y en la siguiente ronda (la cuarta) tendríamos un bloque del doble de tamaño. Resumiendo, si tenemos un torneo de n rondas con 2n participantes:

  • En la ronda 1 los jugadores de cada partido sale de un grupo de 2 inscritos consecutivos. Y hay 2n-1 partidos.
  • En la ronda 2, los jugadores de cada partido sale de un grupo de 4 inscritos consecutivos (2), y hay 2n-2 partidos.
  • En la ronda i, los jugadores de cada partido salen de un grupo de 2i inscritos consecutivos, y hay 2n-i partidos.
  • En la ronda n (la última), los jugadores de cada partido salen de un grupo de 2n inscritos consecutivos (todos), y hay 2n-n = 20 = 1 partido (la final).

Con estas conclusiones, para saber si dos jugadores se enfrentarán en la primera ronda basta saber si están en el mismo grupo de dos. Si no lo están, para saber si se enfrentarán en la segunda ronda basta saber si están en el mismo grupo de cuatro consecutivos, y así sucesivamente. Para eso, la numeración que tenemos resulta ser muy incómoda. Tal y como hemos hecho ya en algún acertijo anterior, lo mejor es cambiarla. Aunque nos han acostumbrado desde pequeños a contar empezando en 1, a los ordenadores y a muchas expresiones matemáticas les viene mejor empezar por 0. Por tanto, en lugar de numerar a los jugadores de 1 a 2n los consideraremos desde el 0 al 2n − 1. Así, ante la pregunta de en qué ronda se cruzan, por ejemplo, los jugadores 13 y 16, los renumeraremos a 12 y 15.

¿Por qué nos viene bien este cambio? Al hacerlo, la primera pareja de jugadores es la formada por los jugadores 0 y 1 (no 1 y 2, como antes). Si os fijáis, al dividir ambos números por 2 (sin decimales), obtenemos el mismo resultado (0). Con la siguiente pareja de jugadores que se enfrentan (los jugadores 2 y 3) ocurre exactamente lo mismo (en este caso, la división es 1). Y así sucederá con el resto de las parejas que se enfrentan en la primera ronda. Por tanto, para saber si dos jugadores se enfrentan en la primera ronda basta con saber si la división por dos de sus números (tras restar 1) es la misma. De igual forma, para saber si se enfrentarán en la segunda ronda bastará con dividir por 4 (22) y ver si el resultado es el mismo. Y para saber si se enfrentan en la ronda i dividiremos por 2i y compararemos los resultados. Si estás acostumbrado a la numeración binaria, te saltará a la vista que tanta división por potencias de dos se puede hacer muy fácilmente con rotaciones de bits, y la solución queda así muy elegante.

Solo falta una cuestión, relativa al número de rondas. Como comentó Gualterio, el número de rondas del torneo es indiferente. Los jugadores 1 y 2 (0 y 1 tras renumerarlos) se enfrentarán siempre en la primera ronda, tengamos 8 participantes al principio (como en la figura) o tengamos 256 (como las 8 rondas de nuestras preguntas). Por tanto es un dato innecesario que os dimos para despistar 🙂

Como siempre, si aún no lo has hecho y tras esta explicación te quieres animar, puedes programar y probar tu solución aquí.

¡Hasta mañana!

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: