Selectivo de Cono 2018 P2

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

OFO - Medalla de Bronce-OFO 2016 OFO - Medalla de Bronce-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 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 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 206
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 8
Nivel: 3

Selectivo de Cono 2018 P2

Mensaje sin leer por Matías »

Hallar todos los números enteros positivos $n$ con la siguiente propiedad: los números del $1$ al $n$, $1,2,\ldots ,n$ se pueden dividir en tres subconjuntos no vacíos con diferentes cantidades de números tales que para toda pareja de subconjuntos, el conjunto con menos elementos tenga suma más grande que el subconjunto con más elementos.
Santito
Mensajes: 8
Registrado: Vie 17 Jul, 2015 9:04 pm
Nivel: Exolímpico

Re: Selectivo de Cono 2018 P2

Mensaje sin leer por Santito »

Spoiler: mostrar
Como los tres subconjuntos no pueden ser vacíos y deben tener distintas cantidades de números, $n \geq 6$ (ya que las cantidades mínimas de números en los subconjuntos son 1, 2 y 3).

Llamaremos $S_{1}$ al conjunto con menor cantidad de números y mayor suma, $S_{3}$ al conjunto con mayor cantidad de números y menor suma, y $S_{2}$ al conjunto restante.

Si $n = 6$, la única distribución posible de cantidades de números en los subconjuntos es 1 en $S_{1}$, 2 en $S_{2}$ y 3 en $S_{3}$. Es fácil ver que la mayor suma posible en $S_{1}$ es 6, por lo que las sumas en $S_{2}$ y $S_{3}$ deberían ser menores que 6. En $S_{2}$ y $S_{3}$ hay que incluír los números del 1 al 5, pero $1+2+3+4+5=15$. Es decir: $S_{2}<6$, $S_{3}<6$ y $S_{2} + S_{3} = 15$, absurdo.

Si $n = 7$, la única distribución posible de cantidades de números en los subconjuntos es 1 en $S_{1}$, 2 en $S_{2}$ y 4 en $S_{3}$. Es fácil ver que la mayor suma posible en $S_{1}$ es 7, por lo que las sumas en $S_{2}$ y $S_{3}$ deberían ser menores que 7. En $S_{2}$ y $S_{3}$ hay que incluír los números del 1 al 6, pero $1+2+3+4+5+6=21$. Es decir: $S_{2}<7$, $S_{3}<7$ y $S_{2} + S_{3} = 21$, absurdo.

Si $n = 8$, hay dos posibles distribuciones de cantidades de números en los subconjuntos: 1 en $S_{1}$, 2 en $S_{2}$ y 5 en $S_{3}$ o 1 en $S_{1}$, 3 en $S_{2}$ y 4 en $S_{3}$. Es fácil ver que la mayor suma posible en $S_{1}$ es 8, por lo que las sumas en $S_{2}$ y $S_{3}$ deberían ser menores que 8. En $S_{2}$ y $S_{3}$ hay que incluír los números del 1 al 7, pero $1+2+3+4+5+6+7=28$. Es decir: $S_{2}<8$, $S_{3}<8$ y $S_{2} + S_{3} = 28$, absurdo.

Si $n = 9$, una distribución que satisface las condiciones del problema es: $S_{1}$ = {8, 9} (suma 17), $S_{2}$ = {3, 6, 7} (suma 16) y $S_{3}$ = {1, 2, 4, 5} (suma 12).

Basándonos en esta distribución podemos afirmar que siempre que $n \equiv 0 \mod{3}$ habrá una distribución que satisfaga las condiciones. Por ejemplo, si $n = 12$, bastará con agregar el 12 a $S_{1}$, el 11 a $S_{2}$ y el 10 a $S_{3}$. Es decir, siempre que se agreguen tres números consecutivos, el mayor irá a $S_{1}$, el del medio a $S_{2}$ y el menor a $S_{3}$. De esta manera no se alterarán las relaciones de cantidades (ya que siempre se le suma un número a cada conjunto) ni las de sumas (ya que al conjunto de mayor suma se le agregará el número más grande de los tres y al de menor suma se le agregará el número más pequeño de los tres).

Si $n = 10$, la única distribución posible de cantidades de números en los subconjuntos tales que $S_{1}$ tenga más de un número: 2 en $S_{1}$, 3 en $S_{2}$ y 5 en $S_{3}$. Es fácil ver que la mayor suma posible en $S_{1}$ es 19, por lo que las sumas en $S_{2}$ y $S_{3}$ deberían ser menores que 19. En $S_{2}$ y $S_{3}$ hay que incluír los números del 1 al 8, pero $1+2+3+4+5+6+7+8=36$. Es decir: $S_{2}<19$, $S_{3}<19$ y $S_{2} + S_{3} = 36$. La única forma de lograrlo sería si las sumas de $S_{2}$ y $S_{3}$ son 18, pero para cumplir con el enunciado la suma de $S_{2}$ debería ser mayor que la de $S_{3}$, por lo que descartamos este caso.

Si $n = 11$, hay dos posibles distribuciones de cantidades de números en los subconjuntos tales que $S_{1}$ tenga más de un número: 2 en $S_{1}$, 3 en $S_{2}$ y 6 en $S_{3}$ o 2 en $S_{1}$, 4 en $S_{2}$ y 5 en $S_{3}$. Es fácil ver que la mayor suma posible en $S_{1}$ es 21, por lo que las sumas en $S_{2}$ y $S_{3}$ deberían ser menores que 21. En $S_{2}$ y $S_{3}$ hay que incluír los números del 1 al 9, pero $1+2+3+4+5+6+7+8+9=45$. Es decir: $S_{2}<21$, $S_{3}<21$ y $S_{2} + S_{3} = 45$, absurdo.

Si $n = 13$, una distribución que satisface las condiciones del problema es: $S_{1}$ = {11, 12, 13} (suma 36), $S_{2}$ = {7, 8, 9, 10} (suma 34) y $S_{3}$ = {1, 2, 3, 4, 5, 6} (suma 21).

Basándonos en esta distribución podemos afirmar que siempre que $n \equiv 1 \mod{3}$ habrá una distribución que satisfaga las condiciones ya que, al igual que para $n \equiv 0 \mod{3}$, siempre que se agreguen tres números consecutivos, el mayor irá a $S_{1}$, el del medio a $S_{2}$ y el menor a $S_{3}$, y de esta manera no se alterarán las relaciones de cantidades ni las de sumas.

Si $n = 14$, una distribución que satisface las condiciones del problema es: $S_{1}$ = {12, 13, 14} (suma 39), $S_{2}$ = {7, 8, 9, 10} (suma 34) y $S_{3}$ = {1, 2, 3, 4, 5, 6, 11} (suma 32).

Basándonos en esta distribución podemos afirmar que siempre que $n \equiv 2 \mod{3}$ habrá una distribución que satisfaga las condiciones ya que, al igual que para $n \equiv 0 \mod{3}$ y $n \equiv 1 \mod{3}$, siempre que se agreguen tres números consecutivos, el mayor irá a $S_{1}$, el del medio a $S_{2}$ y el menor a $S_{3}$, y de esta manera no se alterarán las relaciones de cantidades ni las de sumas.

Entonces, la respuesta final es que $n = \mathbb{N} - \left\lbrace 1, 2, 3, 4, 5, 6, 7, 8, 10, 11 \right\rbrace $
1  
Matías

OFO - Medalla de Bronce-OFO 2016 OFO - Medalla de Bronce-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 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 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 206
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 8
Nivel: 3

Re: Selectivo de Cono 2018 P2

Mensaje sin leer por Matías »

Spoiler: mostrar
Sea $A$ el subconjunto con mayor cantidad de números y menor suma, $B$ el subconjunto "del medio" y $C$ el subconjunto con menor cantidad de números y mayor suma.

Como $|C|\geq 1$, $|B|\geq 2$ y $|A|\geq 3$, tenemos que $n\geq 6$.

Veamos que si $n\equiv 0(3)$ y $n\geq 12$ podemos elegir los siguientes subconjuntos:
$A=${$x/x\in N\wedge x\leq \frac{n}{3}+1$} $|A|=\frac{n}{3}+1$
$B=${$x/x\in N\wedge \frac{n}{3}+2\leq x\leq \frac{2n}{3}+1$} $|B|=\frac{n}{3}$
$C=${$x/x\in N\wedge \frac{2n}{3}+2\leq x\leq n$} $|C|=\frac{n}{3}-1$
Podemos ver que $\sum_{x\in A}x<\sum_{x\in B}x$ ya que $1+2=3<6\leq \frac{n}{3}+2$, y que $\sum_{x\in B}x<\sum_{x\in C}x$ ya que $(\frac{n}{3}+2)+(\frac{n}{3}+3)-3\leq\frac{2n}{3}+2$, $n\geq (\frac{2n}{3}+1)+(\frac{n}{3}-1)\geq(\frac{2n}{3}+1)+3$, y $\frac{n}{3}+4<\frac{2n}{3}+3$.

Veamos que si $n\equiv 1(3)$ y $n\geq 13$ podemos elegir los siguientes subconjuntos:
$A=${$x/x\in N\wedge x\leq \frac{n+2}{3}+1$} $|A|=\frac{n+2}{3}+1$
$B=${$x/x\in N\wedge \frac{n+2}{3}+2\leq x\leq\frac{2n+1}{3}+1$} $|B|=\frac{n+2}{3}-1$
$C=${$x/x\in N\wedge \frac{2n+1}{3}+2\leq x\leq n$} $|C|=\frac{n+2}{3}-2$
Podemos ver que $\sum_{x\in A}x<\sum_{x\in B}x$ ya que $1+2+3=6<7\leq\frac{n+2}{3}+2$, y que $\sum_{x\in B}x<\sum_{x\in C}x$ ya que $(\frac{n+2}{3}+2)+(\frac{n+2}{3}+3)-4\leq (\frac{2n+1}{3}+2)$, $n\geq(\frac{2n+1}{3}+1)+(\frac{n-1}{3}-1)\geq\frac{2n+1}{3}+3$, y $n-1\geq(\frac{2n+1}{3})+(\frac{n-4}{3})\geq\frac{2n+1}{3}+3$

Veamos que si $n\equiv 2(3)$ y $n\geq 20$ podemos elegir los siguientes subconjuntos:
$A=${$x/x\in N\wedge x\leq \frac{n+1}{3}+1$} $|A|=\frac{n+1}{3}+1$
$B=${$x/x\in N\wedge \frac{n+1}{3}+2\leq x\leq \frac{2n+2}{3}+1$} $|B|=\frac{n+1}{3}$
$C=${$x/x\in N\wedge \frac{2n+2}{3}+2\leq x\leq n$} $|C|=\frac{n+1}{3}-2$
Podemos ver que $\sum_{x\in A}x<\sum_{x\in B}x$ ya que $1+2+3=6<9\leq\frac{n+1}{3}+2$, y que $\sum_{x\in B}x<\sum_{x\in C}x$ ya que $(\frac{n+1}{3}+2)+(\frac{n+1}{3}+3)+(\frac{n+1}{3}+4)-10\leq n$, $n-1\geq(\frac{n+1}{3}+5)+(\frac{2n-1}{3}-6)\geq(\frac{n+1}{3}+5)+7$, y $n-2\geq(\frac{n+1}{3}+6)+(\frac{2n-1}{3}-8)\geq(\frac{n+1}{3}+6)+5$

Si $n=9$ podemos tomar $A=${$1, 2, 3, 6$}, $B=${$4, 5, 7$} y $C=${$8, 9$}
Si $n=14$ podemos tomar $A=${$1, 2, 3, 4, 5, 6, 7$}, $B=${$8, 9, 10, 11$} y $C=${$12, 13, 14$}
Si $n=17$ podemos tomar $A=${$1, 2, 3, 4, 5, 6, 7, 15$}, $B=${$8, 9, 10, 11, 16$} y $C=${$12, 13, 14, 17$}

Si $n=6$ tenemos que debe ser $|C|=1$ y $|A|=3$, entonces $\sum_{x\in A}x\geq 1+2+3=6\geq\sum_{x\in C}x$ (absurdo).
Si $n=7\vee 8$ tenemos que debe ser $|C|=1$ y $|A|\geq 4$, entonces $\sum_{x\in A}x\geq 1+2+3+4=10>8\geq\sum_{x\in C}x$ (absurdo).
Si $n=10$ tenemos que $|C|\leq 2$, entonces $\sum_{x\in C}x\leq 9+10=19\implies \sum_{x\in B}x\leq 18\wedge \sum_{x\in A}x\leq 17\implies \sum_{i=1}^{10}i\leq 55$, pero tenemos que $\sum_{i=1}^{10}i=55$ (absurdo).
Si $n=11$ tenemos que $|C|\leq 2$, entonces $\sum_{x\in C}x\leq 10+11=21\implies \sum_{i=1}^{11}i\leq 60$, pero tenemos que $\sum_{i=1}^{11}i=66$ (absurdo).

Por lo tanto concluimos que los naturales $n$ que cumplen son $n=9$ y $n\geq 12$.
Responder