La fila ganadora

1. Prueba a construir la fila poco a poco.
2. Si ya tienes una fila válida para k jugadores, intenta insertar al jugador nuevo en el lugar adecuado.
3. Recorre la fila hasta encontrar el primer jugador al que el nuevo haya ganado.

Respuesta: tiene razón. Esa fila siempre existe.

Vamos a construirla incorporando a los ocho jugadores uno a uno.

Con un solo jugador, la fila ya cumple la condición: no hay nadie detrás de él.

Ahora supongamos que ya hemos conseguido una fila válida con $k$ jugadores, donde $1\le k<8$:

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

y la flecha significa “ganó a”. Queremos añadir un nuevo jugador $X$.

Si $X$ ganó a $P_1$, lo colocamos al principio:

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

Si $P_k$ ganó a $X$, lo colocamos al final:

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

Queda el caso en que no puede ir ni al principio ni al final. Entonces $P_1$ ganó a $X$, pero $X$ ganó a $P_k$.

Recorremos la fila desde el principio y buscamos el primer jugador al que $X$ haya ganado. Ese jugador existe, porque $X$ ganó a $P_k$. Llámalo $P_{i+1}$. Como es el primero al que $X$ ganó, el jugador anterior, $P_i$, tuvo que ganar a $X$.

Así tenemos:

$$ P_i\to X $$

y

$$ X\to P_{i+1}. $$

Insertamos a $X$ entre ellos:

$$ P_1\to\cdots\to P_i\to X\to P_{i+1}\to\cdots\to P_k. $$

La fila sigue siendo válida, porque solo hemos reemplazado el enlace $P_i\to P_{i+1}$ por dos enlaces válidos: $P_i\to X\to P_{i+1}$.

Este procedimiento permite pasar de una fila válida de $k$ jugadores a una fila válida de $k+1$ jugadores. Empezamos con 1 jugador y repetimos el proceso hasta llegar a 8.

Así obtenemos una fila válida con los ocho ajedrecistas. Además, el razonamiento no usa nada especial del número 8: funciona igual para cualquier número de jugadores. En todo torneo sin empates existe una fila en la que cada jugador ha ganado al siguiente.