Selectivo Cono Sur 2019 P2

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

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021
Mensajes: 1114
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Selectivo Cono Sur 2019 P2

Mensaje sin leer por Matías V5 »

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
maxiR

OFO - Mención-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Bronce-OFO 2019
Mensajes: 26
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 »

los numeros de la lista son todos distintos?
Avatar de Usuario
¿hola?

OFO - Mención-OFO 2016 OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Plata-OFO 2019 OFO - Medalla de Oro-OFO 2020
COFFEE - Mención-COFFEE Ariel Zylber OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022
Mensajes: 164
Registrado: Vie 01 Ene, 2016 1:12 am
Medallas: 9
Nivel: Exolímpico
Contactar:

Re: Selectivo Cono Sur 2019 P2

Mensaje sin leer por ¿hola? »

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 2016 OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Plata-OFO 2019 OFO - Medalla de Oro-OFO 2020
COFFEE - Mención-COFFEE Ariel Zylber OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022
Mensajes: 164
Registrado: Vie 01 Ene, 2016 1:12 am
Medallas: 9
Nivel: Exolímpico
Contactar:

Re: Selectivo Cono Sur 2019 P2

Mensaje sin leer por ¿hola? »

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.
Yes, he who
Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 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 COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023
Mensajes: 591
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 17
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: Selectivo Cono Sur 2019 P2

Mensaje sin leer por Turko Arias »

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:
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
BrunZo

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Copa-FOFO 10 años OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años
OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 414
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 16
Nivel: 3

Re: Selectivo Cono Sur 2019 P2

Mensaje sin leer por BrunZo »

¿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
Avatar de Usuario
Brimix

OFO - Medalla de Oro-OFO 2015 OFO - Medalla de Oro-OFO 2016 OFO - Medalla de Plata-OFO 2019 OFO - Medalla de Oro-OFO 2020 OFO - Medalla de Plata-OFO 2021
OFO - Medalla de Plata-OFO 2023 OFO - Medalla de Oro-OFO 2024
Mensajes: 97
Registrado: Dom 21 Abr, 2013 10:00 am
Medallas: 7
Nivel: Exolímpico
Ubicación: Rosario♥
Contactar:

Re: Selectivo Cono Sur 2019 P2

Mensaje sin leer por Brimix »

Buenas!
BrunZo escribió: Vie 29 Mar, 2019 9:29 pm
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.
Ojo que dado que los números tienen que ser distintos, justo ese ejemplo falla.
Dejo un ejemplo que anda:
Spoiler: mostrar
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!
2  
♪♫Nuestro ARG2 es nuestro ejemplo. 'Efe de equis mas one!'♫♪
Responder