Problema 2 Cono Sur 2018

Problemas que aparecen en el Archivo de Enunciados.
jujumas

OFO - Mención-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Oro perfecto-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017
FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
OFO - Jurado-OFO 2020
Mensajes: 399
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 11
Nivel: Exolímpico

Problema 2 Cono Sur 2018

Mensaje sin leer por jujumas » Sab 25 Ago, 2018 4:58 pm

Demostrar que todo entero positivo puede ser representado como suma de potencias de $3$, $4$ y $7$ de modo que no aparezcan en la representación dos potencias con la misma base y el mismo exponente.

Por ejemplo: $2=7^0+7^0$ y $22=3^2+3^2+4^1$ no son representaciones válidas, pero $2=3^0+7^0$ y $22=3^2+3^0+4^1+4^0+7^1$ si son válidas.

jujumas

OFO - Mención-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Oro perfecto-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017
FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
OFO - Jurado-OFO 2020
Mensajes: 399
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 11
Nivel: Exolímpico

Re: Problema 2 Cono Sur 2018

Mensaje sin leer por jujumas » Sab 25 Ago, 2018 6:04 pm

Solución:
Spoiler: mostrar
Lema: $\left (\sum \limits _{i=0}^{p-1}3^i\right )+\left (\sum \limits _{j=0}^{q-1}4^j\right )+\left (\sum \limits _{k=0}^{r-1}7^k\right )+1\geq \min \left \{3^p;4^q;7^r \right \}$.

Demostración: Supongamos lo contrario. Luego, por suma de potencias de igual base, tenemos al multiplicar por $6$ que $3\left (3^p-1\right )+2\left (4^q-1\right )+\left (7^r-1\right )+6<6\left (\min \left \{3^p;4^q;7^r\right \}\right )$. Entonces tenemos que $3\left (3^p\right )+2\left (4^q\right )+7^r<6\left (3^p\right )$. Luego, $\frac{1}{2}\left (3\left (3^p\right )+2\left (4^q\right )+7^r\right )<3\left (3^p\right )$. Además, tenemos que $3\left (3^p\right )+2\left (4^q\right )+7^r<6\left (4^q\right )$, de donde $\frac{1}{3}\left (3\left (3^p\right )+2\left (4^q\right )+7^r\right )<2\left (4^q\right )$ y que $3\left (3^p\right )+2\left (4^q\right )+7^r<6\left (7^r\right )$, de donde $\frac{1}{6}\left (3\left (3^p\right )+2\left (4^q\right )+7^r\right )<\left (7^r\right )$. Sumando estas tres desigualdades, tenemos que:

$$\frac{1}{2}\left (3\left (3^p\right )+2\left (4^q\right )+7^r\right )+\frac{1}{3}\left (3\left (3^p\right )+2\left (4^q\right )+7^r\right )+\frac{1}{6}\left (3\left (3^p\right )+2\left (4^q\right )+7^r\right )<3\left (3^p\right )+2\left (4^q\right )+7^r$$

lo que claramente es un absurdo, al ser ambos lados iguales. Esto demuestra el Lema.


Para todos enteros positivos $x$, $y$, $z$, llamemos $\mathbb{F}(x;y;z)$ al conjunto de enteros positivos expresables según las reglas del enunciado en donde los máximos exponentes a los que se eleva $3$, $4$ y $7$ son menores o iguales a $x$, $y$ y $z$ respectivamente. Notemos que el mínimo elemento de $\mathbb{F}(x;y;z)$ es $1$ y que el máximo es $\left (\sum \limits _{i=0}^{x}3^i\right )+\left (\sum \limits _{j=0}^{y}4^j\right )+\left (\sum \limits _{k=0}^{z}7^k\right )$.

Ahora, vamos a decir que $\mathbb{F}(x;y;z)$ es conexo si incluye a todos los enteros positivos entre estos extremos. Notemos entonces que $\mathbb{F}(0;0;0)$ es conexo.

Es facil ver que $\mathbb{F}(x+1;y;z)$ incluye a la unión de $\mathbb{F}(x;y;z)$, a $3^{x+1}$, y la suma entre $3^{x+1}$ y cualquier elemento de $\mathbb{F}(x;y;z)$. Análogamente, podemos ver lo que sucede con $\mathbb{F}(x;y+1;z)$ y con $\mathbb{F}(x;y;z+1)$.

Con esto, podemos probar que si $\mathbb{F}(x;y;z)$ es conexo, al menos uno de $\mathbb{F}(x+1;y;z)$, $\mathbb{F}(x;y+1;z)$, $\mathbb{F}(x;y;z+1)$ es conexo, lo que es facil de ver por el Lema. Luego, como $\mathbb{F}(0;0;0)$ es conexo, podemos conseguir conjuntos conexos arbitrariamente grandes, por lo que todo entero positivo esta incluído en al menos uno. Esto demuestra lo pedido.

Responder