Selectivo de IMO 2021 - Problema 3

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

Selectivo de IMO 2021 - Problema 3

Mensaje sin leer por Monazo »

Juli y Mica juegan al siguiente juego. Juli elige $100$ números reales no negativos, no necesariamente distintos $x_1,x_2,\dots ,x_{100}$ cuya suma sea $1$, y le dice los números a Mica. Mica agrupa los números en $50$ parejas a su elección, calcula la multiplicación de los dos números en cada pareja, y escribe en el pizarrón el mayor de estos $50$ resultados. Juli quiere que el número escrito sea lo mayor posible, mientras que Mica quiere que sea lo menor posible. ¿Qué número resultará escrito si los dos juegan de manera óptima?
Soy una Estufa en Piloto
:shock:
Fran B
Mensajes: 9
Registrado: Mar 18 Jun, 2019 7:29 pm
Nivel: 2

Re: Selectivo de IMO 2021 - Problema 3

Mensaje sin leer por Fran B »

Spoiler: mostrar
Digamos que $x_{100} \geq x_{99} \geq ... \geq x_2 \geq x_1$.
Veamos que Mica siempre elige las parejas $(x_1, x_{100}); (x_2, x_{99}), ..., (x_i, x_{101-i})$, o bien otra configuración en la cual el número escrito es el mismo. Veamos en general por inducción que para cualquier cantidad de números $n \geq 4$ con $n$ par se empareja el menor con el mayor, el segundo menor con el segundo mayor, etc.

Para $n = 4$, las posibles parejas son:
$(x_1, x_2), (x_3, x_4)$, y como $x_4 \geq x_3 \geq x_2 \geq x_1$, el número escrito es $x_4x_3$.
$(x_1, x_3), (x_2, x_4)$, y como $x_4 \geq x_3$ y $x_2 \geq x_1$, el número escrito es $x_4x_2$.
$(x_1, x_2), (x_3, x_4)$, donde el número escrito puede ser $x_4x_1$ o $x_3x_2$.

$x_4x_3 \geq x_4x_2 \geq x_4x_1$ y $x_4x_3 \geq x_4x_2 \geq x_3x_2$, por lo que elegir $(x_1, x_2), (x_3, x_4)$ minimiza el número escrito.

Supongamos que se cumple la propiedad para $n$. Luego, para el caso de $n+2$, comparemos lo que pasa al emparejar $x_1$ con $x_{n+2}$ y $x_a$ con $x_{n+2}$ para un $a > 1$.
En el primer caso, por hipótesis inductiva, en los $n$ números del $x_2$ al $x_n+1$ se emparejará $(x_2, x_{n+1}), (x_3,x_n), ..., (x_ix_{n+3-i})$.
En el segundo, por hipótesis inductiva, se emparejará $(x_i, x_{n+2-i})$ para $i < a$ y $(x_i, x_{n+3-i})$ para $i > a$.
Los productos con $i > a$ se mantuvieron igual en ambos casos, y los productos con $1 < i \leq a$ son menores en el segundo caso que en el primero, pero $x_{n+2}x_a$ es mayor a todos esos productos en ambos casos (ya que si $1 < i \leq a \Rightarrow x_i \leq x_a$ y $x_{n+2-a} < x_{n+3-a} < x_{n+2}$), por lo que en el primer caso se escribe un número igual o mayor.

Después Juli maximizará el número escrito al elegir los 100 números que sumen 1 sabiendo que se escribirá el mayor entre $x_1x_{100}, x_2x_{99}, etc.$
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 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 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Selectivo de IMO 2021 - Problema 3

Mensaje sin leer por Gianni De Rico »

Hola @Fran B
Spoiler: mostrar
Lo que pusiste está muy bien como una idea, pero no termina de resolver el problema.
En este tipo de situaciones donde se te pide maximizar y/o minimizar algo, es importante dar no sólo una forma en la que se obtendría lo pedido, sino también mostrar un ejemplo en el que efectivamente se alcance. Por ejemplo, digamos que la respuesta del problema (el número que queda escrito) es $X$, entonces habría que mostrar que Mica siempre puede lograr que el resultado sea menor o igual que $X$ sin importar lo que elija Juli, y dar $100$ números para los que Juli pueda asegurarse que el resultado de Mica sea (al menos) $X$.
Como mínimo siempre tenés que dar algún ejemplo (no importa si al final la respuesta es otra), si no hacés eso te van a considerar el problema como no resuelto directamente.

Lo que escribiste vos es esencialmente Rearrangement, de modo que sabés de qué forma le va a convenir jugar a Mica, te faltaría ver que haciendo eso siempre puede garantizar un resultado menor o igual a $X$ y dar el ejemplo de Juli.
♪♫ do re mi función lineal ♪♫
muebalee
Mensajes: 2
Registrado: Jue 09 Jun, 2022 11:53 pm
Nivel: 3

Re: Selectivo de IMO 2021 - Problema 3

Mensaje sin leer por muebalee »

buenas, mi solución no se basa en ningún argumento y no se ve tan bien, pero tiene sentido común.
Si consideramos un numero "A" menor a 1 pero que sea alto (por ejemplo 0,7) y luego consideramos un numero "B" de forma "(1-A)/99", y juli elige un primer valor "A" y 99 valores "B" entre sus 100 números, Mica cuando forme las parejas inherentemente tendrá que multiplicar "A" por "B". Si llamamos "Y" al valor que Mica escribirá en el pizarrón, y planteamos la función Y=A*B , luego reemplazamos "B" por "(1-A)/99" tendremos la expresión "Y(A)", la cual podemos derivar e igualar a 0 para obtener el máximo de la función (corroboramos que es un máximo viendo que la segunda derivada es siempre negativa). Dicho máximo será "A = 0,5". Reemplazando en las primeras expresiones, "B = 0,00505 periódico en 505" y el máximo valor de "Y = 0,0025 periódico en 25". Si la estrategia de juego de Juli y de Mica es la óptima, este último valor dado de "Y" será el escrito en el pizarrón.
Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Jurado-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 269
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 11
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Re: Selectivo de IMO 2021 - Problema 3

Mensaje sin leer por Fedex »

Este problema lo rendí y no me salió :(
Spoiler: mostrar
Sin pérdida de generalidad $x_1 \leq x_2 \leq \cdots \leq x_{100}$.

Vamos a probar primero que lo mejor que puede hacer Mica es agrupar armando los productos $x_1x_{100}, \; x_2x_{99}, \; \cdots, \; x_{50}x_{51}$.

Lema 1: Sea $A$ un agrupamiento con dos productos $x_mx_M$ (con $m < M$) y $x_{m’}x_{M’}$ (con $m’ < M’$) tales que $m’ < m$ y $M’ < M$. Sea entonces $A’$ el agrupamiento que surge de cambiar esos dos productos por $x_mx_{M’}$ y $x_{m’}x_M$ entonces $\max_{x_ix_j}(A’) \leq \max_{x_ix_j}(A)$.
Spoiler: mostrar
Notar que $\max(x_mx_M,\; x_{m’}x_{M’}) = x_mx_M$ y además:
$$x_mx_{M’} \leq x_mx_M$$
$$x_{m’}x_M \leq x_mx_M$$
Luego $\max(x_mx_{M’}, \; x_{m’}x_M) \leq \max(x_mx_M, \; x_{m’}x_{M’})$. Como el resto de productos en $A$ y $A’$ son los mismos, se sigue lo enunciado.
Lema 2: Si un agrupamiento $A$ no tiene un par de productos como el del Lema 1 entonces $A = \lbrace
x_1x_{100}, \; x_2x_{99}, \; \cdots, \; x_{50}x_{51} \rbrace$.
Spoiler: mostrar
Notemos que si aparecen dos pares distintos $x_ix_{100}$ y $x_1x_j$ entonces $1 < i$ y $j < 100$ por lo que hay un par que verifica la hipótesis del Lema 1, luego sí debe aparecer $x_1x_{100}$.

Razonando inductivamente en el conjunto que queda de remover los extremos se sigue el lema.
Uniendo ambos lemas, se tiene que Mica minimiza el mayor producto agrupándolos como se propuso. Ahora vamos con Juli, para eso vamos a separar en dos casos.

Caso 1) $\max(x_ix_{101-i})= x_{50}x_{51}$:
Spoiler: mostrar
Notar que:
$$50x_{51} \leq x_{51} + \cdots + x_{100}$$
$$x_{50} \leq x_{51} \leq \frac{x_{51} + \cdots + x_{100}}{50}$$
Multiplicando ambas tenemos que:
$$x_{50}x_{51}\leq \frac{(x_{51} + \cdots + x_{100})^2}{50^2} \leq \frac{1}{2500}< \frac{1}{396}$$
Caso 2) $\max(x_ix_{101-i}) = x_jx_{101-j}$ donde $1 \leq j < 50$.
Spoiler: mostrar
Notar que:
$$jx_{101-j} \leq x_{101-j} + \cdots + x_{100}$$
$$(101-2j)x_j \leq x_j+ \cdots + x_{100-j} \leq x_1 + \cdots + x_{100-j}$$
Multiplicando ambas tenemos que:
$$x_jx_{101-j} \leq \frac{1}{j(101-2j)} \cdot (x_1 + \cdots + x_{100-j})(x_{101-j} + \cdots + x_{100}) \leq \frac{1}{j(101-2j)} \cdot (\frac{x_1 + \cdots + x_{100}}{2})^2 = \frac{1}{j(101-2j)} \cdot \frac{1}{4}$$
Donde para $1 \leq j < 50$ se da $j(101-2j) \geq 99$ ya que se reescribe como $0 \geq (j-1)(2j-99)$. Luego:
$$x_jx_{101-j} \leq \frac{1}{j(101-2j)} \cdot \frac{1}{4} \leq \frac{1}{396}$$
Así concluimos que una cota superior para el valor máximo que puede asegurarse Mica es $\frac{1}{396}$. Este en efecto puede ser alcanzado con $x_1 = \cdots = x_{99} = \frac{1}{198}$ y $x_{100} = \frac{1}{2}$ por lo que estamos. Luego este será el valor que aparece escrito si ambas juegan de manera óptima.
3  
Avatar de Usuario
Tiziano Brunelli

OFO - Medalla de Plata-OFO 2023 FOFO 13 años - Medalla-FOFO 13 años OFO - Mención-OFO 2024
Mensajes: 99
Registrado: Dom 21 Ago, 2022 1:24 pm
Medallas: 3
Nivel: Exolímpico
Ubicación: Al lado de Alta Córdoba, Córdoba capital, Córdoba

Re: Selectivo de IMO 2021 - Problema 3

Mensaje sin leer por Tiziano Brunelli »

Spoiler: mostrar
La solución comienza demostrando que Mica agrupará al mayor con el menor, el segundo mayor con el segundo menor y así:
$$x_1\geq x_2\geq ...\geq x_{100}$$
si mica elige la pareja $(x_j;x_i)$ con $j<51$ y $i< 101-j$ entonces $x_jx_i\geq x_jx_{101-j}$ por lo que para minimizar cualquier multiplicación que pueda llegar a ser la máxima siempre se elegirá las parejas del tipo $ (x_j;x_{101-j}) $
Luego, lo importante será maximizar la multiplicación entre $x_1$ y $x_{100}$, para ello hay que maximixar $x_1$ y $x_{100}$, $x_1<1$ es la restricción que tenemos con respecto a este término, y $x_{100}\leq \frac{1-x_1}{99}$. Por lo que la multiplicación nos queda $x_1\frac{1-x_1}{99}=\frac{x_1-x_1^2}{99}$. Para encontrar el máximo de esta función la derivaré e igualaré a 0, sabiendo que es un polinomio de grado $2$ y su coeficiente cuadrático es negativo, entonces sé que la raíz de la derivada es el máximo, solo quedará verificar que este máximo esté dentro en el rango $[\frac{1}{100};1)$ para que pueda ser una solución del problema.
Entonces si: $f(x)=\frac{x-x^2}{99}$
$$f'(x)=\frac{1-2x}{99}=0$$
$$x=\frac{1}{2}$$
lo que nos deja que $x_1=\frac{1}{2}$ y $x_{100}=\frac{1}{198}$ y el producto que se escribirá será $\frac{1}{396}$
1  
"cada vez que uses xor, piensa en mí, estaré usando vectores módulo 2"- un cordobés a otro. :D
Responder