FOFO 9 años Problema 8

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

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Bronce-OFO 2016 OFO - Jurado-OFO 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 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 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
Mensajes: 157
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

FOFO 9 años Problema 8

Mensaje sin leer por AgusBarreto »

Sea $A$ un conjunto de $n$ reales positivos. Sea $S$ el conjunto de todas las sumas de algunos de los números del conjunto. Demostrar que se puede particionar a $S$ en $n$ subconjuntos tales que para cada subconjunto la razón entre el más grande y el más chico no supera $2$.
Avatar de Usuario
AgusBarreto

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Bronce-OFO 2016 OFO - Jurado-OFO 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 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 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
Mensajes: 157
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

Re: FOFO 9 años Problema 8

Mensaje sin leer por AgusBarreto »

Aquí vamos a publicar la solución oficial
HelcsnewsXD

FOFO 9 años - Mención Especial-FOFO 9 años COFFEE - Mención-COFFEE Carolina González COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Mención-FOFO 10 años
Mensajes: 59
Registrado: Jue 13 Sep, 2018 8:59 am
Medallas: 4

Re: FOFO 9 años Problema 8

Mensaje sin leer por HelcsnewsXD »

Lo hice con inducción, puesto que con 1 cumple, demostré que si consideramos que un conjunto $S_n$ cumple, el $S_{n+1}$ también. Por esto, se cumple para todos los n y la partición siempre será posible.
Spoiler: mostrar
Este problema lo demostraré con inducción, considerando los casos donde $A$ tiene $1$, $n$ y $n+1$ elementos respectivamente. La demostración de que se cumple siempre dentro de un conjunto $A$, nace de la demostración que hacemos a continuación, por lo que es innecesaria (básicamente, la demostración es considerar un conjunto $A$ con todos los números excepto con el que cambiás o sacás, por esto, es como si agregaras un conjunto, el cual ya estaba de antes, y se hace el proceso descripto a continuación). Por esto, tenemos que:
1) Para $n=1 \rightarrow S={s_0} / \frac{s_0}{s_0} \leq 2$
2) Para $n \rightarrow$ Supongamos que se cumple. Para cada conjunto, llamaremos $M_s$ al máximo y $m_s$ al mínimo. Además, consideremos que los números reales usados son $a_1\leq a_2\leq … \leq a_n$ sin pérdida de generalidad
3) Veamos qué pasa con $n+1 \rightarrow$ se agrega $a_{n+1}$, $n$ sumas y un conjunto $S_{n+1}$. Bien sabemos que si alguna de estas sumas se encuentra entre $M_{s_x}$ y $m_{s_x}$ inclusive, puede agregarse a ese conjunto sin modificar la razón existente en él. Por esto, el caso donde $a_{n+1}$ no es extremo, es sencillo de resolver.
Ahora, si es extremo, tenemos dos casos: es el máximo o es el mínimo (para los dos, la demostración es semejante). Empecemos con $a_{n+1}$ máximo. Acá, dentro de las $n$ sumas tenemos un mínimo y un máximo internos, los cuales son $a_1+a_{n+1}$ y $a_n+a_{n+1}$, respectivamente. Si alguna de las sumas llega a estar entre un $M_{s_x}$ y un $m_{s_x}$, inclusives, ya vimos lo que sucede (es indiferente considerarlo o no, ya que el resultado será el mismo). Por esto, también consideremos $a_{n-1}+a_n < a_1 + a_{n+1}$. Una posibilidad es agregar las n sumas en $S_{n+1}$ pero ahora veamos qué sucede si esto no llegara a ser posible $\Rightarrow \frac{a_n+a_{n+1}}{a_1+a_{n+1}} > 2 \Rightarrow a_n+a_{n+1} > 2a_1+2a_{n+1} \Rightarrow a_n – 2a_1 > a_{n+1}$, lo cual es imposible ya que $a_{n+1}$ es máximo. Por lo tanto, se llega a un absurdo.
Con $a_{n+1}$ como mínimo, se hacen las mismas consideraciones: Dentro de estas sumas, el mínimo y el máximo son, respectivamente, $a_1+a_{n+1}$ y $a_n+a_{n+1}$. Si alguna de las sumas llega a estar entre un $M_{s_x}$ y un $m_{s_x}$, inclusives, ya vimos lo que pasaba. Por esto, también consideremos que $a_1+a_2 > a_{n+1}+a_n$. Una posibilidad es agregar las n sumas en $S_{n+1}$, pero ahora veamos qué sucede si esto no llegara a ser posible $\Rightarrow \frac{a_n+a_{n+1}}{a_1+a_{n+1}} > 2 \Rightarrow a_n+a_{n+1} > 2a_1+2a_{n+1} \Rightarrow \frac{a_n-a_{n+1}}{2} > a_1$. Y, además, $a_1+a_2 > a_{n+1}+a_n \Rightarrow a_1 > a_{n+1} + a_n – a_2$. Por esto, tenemos que: $a_{n+1}+a_n-a_2 < \frac{a_n-a_{n+1}}{2} \Rightarrow 2a_{n+1} + 2a_n -2a_2 < a_n-a_{n+1} \Rightarrow 3a_{n+1}+a_n-2a_2 < 0 \Rightarrow$ Absurdo ya que todos son $\mathbb{R^{+}}$ y $a_2\leq a_n \Rightarrow$ Se completa la inducción, demostrándose esta posibilidad de partición
Na, clave la solución :lol:
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 FOFO 10 años - Copa-FOFO 10 años OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años
OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 411
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 16
Nivel: 3

Re: FOFO 9 años Problema 8

Mensaje sin leer por BrunZo »

HelcsnewsXD escribió: Mar 15 Oct, 2019 10:17 am Lo hice con inducción, puesto que con 1 cumple, demostré que si consideramos que un conjunto $S_n$ cumple, el $S_{n+1}$ también. Por esto, se cumple para todos los n y la partición siempre será posible.
Spoiler: mostrar
Este problema lo demostraré con inducción, considerando los casos donde $A$ tiene $1$, $n$ y $n+1$ elementos respectivamente. La demostración de que se cumple siempre dentro de un conjunto $A$, nace de la demostración que hacemos a continuación, por lo que es innecesaria (básicamente, la demostración es considerar un conjunto $A$ con todos los números excepto con el que cambiás o sacás, por esto, es como si agregaras un conjunto, el cual ya estaba de antes, y se hace el proceso descripto a continuación). Por esto, tenemos que:
1) Para $n=1 \rightarrow S={s_0} / \frac{s_0}{s_0} \leq 2$
2) Para $n \rightarrow$ Supongamos que se cumple. Para cada conjunto, llamaremos $M_s$ al máximo y $m_s$ al mínimo. Además, consideremos que los números reales usados son $a_1\leq a_2\leq … \leq a_n$ sin pérdida de generalidad
3) Veamos qué pasa con $n+1 \rightarrow$ se agrega $a_{n+1}$, $n$ sumas y un conjunto $S_{n+1}$. Bien sabemos que si alguna de estas sumas se encuentra entre $M_{s_x}$ y $m_{s_x}$ inclusive, puede agregarse a ese conjunto sin modificar la razón existente en él. Por esto, el caso donde $a_{n+1}$ no es extremo, es sencillo de resolver.
Ahora, si es extremo, tenemos dos casos: es el máximo o es el mínimo (para los dos, la demostración es semejante). Empecemos con $a_{n+1}$ máximo. Acá, dentro de las $n$ sumas tenemos un mínimo y un máximo internos, los cuales son $a_1+a_{n+1}$ y $a_n+a_{n+1}$, respectivamente. Si alguna de las sumas llega a estar entre un $M_{s_x}$ y un $m_{s_x}$, inclusives, ya vimos lo que sucede (es indiferente considerarlo o no, ya que el resultado será el mismo). Por esto, también consideremos $a_{n-1}+a_n < a_1 + a_{n+1}$. Una posibilidad es agregar las n sumas en $S_{n+1}$ pero ahora veamos qué sucede si esto no llegara a ser posible $\Rightarrow \frac{a_n+a_{n+1}}{a_1+a_{n+1}} > 2 \Rightarrow a_n+a_{n+1} > 2a_1+2a_{n+1} \Rightarrow a_n – 2a_1 > a_{n+1}$, lo cual es imposible ya que $a_{n+1}$ es máximo. Por lo tanto, se llega a un absurdo.
Con $a_{n+1}$ como mínimo, se hacen las mismas consideraciones: Dentro de estas sumas, el mínimo y el máximo son, respectivamente, $a_1+a_{n+1}$ y $a_n+a_{n+1}$. Si alguna de las sumas llega a estar entre un $M_{s_x}$ y un $m_{s_x}$, inclusives, ya vimos lo que pasaba. Por esto, también consideremos que $a_1+a_2 > a_{n+1}+a_n$. Una posibilidad es agregar las n sumas en $S_{n+1}$, pero ahora veamos qué sucede si esto no llegara a ser posible $\Rightarrow \frac{a_n+a_{n+1}}{a_1+a_{n+1}} > 2 \Rightarrow a_n+a_{n+1} > 2a_1+2a_{n+1} \Rightarrow \frac{a_n-a_{n+1}}{2} > a_1$. Y, además, $a_1+a_2 > a_{n+1}+a_n \Rightarrow a_1 > a_{n+1} + a_n – a_2$. Por esto, tenemos que: $a_{n+1}+a_n-a_2 < \frac{a_n-a_{n+1}}{2} \Rightarrow 2a_{n+1} + 2a_n -2a_2 < a_n-a_{n+1} \Rightarrow 3a_{n+1}+a_n-2a_2 < 0 \Rightarrow$ Absurdo ya que todos son $\mathbb{R^{+}}$ y $a_2\leq a_n \Rightarrow$ Se completa la inducción, demostrándose esta posibilidad de partición
Spoiler: mostrar
Creo que acá tenés otro problema: Vos repetís varias veces a través de la solución que una suma nueva $s$ o bien entra algún $[m_{s_x},M_{s_x}]$, o bien es más grande que todos los números viejos, es decir, $s>a_n+a_{n+1}$. Pero esto no es necesariamente cierto, y acá radica la dificultad del problema: Puede ser que algún número te caiga en los "huecos" entre los conjuntos, sería algo así como caer entre $M_{s_x}$ y $m_{s_{x+1}}$, por lo cual no entra en ningún conjunto antes formado, lo cual invalida gran parte del argumento.
Por otro lado, como dato, si estás haciendo este tipo de inducción se puede asumir de una que $a_{n+1}$ es el mayor, el menor o lo que quieras, de la siguiente forma: Tenés un conjunto $A$ de $n+1$ elementos, y te fijás en el más grande, digamos $a_{n+1}$, y se lo sacás. Entonces, tenés un conjunto $A'$ de $n$ elementos (que por hipótesis inductiva cumple) y su mayor elemento $a_{n+1}$, y estás en la misma situación, pero con $a_{n+1}$ siendo el mayor. De todos modos, yo no encuentro ningún camino libre por este lado...
Avatar de Usuario
Joacoini

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-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 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: 460
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 16
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Re: FOFO 9 años Problema 8

Mensaje sin leer por Joacoini »

HelcsnewsXD escribió: Mar 15 Oct, 2019 10:17 am Lo hice con inducción, puesto que con 1 cumple, demostré que si consideramos que un conjunto $S_n$ cumple, el $S_{n+1}$ también. Por esto, se cumple para todos los n y la partición siempre será posible.
Spoiler: mostrar
Este problema lo demostraré con inducción, considerando los casos donde $A$ tiene $1$, $n$ y $n+1$ elementos respectivamente. La demostración de que se cumple siempre dentro de un conjunto $A$, nace de la demostración que hacemos a continuación, por lo que es innecesaria (básicamente, la demostración es considerar un conjunto $A$ con todos los números excepto con el que cambiás o sacás, por esto, es como si agregaras un conjunto, el cual ya estaba de antes, y se hace el proceso descripto a continuación). Por esto, tenemos que:
1) Para $n=1 \rightarrow S={s_0} / \frac{s_0}{s_0} \leq 2$
2) Para $n \rightarrow$ Supongamos que se cumple. Para cada conjunto, llamaremos $M_s$ al máximo y $m_s$ al mínimo. Además, consideremos que los números reales usados son $a_1\leq a_2\leq … \leq a_n$ sin pérdida de generalidad
3) Veamos qué pasa con $n+1 \rightarrow$ se agrega $a_{n+1}$, $n$ sumas y un conjunto $S_{n+1}$. Bien sabemos que si alguna de estas sumas se encuentra entre $M_{s_x}$ y $m_{s_x}$ inclusive, puede agregarse a ese conjunto sin modificar la razón existente en él. Por esto, el caso donde $a_{n+1}$ no es extremo, es sencillo de resolver.
Ahora, si es extremo, tenemos dos casos: es el máximo o es el mínimo (para los dos, la demostración es semejante). Empecemos con $a_{n+1}$ máximo. Acá, dentro de las $n$ sumas tenemos un mínimo y un máximo internos, los cuales son $a_1+a_{n+1}$ y $a_n+a_{n+1}$, respectivamente. Si alguna de las sumas llega a estar entre un $M_{s_x}$ y un $m_{s_x}$, inclusives, ya vimos lo que sucede (es indiferente considerarlo o no, ya que el resultado será el mismo). Por esto, también consideremos $a_{n-1}+a_n < a_1 + a_{n+1}$. Una posibilidad es agregar las n sumas en $S_{n+1}$ pero ahora veamos qué sucede si esto no llegara a ser posible $\Rightarrow \frac{a_n+a_{n+1}}{a_1+a_{n+1}} > 2 \Rightarrow a_n+a_{n+1} > 2a_1+2a_{n+1} \Rightarrow a_n – 2a_1 > a_{n+1}$, lo cual es imposible ya que $a_{n+1}$ es máximo. Por lo tanto, se llega a un absurdo.
Con $a_{n+1}$ como mínimo, se hacen las mismas consideraciones: Dentro de estas sumas, el mínimo y el máximo son, respectivamente, $a_1+a_{n+1}$ y $a_n+a_{n+1}$. Si alguna de las sumas llega a estar entre un $M_{s_x}$ y un $m_{s_x}$, inclusives, ya vimos lo que pasaba. Por esto, también consideremos que $a_1+a_2 > a_{n+1}+a_n$. Una posibilidad es agregar las n sumas en $S_{n+1}$, pero ahora veamos qué sucede si esto no llegara a ser posible $\Rightarrow \frac{a_n+a_{n+1}}{a_1+a_{n+1}} > 2 \Rightarrow a_n+a_{n+1} > 2a_1+2a_{n+1} \Rightarrow \frac{a_n-a_{n+1}}{2} > a_1$. Y, además, $a_1+a_2 > a_{n+1}+a_n \Rightarrow a_1 > a_{n+1} + a_n – a_2$. Por esto, tenemos que: $a_{n+1}+a_n-a_2 < \frac{a_n-a_{n+1}}{2} \Rightarrow 2a_{n+1} + 2a_n -2a_2 < a_n-a_{n+1} \Rightarrow 3a_{n+1}+a_n-2a_2 < 0 \Rightarrow$ Absurdo ya que todos son $\mathbb{R^{+}}$ y $a_2\leq a_n \Rightarrow$ Se completa la inducción, demostrándose esta posibilidad de partición
Otro problema que tenés es que solo consideras las sumas de dos elementos, pero el enunciado dice algunos elementos, no solo dos.
NO HAY ANÁLISIS.
Responder