EGMO 2018 - P3

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

OFO - Mención-OFO 2017 FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019
Mensajes: 405
Registrado: Sab 04 Jun, 2016 11:50 pm
Medallas: 5
Ubicación: Puerto Rico

EGMO 2018 - P3

Mensaje sin leer por Violeta »

En una competencia de matemáticas hay $n$ competidores $C_1, C_2, \ldots, C_n$. Luego de un examen difícil, todos hacen la fila para ir a comer. El orden de esta fila la decide el jurado y pueden ordernarla como quiera.

Luego, el jurado escoge un competidor $C_i$ de la fila y si este competidor tiene por lo menos $i$ personas delante de él, le paga un peso al jurado y se adelanta $i$ lugares en la fila. Si hay menos de $i$ personas delante de $C_i$, el proceso acaba y el restaurante abre.

Para cada entero $n$, encontrar la cantidad máxima de pesos que se puede llevar el jurado, eligiendo el orden inicial y los competidores de manera óptima.

Nota: El competidor $C_i$ no cambia de lugar con el competidor que está $i$ personas después de él, sino que se mueve $i$ lugares hacia el frente de la fila y las $i$ personas a las que se le cuela quedan un lugar más atrás.
Para todo [math], existen [math] primos en sucesión aritmética.
Avatar de Usuario
Fran5

OFO - Medalla de Oro-OFO 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 1125
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 22
Nivel: Exolímpico
Ubicación: Santa Fe

Re: EGMO 2018 - P3

Mensaje sin leer por Fran5 »

Bellísimo problema, hay mucho para pensar por acá.
Spoiler: mostrar
Sea $\sigma$ un orden de los competidores (podemos pensarlo como una permutación $\sigma$ en $S_n$). En este caso $\sigma(j)$ es el lugar que ocupa $C_j$ en la fila, donde $1$ es la primer posición en la fila (sin nadie delante) y $n$ es la última (sin nadie detrás).

Observemos que si $\sigma(j) = k$ entonces $C_j$ tiene $k-1$ personas delante y $n-k$ personas detrás.

Definimos $f(\sigma)$ como el máximo de pesos que puede ganar el jurado en tal permutación.
Queremos hallar el máximo sobre todas las $\sigma$.

Supongamos que algún participante $C_j$ posee al menos $j$ personas detrás de él en la fila. Entonces el orden actual $\sigma$ no es óptimo: este participante podría estar $j$ lugares más atrás en una permutación $\tau$ y pagar un peso extra para ir a la posición original, de modo que $f(\tau) \geq f(\sigma)+1$

Si no hay $j$ participantes detrás de $C_j$ entonces $\sigma(j) > (n-j)$ ya que en caso contrario podríamos aplicar el proceso anterior.

Por inducción vemos que el óptimo se debería alcanzar cuando $\sigma(j) = n-j+1$, es decir, los participantes están ordenados de mayor a menor.

(hasta acá mostramos que $f(\sigma) > f(\tau)$ para cualquier orden $\tau$ que no sea de mayor a menor.

Ahora hay que calcular cuál es el mejor procedimiento en este caso.
Para casos pequeños vemos que para $n=1$ es $0$, para $n=2$ es $1$, y para $n=3$ es $4$.
Ni idea cuál es el patrón :shock:

Para $n=4$ si en cada paso mandamos al más peque adelante, obtenemos $8$, en el siguiente ejemplo
Spoiler: mostrar
1234
2134
2314
2341
3421
4213
4231
4312
4321
Pero si elegimos convenientemente, podemos hacer un poco más, de hecho $11$
Spoiler: mostrar
1234
2134
1324
3124
3214
2143
2413
4123
4213
4132
4312
4321
Cuál fue la diferencia? Antes el participante $C_1$ hizo $5$ cambios, y ahora $7$. Del mismo modo el participante $C_2$ antes hizo dos cambios, y ahora hizo $3$. En ambos ejemplos el participante $C_3$ hizo un cambio, y $C_4$ no puede hacer ninguno.

Curioso no? Veamos el siguiente ejemplo para $n=5$

Spoiler: mostrar
12345
21345
13245
31245
32145
31425
14235
41235
42135
41325
43125
43215
43152
43512
45123
45213
45132
45312
45321
53214
53142
53412
53421
54213
54132
54312
54321
Obtenemos $26$ cambios. El participante $C_5$ no cambió nunca, obviamente. El participante $C_4$ sólo cambió una vez. El participante $C_3$ cambió $3$ veces, el participante $C_2$ cambió $7$ veces y el participante $C_1$ cambió $15$ veces.

Eso nos hace pensar que el máximo será $0+1+3+7+15+ \ldots + 2^{n-1}-1= 2^n-1 -n = 2^n-(n+1)$

Teorema: El participante $C_j$ cambiará como mucho $2^{n-j}-1$ veces.

Para ello necesitamos ciertos lemas

Lema: Cada vez que un participante $C_j$ cambia, deberá adelantarse a otro participante $C_k$ con $k>j$
Demo: es trivial.

Lema: Si $C_j$ se adelanta a $C_k$, con $k>j$, una cantidad $X$ de veces, entonces $C_k$ se adelanta a $C_j$ exactamente $X-1$ veces.
Demo: en efecto, cada vez que uno se adelanta al otro cambian de orden en la fila, de modo que se tienen que adelantar alternadamente. Al principio $C_j$ está detrás de $C_k$ de modo que es el primero en adelantarse. Pero al final termina delante, eso quiere decir que también fue el último. Luego se adelantó una vez más

Ahora podemos probar el teorema.

Por inducción en $r = (n-j)$ es claro para $r= 0$ y $r=1$. Para $r \geq 2$ tenemos que la cantidad de veces que $C_{n-r}$ se adelanta en la fila es menor o igual a la suma de la cantidad de veces que intercambia lugar con $C_n$, $C_{n-1}$ hasta $C_{n-(r-1)}$. Para cada uno de ellos intercambia lugar exactamente $X+1$ veces por el lema anterior, de modo que tenemos como mucho $$\sum_{i=0}^{r-1} (2^{n-(n-r)}-1)+1 = \sum_{i=0}^{r-1} 2^{r} = 2^{r}-1 = 2^{n-j}-1$$

Esto muestra que el máximo de dinero que afanar ganar el jurado es $2^n-(n+1)$

Falta mostrar un ejemplo para cada $n$ donde efectivamente se gane esta cantidad.
Spoiler: mostrar
Por inducción, nuevamente.

Tenemos los participantes ordenados de mayor a menor. Primero hacemos $2^n-(n+1)$ movimientos en los últimos $n$ participantes, de modo que nos queda $C_{n+1}$ primero en la fila y luego vienen de menor a mayor. Luego hacemos $n$ movimientos comenzando con $C_n$ donde cada participante $C_j$ que estaba en el último puesto pasa a la posición $n-j$. Finalmente con $C_{n+1}$ al final y los otros participantes en orden inverso realizamos otros $2^n-(n+1)$ movimientos. De este modo tenemos $$2^n-(n+1)+n+2^n-(n+1) = 2^{n+1}-2n+n-2 = 2^{n+1}-(n+1 +1)$$ pesos
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro //
Responder