Entrenamiento IMO 2014 - Problema 8 (C1)

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020
Mensajes: 960
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 7
Nivel: Exolímpico

Entrenamiento IMO 2014 - Problema 8 (C1)

Mensaje sin leer por Matías V5 » Mar 10 Jun, 2014 7:49 pm

Sea [math] un entero positivo. Hallar el menor entero [math] con la siguiente propiedad: Dados cualesquiera números reales [math] tales que [math] y [math] para [math], es posible partir a estos números en [math] grupos (algunos de los cuales pueden ser vacíos) tales que la suma de los números en cada grupo sea a lo sumo [math].
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore!

Numberblocks - https://www.youtube.com/watch?v=SoRiOoqao5Y

Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González
Mensajes: 400
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 8
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: Entrenamiento IMO 2014 - Problema 8 (C1)

Mensaje sin leer por Turko Arias » Mié 20 May, 2020 12:08 pm

Spoiler: mostrar
Tomando $a_1=a_2=...=a_{2n-1}=\frac{n}{2n-1}$ observamos que $k \geq 2n-1$.
Ahora bien, supongamos que tenemos reales $a_1, a_2,...,a_d$ cumpliendo las condiciones del enunciado, sin pérdida de generalidad $a_1 \leq a_2 \leq ... \leq a_d$. A cada elemento $a_i$ que sea mayor que $\frac{1}{2}$ lo mandamos a un conjunto nuevo. Supongamos que tenemos $m$ números cumpliendo eso. Claramente $m < \frac{n}{\frac{1}{2}}$ por lo que $m \leq 2n-1$ y no nos estaríamos excediendo de $2n-1$. Nos queda entonces $a_1+...+a_{d-m} \leq n-\frac{m}{2}$ y tenemos aún disponibles $2n-m-1$ conjuntos vacíos. Ahora bien, vamos tomando los $a_i$ desde el primero. Lo metemos en un conjunto vacío. A partir del segundo elemento aplicamos el siguiente algoritmo:
  • Si la suma total de los elementos del conjunto actual es mayor que $\frac{1}{2}$ añadimos el elemento a un nuevo conjunto vacío que pasa a ser nuestro conjunto actual.
  • Si la suma total de los elementos es a lo sumo $\frac{1}{2}$ añadimos el elemento al conjunto actual.
Notamos que como en cada conjunto, excepto tal vez en el último, la suma total de sus elementos es mayor que $\frac{1}{2}$, por lo que la cantidad máxima de conjuntos que vamos a utilizar es menor a $\frac{n-\frac{m}{2}}{\frac{1}{2}}=2n-m$, luego, dicha cantidad es a lo sumo $2n-m-1$ y ya habíamos utilizado $m$ al principio, por lo que $2n-1$ funciona, y por ende $k=2n-1$ $\blacksquare$
Muchas ideas en común con este problema, creo que si alguno había resuelto este problema antes de la prueba, iba con una buena parte del problema ya en mente.
Pd: si este problema es de combi, ese problema claramente no es de álgebra :roll:
Fundamentalista del Aire Acondicionado

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
Mensajes: 1243
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 6
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Entrenamiento IMO 2014 - Problema 8 (C1)

Mensaje sin leer por Gianni De Rico » Mié 20 May, 2020 12:28 pm

Y también tiene un aire a este, que aparentemente era de Teoría de Números...
Queda Elegantemente Demostrado

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
Mensajes: 940
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 12
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Entrenamiento IMO 2014 - Problema 8 (C1)

Mensaje sin leer por Fran5 » Mié 20 May, 2020 12:40 pm

Turko Arias escribió:
Mié 20 May, 2020 12:08 pm
creo que si alguno había resuelto este problema antes de la prueba, iba con una buena parte del problema ya en mente.

Hay que estar registrado para ver las imágenes
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"

Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González
Mensajes: 400
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 8
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: Entrenamiento IMO 2014 - Problema 8 (C1)

Mensaje sin leer por Turko Arias » Mié 20 May, 2020 1:02 pm

Gianni De Rico escribió:
Mié 20 May, 2020 12:28 pm
Y también tiene un aire a este, que aparentemente era de Teoría de Números...
Si y no... Estéticamente son parecidos, pero ese problema habla de un tipo de fracciones en particular, y acá hablamos de reales, por lo que las maneras de encararlos son distintos. En el problema que cité no hablo de un parecido estético, sino que la esencia de las soluciones es la misma. Igual ese problema no es ni un poco TN, no se que onda, todos dicen lo mismo
Fundamentalista del Aire Acondicionado

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
Mensajes: 1243
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 6
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Entrenamiento IMO 2014 - Problema 8 (C1)

Mensaje sin leer por Gianni De Rico » Mié 20 May, 2020 1:14 pm

Claro, yo me refería al parecido estético nomás. Creo que nadie sabe muy bien por qué ese problema es de TN, pero era el N3 de la SL, así que algún approach por ese lado debe haber...
Queda Elegantemente Demostrado

Responder