Selectivo Cono Sur 2019 P2

Avatar de Usuario
Matías V5

Colaborador OFO - Jurado FOFO 6 años - Jurado
Mensajes: 905
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 6
Nivel: Exolímpico

Selectivo Cono Sur 2019 P2

Mensaje sin leer por Matías V5 » Jue 28 Mar, 2019 9:28 pm

Matías construye una lista de números enteros con la siguiente propiedad: para cada tres números de la lista hay dos de ellos que sumados dan por resultado una potencia de $2$ con exponente entero no negativo. Determinar la mayor cantidad de números que puede tener la lista de Matías.
"La geometría es el arte de hacer razonamientos correctos a partir de figuras incorrectas." -- Henri Poincaré

maxiR

OFO - Mención FOFO 8 años - Mención Especial OFO - Medalla de Bronce
Mensajes: 21
Registrado: Vie 26 Ene, 2018 3:30 pm
Medallas: 3
Nivel: 1
Ubicación: Barrancas

Re: Selectivo Cono Sur 2019 P2

Mensaje sin leer por maxiR » Vie 29 Mar, 2019 12:05 am

los numeros de la lista son todos distintos?

Avatar de Usuario
¿hola?

OFO - Mención OFO - Medalla de Bronce OFO - Medalla de Plata
Mensajes: 96
Registrado: Vie 01 Ene, 2016 1:12 am
Medallas: 4
Nivel: 3

Re: Selectivo Cono Sur 2019 P2

Mensaje sin leer por ¿hola? » Vie 29 Mar, 2019 12:25 am

maxiR escribió:
Vie 29 Mar, 2019 12:05 am
los numeros de la lista son todos distintos?
Si.
Yes, he who

Avatar de Usuario
¿hola?

OFO - Mención OFO - Medalla de Bronce OFO - Medalla de Plata
Mensajes: 96
Registrado: Vie 01 Ene, 2016 1:12 am
Medallas: 4
Nivel: 3

Re: Selectivo Cono Sur 2019 P2

Mensaje sin leer por ¿hola? » Vie 29 Mar, 2019 3:56 pm

Spoiler: mostrar
Lama 1: no existen $x,y,z$ enteros distintos tales que cualesquiera dos de ellos sumados son una potencia de $2$
Demostración:
Spoiler: mostrar
supongamos que existen y son $x,y,z$
$x+y=2^a \Rightarrow x≡-y$ $mod$ $2^a$
$y+z=2^b \Rightarrow y≡-z$ $mod$ $2^a$
$x+z=2^c \Rightarrow z≡-x$ $mod$ $2^a$
Es claro q $a,b,c$ son todos distintos, sin perdida de generalidad $a<b<c$
luego $x≡-y≡z≡-x$ $mod$ $2^a$ y como $a<2^a$ entonces $a=2^{a-1}$ que implica $y=2^a-2^{a-1}=2^a=x$ absurdo, por lo que no existen $x,y,z$
Supongamos que los números $a,b,c,d,e$ son enteros que cumplen la propiedad de la lista.

Lema 2: cada elemento suma una potencia de $2$ con exactamente dos de los otros elementos en $(a,b,c,d,e)$.
Spoiler: mostrar
Supongamos que $a+b$, $a+c$, $a+d$ son potencias de $2$ entonces en el subconjunto $(b,c,d)$ no hay dos números que sumen una potencia de $2$ porque si no contradice el lema 1, osea $a$ suma una potencia de $2$ con menos de tres de los otros números.
Si $a$ solo suma una potencia de $2$ con $b$ entonces tomamos de $(c,d,e)$ dos números $x$,$y$ tales que no suman una potencia de $2$, entonces en $(a,x,y)$ se incumple el enunciado, osea $a$ suma una potencia de $2$ con mas de uno de los otros números.
Esto demuestra lo que pedimos.
Sin perdida de generalidad $a$ suma una potencia de $2$ con $b$ y $c$, $b$ con $a$ y $d$, luego $d$ con $b$ y $e$ (no puede sumar con $c$ por que si no el conjunto $(c,d,e)$ incumpliría el lema 1, luego $e$ suma una potencia de $2$ con $c$ y $d$. Osea
$a+b=2^{k1} \Rightarrow a≡-b$ $mod$ $2^{k1}$
$a+c=2^{k2} \Rightarrow a≡-c$ $mod$ $2^{k1}$
$b+d=2^{k3} \Rightarrow b≡-d$ $mod$ $2^{k1}$
$d+e=2^{k4} \Rightarrow d≡-e$ $mod$ $2^{k1}$
$e+c=2^{k5} \Rightarrow e≡-c$ $mod$ $2^{k1}$
Sin perdida de generalidad $k1$ es el menor
Entonces $a≡-b≡d≡-e≡c≡-a$ $mod$ $2^{k1}$ osea $a=2^{k1-1}$ que implica $b=a=2^{k1-1}$ lo que es absurdo. Entonces la lista tiene menos de $5$ elementos.
Ejemplo con $4$ números, $(1,2,3,6)$. La lista de Raimu tiene como máximo $4$ elementos.
1  
Yes, he who

Avatar de Usuario
Turko Arias

Colaborador OFO - Medalla de Plata OFO - Medalla de Oro FOFO Pascua 2019 - Medalla
Mensajes: 263
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 4
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: Selectivo Cono Sur 2019 P2

Mensaje sin leer por Turko Arias » Vie 29 Mar, 2019 4:21 pm

Más allá de que los problemas no son el mismo, conocer este problema 34 T. I. de las Ciudades Primavera 2012 N Mayor Problema 1 te ayuda bastante a saber por donde puede ir la solución, y es más, hay soluciones que trabajan alrededor de este problema, planteándolo como un lema :mrgreen: :mrgreen: :mrgreen:

BrunZo

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

Re: Selectivo Cono Sur 2019 P2

Mensaje sin leer por BrunZo » Vie 29 Mar, 2019 9:29 pm

¿hola? escribió:
Vie 29 Mar, 2019 3:56 pm
Spoiler: mostrar
La lista de Raimu tiene como máximo $4$ elementos.
Spoiler: mostrar
Me parece que no es cierto eso. Fijate que los números pueden ser negativos. Por ejemplo, $\{-1,3,5,-3,5,11\}$ funciona correctamente. De hecho, el máximo es $6$ elementos.
EDIT: Solución oficial:
Spoiler: mostrar
Vamos a demostrar que el máximo es $6$, por ejemplo $\{-1,3,5,-3,5,11\}$.
Supongamos que hay $7$ números o más. Si hubiese más de dos enteros no positivos, elegimos tres de ellos y ninguno da potencia de $2$. Por lo que hay, al menos, cinco enteros positivos. Tomemos el mayor de ellos $M$ y otros cuatro $a$, $b$, $c$, $d$. Como $M+a$, $M+b$, $M+c$, $M+d$ están entre $M$ y $2M$, hay, como mucho, una potencia de $2$ entre ellos, digamos $M+a$. Ahora, tomemos los grupos $(M,b,c)$, $(M,b,d)$, $(M,c,d)$. Como $M+b$, $M+c$, $M+d$ no son potencias de dos, $b+c$, $b+d$, $c+d$ deberán ser potencias de dos. Veamos que esto es imposible:
Supongamos que $b$ es el mayor de $\{b,c,d\}$. Como antes, $b+c$, $b+d$ están entre $b$ y $2b$, luego sólo uno es potencia de $2$. Absurdo.
Con esto finalizamos la demostración

Responder