Nacional 2019 N3 P1

Problemas que aparecen en el Archivo de Enunciados.
LuchoLP

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Bronce-OFO 2016 OFO - Medalla de Plata-OFO 2017
Mensajes: 191
Registrado: Mié 17 Abr, 2013 7:27 pm
Medallas: 3
Nivel: Exolímpico

Nacional 2019 N3 P1

Mensaje sin leer por LuchoLP » Jue 14 Nov, 2019 10:32 am

Un conjunto de números enteros positivos distintos se llama singular si, para cada uno de sus elementos, luego de tachar ese elemento, los restantes se pueden agrupar en dos conjuntos sin elementos comunes de modo que la suma de los elementos de los dos grupos sea la misma. Hallar el menor entero positivo $n>1$ tal que existe un conjunto singular $A$ con $n$ elementos.

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

Re: Nacional 2019 N3 P1

Mensaje sin leer por Gianni De Rico » Sab 21 Dic, 2019 8:38 pm

Una solución mía mezclada con lo que explicó @Joacoini en el Nacional

Solución:
Spoiler: mostrar
Si dos sumas son iguales, estaría bueno que ambas tengan la misma cantidad de elementos. Vamos a ver entonces que los pares no funcionan.
Sea $n=2k$, y sean $a_1,\ldots ,a_{2k}$ los elementos de $A$, cada vez que sacamos un $a_i$, nos quedan dos conjuntos de suma $S_i$, y si llamamos $S$ a la suma de los $a_i$, tenemos que $a_i+2S_i=S$, de donde $a_i\equiv S\pmod 2$, entonces todos los $a_i$ tienen la misma paridad, por lo que $S$ es par, entonces los $a_i$ son pares. Sea $e_i$ el exponente de $2$ en la factorización de cada $a_i$, y sea $m$ el mínimo de los $e_i$. Dividiendo todos los $a_i$ por $2^m$ tenemos un nuevo conjunto con $b_i=\frac{a_i}{2^m}$ que funciona, y tiene al menos un elemento impar, entonces aplicando el mismo razonamiento, tenemos que todos los $b_i$ son pares, absurdo porque al menos uno es impar.
Los pares no funcionan.

Vemos que $3$ no funciona porque si saco uno, los otros dos tienen que ser iguales (porque su suma no es $0$), y son distintos por enunciado.

Ahora lo molesto, ver que el $5$ no funciona.
Supongamos que el $5$ funciona.
Sean $a_1<a_2<a_3<a_4<a_5$ los elementos de $A$.
Saco $a_4$.
Tenemos que $a_5+a_3>a_2+a_1$, entonces no pueden ir así (ni sumarle más al LHS).
Tenemos que $a_5+a_2>a_3+a_1$ porque $a_5>a_3$ y $a_2>a_1$, entonces no pueden ir así.
Queda que $a_5+a_1=a_3+a_2$ o $a_5=a_1+a_2+a_3$.
Supongamos que pasa la primera.
Saco $a_3$.
Por el mismo razonamiento, solamente puede ser $a_5+a_1=a_4+a_2$ o $a_5=a_1+a_2+a_4$.
Si pasa la primera, entonces $a_3=a_4$, si pasa la segunda, entonces $2a_1+a_3+a_4=a_3+a_2$. El primer caso es absurdo porque los elementos son distintos, el segundo porque $a_2<a_4$ y son todos positivos. Supongamos que pasa la segunda (de cuando saco $a_4$).
Saco $a_3$.
Por el mismo razonamiento, solamente puede ser $a_5+a_1=a_4+a_2$ o $a_5=a_1+a_2+a_4$.
Si pasa la segunda, entonces $a_3=a_4$. Entonces solamente puede pasar la primera.
Saco $a_2$.
Por el mismo razonamiento, solamente puede ser $a_5+a_1=a_4+a_3$ o $a_5=a_1+a_3+a_4$.
Si pasa la primera, entonces $a_2=a_3$. Si pasa la segunda, entonces $a_2=a_4$. Absurdo.

Como en todos los casos llegamos a un absurdo, el $5$ no funciona.

El $7$ funciona, un ejemplo es $A=\{1,~3,~5,~7,~9,~11,~13\}$.
1  
Queda Elegantemente Demostrado

Responder