El torneo sin árbitro

**Qué entrena:** construcción inductiva en grafos dirigidos de torneo.

En un torneo de todos contra todos con $n$ jugadores:

• cada par juega exactamente una vez,
• no hay empates.

¿Siempre se puede ordenar a los jugadores en una fila
$P_1,P_2,\dots,P_n$ tal que cada jugador haya ganado al que tiene justo a su derecha?

Es decir:
$$
P_1 \to P_2 \to \cdots \to P_n.
$$

1. Prueba por inducción en n: Si X gana a P_1, colócalo al inicio.
2. Prueba por inducción en n: Paso inductivo: supón una fila válida para n-1 jugadores: P_1to P_2to·sto P_ n-1.
3. Tramo final: Prueba por inducción en n: Paso inductivo: supón una fila válida para n-1 jugadores: P_1to P_2to·sto P_ n-1. Luego, en otro caso, existe algún índice i tal que: P_ito X y Xto P_ i+1 , y se inserta entre P_i y P_ i+1.

[Volver al problema](#prob-torneo-sin-arbitro-fila-ganadora)

**Respuesta:** Sí, siempre existe.

Prueba por inducción en $n$:

• Base $n=1$: trivial.
• Paso inductivo: supón una fila válida para $n-1$ jugadores:

$$
P_1\to P_2\to\cdots\to P_{n-1}.
$$

Añade un jugador nuevo $X$.

1. Si $X$ gana a $P_1$, colócalo al inicio.
2. Si $P_{n-1}$ gana a $X$, colócalo al final.
3. En otro caso, existe algún índice $i$ tal que:

$$
P_i\to X\quad\text{y}\quad X\to P_{i+1},
$$
y se inserta entre $P_i$ y $P_{i+1}$.

En los tres casos la propiedad “cada uno gana al de la derecha” se conserva.

Por inducción, existe para todo $n$.

---