En un torneo de ajedrez participan $N \geq 2$ personas. Cada par de ellas se enfrentan exactamente una vez. En cada partida, una persona recibe $2$ puntos si gana, $1$ punto si empata y $0$ puntos si pierde.
Al finalizar el torneo se publica la lista $\mathcal{P} = (p_1 \geq p_2 \geq . . . \geq p_N )$ de los puntajes que obtuvieron las $N$ personas en el torneo, ordenados de mayor a menor. Decimos que la lista $\mathcal{P}$ es buena si conociendo esta lista y a qué persona corresponde cada puntaje, se puede determinar completamente el resultado de todas las partidas del torneo.
Calcular la cantidad de listas buenas para cada $N$.
Sea $C(n)$ la cantidad de listas buenas de tamaño $n$.
Vamos a ver por inducción que $C(n) = F_{n+1}$, es decir, el $n+1$-ésimo Fibonacci, comenzando desde $1$.
Podemos ver fácil que $C(2) = 2$ y $C(3) = 3$.
Vamos ahora con el paso inductivo.
Sea $a_i$ el jugador con puntaje $p_i$.
Podemos ver que si $p_1 = 2n-2$ entonces $a_i$ ganó todas las partidas, y si lo quitamos tenemos el caso $n-1$, por lo que la lista $(p_1\geq ...\geq p_n)$ será buena si y solo si la lista $(p_2\geq ...\geq p_n)$ es buena. Hasta ahora llevamos entonces $F_n$ casos.
Además, si $p_1 = p_2 = 2n-3$, entonces $a_1$ y $a_2$ ganaron $n-2$ partidas cada uno, y empataron $1$. Como ninguno perdió, sabemos que empataron entre ellos y le ganaron a todo el resto. Quitándolos tenemos el caso $n-2$, por lo que la lista $(p_1\geq ...\geq p_n)$ será buena si y solo si la lista $(p_3\geq ...\geq p_n)$ es buena. Sumamos entonces $F_{n-1}$ casos más.
Vamos a ver ahora que si $a_1$ perdió al menos $2$ puntos, o si $a_1$ perdió $1$ punto y $a_2$ perdió al menos $2$ puntos, entonces la lista resultante no es buena.
Para esto, nos construimos un grafo que represente el problema. Va a ser un grafo dirigido en el que cada par de nodos tenga exactamente $2$ aristas entre ellos. Para los nodos $A$ y $B$, tiramos $2$ aristas de $A$ a $B$ si $A$ perdió con $B$, $2$ aristas de $B$ a $A$ si $B$ perdió con $A$, y $1$ y $1$ si empataron.
Vamos a demostrar que en cualquiera de los $2$ casos tenemos un ciclo (dirigido) de tamaño mayor a $2$. Así, podemos cambiar el sentido de todas las aristas de este ciclo, y obtenemos otra solución con los mismos puntajes, por lo que la lista no es buena.
Caso 1: $a_1$ perdió al menos $2$ puntos, es decir, $p_1\leq 2n-4$.
Esto quiere decir que todos perdieron al menos $2$ puntos, y por lo tanto cada nodo tiene al menos $2$ aristas salientes. Comencemos entonces en un nodo cualquiera, y empecemos a caminar siguiendo el sentido de las aristas. Notemos que si entramos al nodo $B$ desde $A$, entonces podemos salir de $B$ a un nodo distinto de $A$. Esto es así pues sabemos que existe la arista $AB$ y que $B$ tiene al menos $2$ aristas salientes. Aunque una de estas sea $BA$, nos queda otra por la que podemos salir.
Podemos seguir caminando así. Como la cantidad de nodos es finita, en algún momento repetiremos un nodo, y ahí encontramos un ciclo de tamaño mayor a $2$ (ya que siempre salimos por un nodo que no es por el que llegamos).
Caso 2: $a_1$ perdió $1$ punto y $a_2$ perdió al menos $2$ puntos. Es decir, $p_1 = 2n-3$ y $p_2\leq 2n-4$.
En este caso $a_1$ tiene $1$ arista saliente, y todos los otros tienen al menos $2$. Podemos hacer lo mismo que en el caso anterior si comenzamos en $a_1$, ya que a partir de ahí se seguirá cumpliendo la propiedad de que siempre que entramos podemos salir, y si volvemos a $a_1$ no necesitamos salir porque ya es un ciclo. Entonces en este caso también encontramos nuestro ciclo de tamaño mayor a $2$.
Con estos $2$ casos demostramos que las únicas listas buenas son las que vimos al principio. Por lo tanto $C(n) = F_n + F_{n-1} = F_{n+1}$, y estamos.
