acertijo del día

Ocho jugadores y veintiocho partidas sin tablas. El reto no es encontrar al mejor, sino encadenar las victorias.

La fila ganadora

Estratega
Jugadas maestras

Enunciado

Ocho ajedrecistas juegan un torneo todos contra todos. Cada pareja se enfrenta una vez y ninguna partida termina en tablas.

Al terminar, quieres colocarlos en una fila de modo que cada jugador haya vencido al que está inmediatamente detrás de él.

¿Puede hacerse siempre, sean cuales sean los resultados, o existe algún torneo que lo haga imposible?

Ver solución

Solución

Respuesta: siempre puede hacerse.

Construiremos la fila añadiendo a los jugadores uno por uno.

Supongamos que ya tenemos una fila válida:

$ P_1\to P_2\to\cdots\to P_k, $

donde cada flecha significa que el jugador de la izquierda venció al de la derecha. Queremos incorporar a un nuevo jugador \(X\).

Recorremos la fila desde el principio y buscamos el primer jugador \(P_j\) al que \(X\) haya vencido.

Si ese primer jugador es \(P_1\), colocamos a \(X\) al comienzo:

$ X\to P_1\to\cdots\to P_k. $

Si \(j>1\), como \(P_j\) es el primero al que venció \(X\), este no venció a \(P_{j-1}\). Como no hay tablas, necesariamente

$ P_{j-1}\to X. $

También sabemos que

$ X\to P_j. $

Por tanto, podemos insertar a \(X\) entre ambos:

$ P_1\to\cdots\to P_{j-1}\to X\to P_j\to\cdots\to P_k. $

Si \(X\) no venció a ningún jugador de la fila, todos ellos lo vencieron, en particular \(P_k\). Entonces basta colocarlo al final:

$ P_1\to\cdots\to P_k\to X. $

En todos los casos obtenemos una fila válida con un jugador más. Empezando con un solo jugador y repitiendo esta inserción, terminamos colocando a los ocho.

El argumento no depende del número 8: funciona en cualquier torneo sin empates.

Idea esencial: insertar cada nuevo jugador justo antes del primero al que haya vencido.