Contando ternas

[julianferres_]

Hay un torneo de ajedrez con [math]n \geq 3 personas. Cada persona jugó exactamente una vez con el resto, ningun partido terminó en empates.
Decimos que una terna [math]A,B,C es ciclica si y solo si [math]A le ganó a [math]B, [math]B le ganó a [math]C y [math]C le ganó a [math]A.

Demostrar que la cantidad de ternas ciclicas es a lo sumo [math]\frac{1}{4} \binom{n+1}{3}

[julianferres_]

Creo que vale la pena por las ideas

Spoiler: mostrar

Denotamos [math]a_1,a_2,...,a_n a los participantes y [math]b_1,...,b_n al número de partidos que cada uno ganó
Vamos a contar las ternas con un "ganador" (la persona que vence a los otros dos)... Luego restando a [math]\binom{n}{3} (la cantidad de ternas totales) vamos a llegar a lo pedido

Una observación importante es que cada terna con un "ganador" tiene tambien un "perdedor" (La persona que perdió contra los otros dos)

Ademas cada [math]a_i forma parte de [math]S_i=\binom{b_i}{2}+\binom{n-b_i-1}{2} ternas no ciclicas.
Queremos minimizar este número. (Asi maximizaremos las ciclicas)

[math]\binom{b_i}{2}+\binom{n-b_i-1}{2}=\frac{2b_i^2-2b_in+2b_i+n^2-3n+2}{2}=\frac{2b_i(b_i-n+1)+n^2-3n+2}{2}
Y en el ultimo termino tenemos que [math]b_i(n-b_i-1) \leq (\frac{b_i+n-b_i-1}{2})^2=\frac{(n-1)^2}{4}

Entonces [math]S_i \geq \frac{-\frac{(n-1)^2}{2}+n^2-3n+2}{2}=\frac{n^2-4n+3}{4} y hay a lo sumo [math]\frac{n}{2}( \frac{n^2-4n+3}{4}) ternas no-ciclicas (esto vino de minimizar y sumar para todo [math]a_i y luego dividir por [math]2 porque cada terna se conto dos veces (una por el perdedor y otra por el ganador)

Finalmente [math]ciclicas \leq \binom{n}{3}-\frac{n}{2}( \frac{n^2-4n+3}{4})=\frac{n^3-n}{24}=\frac{1}{4} \binom{n+1}{3}

como era requerido[math]\blacksquare