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.
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore! Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
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)$.
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.
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
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.
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
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.
Ojo que dado que los números tienen que ser distintos, justo ese ejemplo falla.
Dejo un ejemplo que anda:
Ejemplo con seis números: $S = \{-2, -1, 3, 5, 6, 10\}$
Se pueden construir grupitos de $3$ enteros $\{a, b, c\}$ tales que los tres pares $(a,b), (b,c), (a,c)$ suman una potencia de $2$.
Nos armamos dos de estos grupitos:
$A = \{-1, 3, 5\}$
$B = \{-2, 6, 10\}$
(Datazo: Notese que cualquier terna de la forma $\{-2^k, 3.2^k, 5.2^k\}$ anda)
Y por palomar cualquier terna de elementos de $S = A\cup B$ tiene al menos dos elementos de alguno $A$ o $B$, esos dos suman una potencia de dos y ganamos!