IMO 2020 Problema 3

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

OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 186
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 4
Nivel: 3

IMO 2020 Problema 3

Mensaje sin leer por Sandy »

Hay $4n$ piedritas de pesos $1,2,3,...,4n$. Cada piedrita se colorea de uno de $n$ colores de manera que hay cuatro piedritas de cada color. Demuestre que podemos colocar las piedritas en dos montones de tal forma que las siguientes dos condiciones se satisfacen:
  • Los pesos totales de ambos montones son iguales.
  • Cada montón contiene dos piedritas de cada color.
$u=tan\left(\frac{x}{2}\right)$
$\frac{2}{1+u^2}du=dx$

Avatar de Usuario
Nicolas Valen
Mensajes: 15
Registrado: Vie 31 Jul, 2020 2:56 am
Nivel: 2

Re: IMO 2020 Problema 3

Mensaje sin leer por Nicolas Valen »

Spoiler: mostrar
Primero veamos si ambas pueden tener el mismo peso: por suma de Gauss el peso total es: $\frac{4n(4n+1)}{2} = 2n(4n+1) = 8n^2+2n$.
Como queremos dividirlo en partes iguales tenemos: $\frac {8n^2+2n}{2} = 4n^2 + n \Rightarrow $ se satisface la primera condición.
Como sabemos que las $4n$ piedritas se conforman en 4 periodos de n piedritas: $P_1, P_2, P_3, P_4$, vamos a calcular el peso en cada uno de ellos que contienen las n piedritas de distinto color:
Peso en $P_1 = \frac{n(n+1)}{2} = \frac{n^2}{2} + \frac {n}{2}$
Peso en $P_2 = \frac{2n(2n+1)}{2} - (\frac{n^2}{2} + \frac {n}{2}) = \frac{3n^2}{2} + \frac{n}{2}$
Peso en $P_3 = \frac{3n(3n+1)}{2} - (\frac{n^2}{2} + \frac {n}{2}) - (\frac{3n^2}{2} + \frac{n}{2}) = \frac{5n^2}{2} + \frac{n}{2}$
Peso en $P_4 = 8n^2 + 2n - (\frac{n^2}{2} + \frac {n}{2}) - (\frac{3n^2}{2} + \frac{n}{2}) - (\frac{5n^2}{2} + \frac{n}{2}) = \frac{7n^2}{2} + \frac{n}{2}$
Ahora, notemos que los 4 periodos tienen la misma cantidad de piedrias de $n$ colores distintos, entonces veamos los pesos de los siguientes montones:
$P_1 + P_4 = \frac{n^2}{2} + \frac {n}{2} + \frac{7n^2}{2} + \frac{n}{2} = 4n^2 + 2n$
$P_2 + P_3 = \frac{3n^2}{2} + \frac{n}{2} + \frac{5n^2}{2} + \frac{n}{2} = 4n^2 + 2n$
Cada monton formado por la suma de $P_1 + P_4$ y $P_2 + P_3$ tiene 2 piedritas de cada color y en particular tienen el mismo peso, satisfaciendo ambas condiciones.
$\int$$\sqrt{tg(\psi)}$ $d\psi = $$ \frac{2\cdot[arctg(\sqrt{2tg(\psi)} + 1) + arctg(\sqrt{2tg(\psi)} - 1)] - [ln(tg(\psi) + \sqrt{2tg(\psi)} + 1) + ln(tg(\psi) - \sqrt{2tg(\psi)} - 1)]}{2^{\frac{3}{2}}}$

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 OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 985
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 13
Nivel: Exolímpico
Ubicación: Santa Fe

Re: IMO 2020 Problema 3

Mensaje sin leer por Fran5 »

Nicolas Valen escribió:
Mar 22 Sep, 2020 7:43 pm
.

Ahora, notemos que los 4 periodos tienen la misma cantidad de piedrias de $n$ colores distintos,
Cómo sería eso? :geek:
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"

BrunZo

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020
Mensajes: 288
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 7
Nivel: 1

Re: IMO 2020 Problema 3

Mensaje sin leer por BrunZo »

Nicolas Valen escribió:
Mar 22 Sep, 2020 7:43 pm
Spoiler: mostrar
Ahora, notemos que los 4 periodos tienen la misma cantidad de piedrias de $n$ colores distintos,
Spoiler: mostrar
¿Por qué?

Si no te estoy malinterpretando, tu argumento es:
Tomo las primeras n y las últimas n. Su suma es tanto.
Tomo las 2n del medio. Su suma es tanto.
Ambas sumas son iguales, así que se cumple la primera condición.
Pero no veo como podés asegurarte que hay dos piedras de cada color. Por ejemplo, si los colores son 1, 1, 1, 1, 2, 2, 2, 2, ..., n, n, n, n; entonces tu primer montón tendría 4 piedras del color 1.

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 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
Mensajes: 1476
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 8
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: IMO 2020 Problema 3

Mensaje sin leer por Gianni De Rico »

Nicolas Valen escribió:
Mar 22 Sep, 2020 7:43 pm
Spoiler: mostrar
Cada monton formado por la suma de $P_1 + P_4$ y $P_2 + P_3$ tiene 2 piedritas de cada color y en particular tienen el mismo peso, satisfaciendo ambas condiciones.
Spoiler: mostrar
¿Qué pasa si las piedritas $1,2,3,4$ tienen el mismo color?

Las piedritas ya están pintadas, vos no podés elegir el color que tienen.
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850

Avatar de Usuario
Nicolas Valen
Mensajes: 15
Registrado: Vie 31 Jul, 2020 2:56 am
Nivel: 2

Re: IMO 2020 Problema 3

Mensaje sin leer por Nicolas Valen »

Bien, asumí cualquiera porque mi interpretación del enunciado fue: "se pintan de uno de los n colores cada una de las piedritas" a las n te quedas sin colores y volves a arrancar porque queres que se pinte cada piedrita de uno de los n, pero tenes 4n. En lo primero que pense es que era directo, un error tonto.
$\int$$\sqrt{tg(\psi)}$ $d\psi = $$ \frac{2\cdot[arctg(\sqrt{2tg(\psi)} + 1) + arctg(\sqrt{2tg(\psi)} - 1)] - [ln(tg(\psi) + \sqrt{2tg(\psi)} + 1) + ln(tg(\psi) - \sqrt{2tg(\psi)} - 1)]}{2^{\frac{3}{2}}}$

BrunZo

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020
Mensajes: 288
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 7
Nivel: 1

Re: IMO 2020 Problema 3

Mensaje sin leer por BrunZo »

Spoiler: mostrar

Yo creo que la magia del problema está en lo siguiente: Yo digo que una pareja es un par de enteros de la forma $(i, 4n+1-i)$ con $1\leq i\leq 2n$. Notemos que la suma de los elementos de toda pareja es la misma, $4n+1$, entonces, si por algún motivo extraño, pudiésemos partir a los números en dos montones compuestos exclusivamente de parejas (en particular, cada montón tendría exactamente $n$ parejas), sería un golazo, porque la suma de pesos en cada montón sería exactamente $n(4n+1)=4n^2+n$, la mitad del peso total.

Ahora, no necesariamente se puede hacer esto... ¿o sí? Bueno, en principio uno estaría tentado a pensar que, en efecto, estamos pidiendo algo muy particular, y que en general podría no ser cierto. Pero, aún así, nunca viene mal pensar, aunque sea un ratito, ideas como esta, que son las que al fin y al cabo resuelven los problemas (siempre teniendo en cuenta, claro está, que no hay que dedicarle tiempo de más a las ideas que no parecen llevar a buen puerto, puesto que éstas son las que al fin y al cabo nos hacen perder el tiempo).

Si pensamos casitos chiquitos, como $n=2,3$, estos parecen avalar nuestra teoría, pues siempre terminamos viendo que existe una partición de esta pinta... Ahora, ¿será cierto para todo $n$? Veremos...

Imaginemonos que reordenamos las piedrecitas es un rectángulo: En cada columna ponemos las cuatro piedras del mismo color, y alineamos horizontalmente los colores. Entonces, imaginémonos que conectamos todas las parejas de piedras como las definimos al comienzo. Notar que las parejas pueden o bien tener ambas piedras de un mismo color, o bien usar piedras de distintos colores. Un hecho divertido que puede notarse a partir de esto es lo siguiente:

Imaginémonos que agarramos la primera piedrecita en la primera columna, y nos fijamos en su pareja. Ahora, o bien la pareja está en la misma columna, o bien no; en cualquier caso, imaginémonos que nos "movemos" a la columna a donde está esta pareja (si están en el mismo color, no nos movemos). Pero notemos entonces, que en la nueva columna en la que estamos tiene más piedras, por lo que podremos tomar alguna de éstas y repetir el proceso: Nos fijamos en su pareja y nos movemos a la columna correspondiente, y así seguimos.

Veamos lo siguiente: Si consideramos el "camino" que realizamos, podemos ver varias cosas:
  • Si nos fijamos en una columna distinta de la primera, cada vez que "entramos" en esta columna, el siguiente paso nos hace "salir" de la columna, usando una piedra distinta (quizás esta "salida" nos hace volver a "entrar" en la misma columna, si hay una pareja contenida, pero al fin y al cabo esto sigue valiendo). De este modo, podemos ver, dentro de cada columna, exactamente dos pares de piedrecitas "entrada-salida" (entramos por una piedra y salimos por la otra).
  • Entonces, podemos ver que el "camino" siempre puede seguir una vez "entra" en una columna distinta de la primera, puesto que siempre tendrá alguna piedra disponible para "salir", lo que nos indica que la única forma de que el camino termine es que vuelva a la columna inicial por segunda vez (en esta columna, la primera piedra es una "salida", así que la próxima vez en "entrar" se formará un par "entrada-salida", y luego, la segunda vez que se "entre", no quedarán piedras disponibles). De hecho, podemos imaginarnos que las piedras inicial y final forman otro par "entrada-salida" (la última es una entrada y la primera una salida), de modo que se forma una especie de "ciclo", puesto que podemos volver al inicio y seguir recorriendo los colores como antes.
  • Como corolario de la existencia de estos pares "entrada-salida", cuando tengamos el "ciclo" completo, se ve que este ciclo usa una cantidad par de piedras en cada color (puesto que en cada color hay, 0, 1 o 2 pares "entrada-salida").
Pero supongamos que hay algún color en el que tenemos sólo un par "entrada-salida". Por la naturaleza "cíclica" de nuestro recorrido, yo digo que podemos empezar nuestro recorrido es la salida de este par y recorrer el "camino" en el mismo sentido para llegar de vuelta la entrada. Pero si esto ocurre, notemos que el "camino" todavía no termino: ¡Tenemos piedras en nuestro nuevo color inicial para continuar el camino! De hecho, si lo continuamos como describimos antes, el resultado sería un camino de mayor longitud, que ahora usa las 4 piedras de nuestro nuevo color inicial (ya que cerrando el ciclo al volver a entrar en este camino, habrá dos pares "entrada-salida"). Pero como esto puede hacerse siempre que haya un color del que usamos sólo dos piedras, y sabemos que al hacer esto algo "avanza" (la longitud del camino crece) podremos estar seguros que al aplicar y seguir aplicando esto, nunca volveremos a un estado anterior, y por ende habrá un punto en el que ya no podremos aplicarlo (la cantidad de piedras es finita). En este punto, todos los colores usan o bien 4 piedras o bien ninguna.

Ahora, separemos todos los colores en los que usamos 4 piedras. A éstos los vamos a agrupar en un "grupo de colores". Sabemos que este "grupo de colores" cumple la propiedad de que existe un "ciclo" que pasa por todas las piedras del grupo (recordemos, aunque sea para no olvidarnos, que estamos imaginando cada paso como movernos por las parejas). Por otro lado, quedan algunos colores en los cuales todavía no usamos ninguna piedra. Pero en ese caso, lo que podemos hacer es exactamente lo mismo que hicimos hasta ahora: Tomar una piedra inicial, armar un ciclo, ir corrigiéndolo para usar 4 piedras de cada color y separar un nuevo "grupo de colores" y repetir. Pero como la cantidad de colores es finita, es claro que en algún momento este proceso terminará, y cuando termine tendremos algunos "grupos de colores" con un ciclo cada uno.

Bueno.

No nos olvidemos de nuestro objetivo original: Nosotros queremos tomar dos piedras de cada color y lograr que el montoncito resultante tenga $n$ parejas... ¿Y qué formas tenemos de tomar dos piedras de cada color? Una forma sencilla es volver a la idea de los pares "entrada-salida": Si tomamos una piedra de cada par, claramente tendremos dos piedras de cada color... ¿Y como interpretamos lo de las parejas? Bueno, fijémonos que si, viendo un par "entrada-salida", tomamos sólo las dos piedras de la pareja que entra y no la que sale, entonces estaríamos tomando sólo una piedra del par "entrada-salida", y también las dos piedras de una pareja. Ahora, si nos fijamos la otra piedra de la pareja que tomamos y vemos su par "entrada-salida", entonces nos gustaría que la otra piedra de este par no sea elegida, así que no podemos elegir la pareja de esta otra piedra. Similarmente, si vemos la otra piedra de esta última pareja no elegida y vemos su par "entrada-salida" nos gustaría elegir la pareja de la otra piedra de ese par, ya que la que estamos viendo no fue elegida, y así siguiendo. En definitiva, veamos que si elegimos, del ciclo, una pareja sí, una no, una sí, una no y así siguiendo, es claro que en cada par "entrada-salida" estaremos elegiendo sólo una piedra, de modo que en definitiva estaremos eligiendo dos piedras de cada color. Por último, cabe notar que si el grupo en el que empezamos tiene $k$ colores, entonces habría $2k$ parejas en el ciclo, de modo que efectivamente se puede elegir una pareja sí y una no alrededor de todo el ciclo, de modo que terminamos partiendo este grupo de colores en dos montones formados de parejas.

Si hacemos lo mismo con el resto de grupos y juntamos todos los montones, terminaremos obteniendo una parición como la deseada.
O
Spoiler: mostrar

Si quieren una solución en difícil:

Si una pareja es algo de la forma $(i, 4n+1-i)$ con $1\leq i\leq 2n$, consideramos el (multi)grafo con un vértice por cada color, con colores A y B conectados por una arista por cada piedra A que forma una pareja con una piedra B (pueden haber bucles y aristas repetidas). Es claro que el grado de cada vértice es $4$ (par), luego cada componente conexa tiene un circuito Euleriano con longitud par, luego podemos colorear aristas de blanco y negro en cada ciclo de cada componente y tomar todas las aristas negras, que forman una partición válida.

De todos modos, por favor leer la otra solución.
2  

Responder