En un torneo de hockey participan una cantidad impar de $n$ equipos. Cada equipo juega exactamente un partido con cada uno de los otros. En este torneo, cada equipo recibe $2$ puntos por partido ganado, $1$ punto por partido empatado y $0$ puntos por partido perdido. Al terminar el torneo se observó que todos los puntajes obtenidos por los $n$ equipos era diferentes. Para cada $n$, determinar la mayor cantidad posible de empates que pudo tener este torneo.
Esta prueba es un poco larga. Cuando entregás un problema nacional no creo que sea necesario hacerlo con este nivel de detalle, así que pueden saltearse algunas partes.
Primero defino algunas convenciones y variables para resolver este problema (esto probablemente tengan que leerlo).
Primero, vamos a alterar el problema para que ganar te de 1 punto, empatar 0, y perder -1. La solución va a ser la misma porque lo único que importa para que una solución sea válida es que todos los puntajes totales sean distintos, que no cambia con esta alteración porque las diferencias entre los resultados son iguales.
Vamos a llamar $E_1, E_2, E_3, ..., E_n$ a los equipos.
Llamamos $P_d$ a la cantidad de partidos definidos (que terminaron en victoria o derrota), $P_e$ a la cantidad de partidos empatados. La cantidad de victorias de todos los equipos (y la cantidad de derrotas tambien) es igual a $P_d$.
Llamamos $p_+$ a la suma de los puntajes de los equipos con puntaje positivo, y $p_-$ a lo mismo pero con puntaje negativo. $p_+ + p_- = 0$
Llamamos $e_+$ a la cantidad de equipos con puntaje positivo, y $e_-$ a lo mismo pero con puntaje negativo. $e_0$ a lo mismo pero con puntaje 0. $e_+ + e_- + e_0 = n = 2k + 1$. $e_0 \leq 1$ entonces $e_+ + e_- \geq 2k$
Sea $k = \frac{n - 1}{2}$. Entonces $n = 2k + 1$
$P_t$ es la cantidad de partidos totales.
Cada equipo juega con todos los otros equipos, entonces $P_t = \frac{n(n - 1)}{2} = \frac{(2k + 1)2k}{2} = (2k + 1)k = 2k^2 + k$
Construyo un ejemplo muy bueno para $n = 7$, donde $P_e = \frac{3k^2}{2} + \frac{k}{2}$
Los numeros en las casillas indican cuantos puntos ganó el equipo de la izquierda con el resultado del partido. Cuando no hay nada, el partido terminó en empate y el resultado es $0$. Esta tabla funciona porque todos los equipos tienen resultados distintos. Está reflejado diagonalmente, porque si, por ejemplo, $E_6$ le ganó a $E_2$, entonces $E_2$ perdió contra $E_6$
Creo que es bastante claro como se puede generalizar este ejemplo para otros $n$.
Pruebo que $P_e = \frac{3k^2}{2} + \frac{k}{2}$ para todo $n$ con este método de generar resultados de torneos.
Si queremos formalizar este método para generar resultados de torneos, vamos a decir que un equipo $E_a$ le gana a otro equipo $E_b$ si $a - b > k$.
La otra condición se puede derivar de esta. Un equipo $E_a$ le pierde contra otro equipo $E_b$ si $b - a > k$. Este es el inverso de la otra condición.
Pruebo que el puntaje total para el equipo $E_{k + 1 + i}$:
Primero vemos cuándo gana:
$a = k + i + 1$
$a - b > k$
$k + i + 1 - b > k$
$i + 1 > b$.
Como $b$ va de $1$ a $n$, entonces gana exactamente $i$ veces. (por ejemplo, si $i = 1$ gana solo cuando $2 > b$, que es cuando $b = 1$ que solo ocurre una vez) (pero solo si $i > 0$, porque no puede ganar una cantidad negativa de veces).
Ahora vemos cuándo pierde:
$a = k + i + 1$
$b - a > k$
$b - k - i - 1$
$k$
$b - 2k > i$
$b - n + 1 - 1 > i$
$b - n > i$
$n - b > -i$.
Como $b$ va de $1$ a $n$ esta condición se cumple $-i$ veces (pero solo si $i < 0$, porque el equipo no puede perder una cantidad negativa de veces).
Entonces el puntaje del equipo $E_{k + i + 1}$ es siempre $i$. Con esto probamos que todos los equipos tienen puntajes distintos con esta configuración cualquiera sea el valor de $k$, porque $i$ es distinto para cada equipo.
Los únicos equipos que ganaron son lo que tienen puntaje positivo, es decir, $i$ positivo. Entonces la suma de sus puntajes ($p_+$) es la cantidad de victorias en el torneo ($P_d$).
$k + i + 1$ va de $1$ a $n$ porque $k + i + 1$ es el numero del equipo, entonces:
$k + i + 1 \leq 2k + 1$
$i \leq k$
Ya descubrimos que sus puntajes totales individuales son iguales a $i$ para cada equipo. Entonces, la suma de sus puntajes es la suma de sus valores de $i$, que van de $1$ a $k$.
Por la suma de Gauss, esto es $P_d = p_+ = \frac{k(k - 1)}{2} = \frac{k^2 - k}{2}$.
En nuestro ejemplo, $P_d = p_+$ . Sin embargo, observemos que en general, para todo resultado del torneo, $P_d > p_+$. Esto es porque todos los puntos positivos que están en $p_+$ tienen que haber venido si o si de un partido definido cada uno. Es posible que existan mas partidos definidos no representados en los puntos, si algún equipo gano contra alguien y perdió contra alguien mas.
Ahora observemos que $p_+$ tiene que ser $\geq$ a la suma de los números entre $1$ y $k$.
Consideremos $e_+$ y $e_-$. Como $e_+ + e_- \geq 2k$, entonces por lo menos 1 de ellos es $\geq k$. Llamamos a esto $e_m$. El valor absoluto de la suma de lo puntajes de estos equipos es por lo menos la suma de los números entre $1$ y $e_m$, porque si no, por el principio del palomar hay por lo menos 2 equipos con el mismo puntaje. (por ejemplo, si hay 3 equipos con puntajes positivos que suman 5, entonces no hay manera de hacer que ningún par de 2 equipos tengan el mismo puntaje porque 1 + 2 + 3 = 6 que es el mínimo valor que se puede conseguir). La suma de estos números es $\frac{e_m(e_m - 1)}{2}$
La suma de los puntajes es o bien $p_+$ o $p_-$, entonces el valor absoluto es $p_+$ porque $p_- = -p_+$. Entonces, llegamos a lo siguiente:
Ahora ya probamos que $P_e \leq \frac{3k^2}{2} + \frac{k}{2}$ siempre. Nosotros ya construimos un método para que $P_e = \frac{3k^2}{2} + \frac{k}{2}$ para todo $k$, entonces si $P_e$ es máximo: