Selectivo de Cono 2018 P2

Matías

OFO - Medalla de Bronce FOFO Pascua 2017 - Medalla OFO - Medalla de Plata
Mensajes: 104
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 4
Nivel: 2

Selectivo de Cono 2018 P2

Mensaje sin leer por Matías » Jue 12 Abr, 2018 9:16 pm

Hallar todos los números enteros positivos $n$ con la siguiente propiedad: los números del $1$ al $n$, $1$, $2$,...,$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: 3
Registrado: Vie 17 Jul, 2015 9:04 pm
Nivel: Exolímpico

Re: Selectivo de Cono 2018 P2

Mensaje sin leer por Santito » Vie 13 Abr, 2018 1:18 pm

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 FOFO Pascua 2017 - Medalla OFO - Medalla de Plata
Mensajes: 104
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 4
Nivel: 2

Re: Selectivo de Cono 2018 P2

Mensaje sin leer por Matías » Dom 15 Abr, 2018 12:54 pm

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