FOFO 9 años Problema 8

Avatar de Usuario
AgusBarreto

OFO - Medalla de Bronce OFO - Jurado FOFO 7 años - Jurado FOFO 8 años - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 116
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 8
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

FOFO 9 años Problema 8

Mensaje sin leer por AgusBarreto » Jue 10 Oct, 2019 11:34 pm

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 - Jurado FOFO 7 años - Jurado FOFO 8 años - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 116
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 8
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

Re: FOFO 9 años Problema 8

Mensaje sin leer por AgusBarreto » Dom 13 Oct, 2019 8:33 pm

Aquí vamos a publicar la solución oficial

HelcsnewsXD
Mensajes: 23
Registrado: Jue 13 Sep, 2018 8:59 am
Nivel: 2

Re: FOFO 9 años Problema 8

Mensaje sin leer por HelcsnewsXD » 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

BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata FOFO Pascua 2019 - Medalla
Mensajes: 178
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 4
Nivel: 1

Re: FOFO 9 años Problema 8

Mensaje sin leer por BrunZo » Mar 15 Oct, 2019 11:58 am

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 FOFO 8 años - Medalla Especial OFO - Medalla de Oro FOFO Pascua 2019 - Medalla
Mensajes: 206
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 4
Nivel: 2
Ubicación: Ciudad Gotica

Re: FOFO 9 años Problema 8

Mensaje sin leer por Joacoini » Mar 15 Oct, 2019 12:08 pm

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