Nacional 2022 - Nivel 2 - Problema 6

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Monazo

OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Mención-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
OFO - Jurado-OFO 2023 OFO - Jurado-OFO 2024
Mensajes: 381
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 17
Nivel: Exolímpico

Nacional 2022 - Nivel 2 - Problema 6

Mensaje sin leer por Monazo »

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.
Soy una Estufa en Piloto
:shock:
Avatar de Usuario
fran :)

FOFO 12 años - Mención-FOFO 12 años OFO - Medalla de Plata-OFO 2023 FOFO 13 años - Copa-FOFO 13 años
Mensajes: 20
Registrado: Mié 22 Jun, 2022 6:04 pm
Medallas: 3
Nivel: 3
Ubicación: Buenos Aires

Re: Nacional 2022 - Nivel 2 - Problema 6

Mensaje sin leer por fran :) »

Spoiler: mostrar
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).
Spoiler: mostrar
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}$
Spoiler: mostrar
Vamos a armar una tabla con una posibilidad muy buena para $n = 7$ ($k = 3$)

\begin{array}{|c|c|c|c|c|c|c|c|} \hline
- & E_1 & E_2 & E_3 & E_4 & E_5 & E_6 & E_7 & Total \\ \hline
E_1 & - & & & & -1 & -1 & -1 & -3 \\ \hline
E_2 & & - & & & & -1 & -1 & -2 \\ \hline
E_3 & & & - & & & & -1 & -1 \\ \hline
E_4 & & & & - & & & & 0 \\ \hline
E_5 & 1 & & & & - & & & 1 \\ \hline
E_6 & 1 & 1 & & & & - & & 2 \\ \hline
E_7 & 1 & 1 & 1 & & & & - & 3 \\ \hline
\end{array}

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.
Spoiler: mostrar
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}$.

$P_e + P_d = P_t$
$P_e = P_t - P_d$
$P_e = 2k^2 + k - \frac{k^2}{2} - \frac{k}{2}$
$P_e = \frac{3k^2}{2} + \frac{k}{2}$
Ahora pruebo que $P_e \leq \frac{3k^2}{2} + \frac{k}{2}$ para todo $k$
Spoiler: mostrar
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:

$p_+ \geq \frac{e_m(e_m - 1)}{2}$
$p_+ \geq \frac{k(k - 1)}{2}$ porque $e_m \geq k$
$P_d \geq \frac{k(k - 1)}{2}$ porque $P_d \geq p_+$
$P_t - P_e \geq \frac{k(k - 1)}{2}$ porque $P_d = P_t - P_e$
$-P_t + P_e \leq -\frac{k(k - 1)}{2}$
$P_e \leq P_t - \frac{k(k - 1)}{2}$
$P_e \leq 2k^2 + k - \frac{k(k - 1)}{2}$
$P_e \leq \frac{3k^2}{2} + \frac{k}{2}$
La respuesta final, en términos de $n$:
Spoiler: mostrar
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:

$P_e(n) = \frac{3\frac{n - 1}{2}^2}{2} + \frac{\frac{n - 1}{2}}{2}$
$P_e(n) = \frac{3\frac{n^2 - 2n + 1}{4}}{2} + \frac{n - 1}{4}$
$P_e(n) =\frac{3n^2 - 6n + 3}{8} + \frac{n - 1}{4}$
$P_e(n) =\frac{3n^2 - 6n + 3}{8} + \frac{2n - 2}{8}$
$P_e(n) =\frac{3n^2 - 4n + 1}{8}$

Comprobamos para $n = 7$:
$P_e(7) =\frac{3 \cdot 49 - 4 \cdot 7 + 1}{8}$
$P_e(7) =\frac{147 - 28 + 1}{8}$
$P_e(7) =\frac{120}{8}$
$P_e(7) =15$
1  
$$\phantom{[muajajacaracteresinfinitos=}\begin{matrix}(λx.F\;a)&→&x=a;F\\(\{x_0\;x_1\}\;a)&→&\{a_0\;a_1\}=a;\{(x_0\;a_0)\;(x_1\;a_1)\}\\\{a_0\;a_1\}=\{b_0\;b_1\}&→&a_0=b_0;a_1=b_1\\\{a_0\;a_1\}=λx.F&→&x=\{x_0\;x_1\};\{f_0\;f_1\}=F;a_0=λx_0.f_0;a_1=λx_1.f_1\end{matrix}\phantom{]}$$
Responder