Problema 2 Cono Sur 2018

jujumas

OFO - Mención OFO - Medalla de Plata FOFO 7 años - Medalla Especial OFO - Oro perfecto FOFO Pascua 2017 - Medalla
OFO - Medalla de Oro
Mensajes: 342
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 7
Nivel: 2

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 - Medalla de Plata FOFO 7 años - Medalla Especial OFO - Oro perfecto FOFO Pascua 2017 - Medalla
OFO - Medalla de Oro
Mensajes: 342
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 7
Nivel: 2

Re: Problema 2 Cono Sur 2018

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

Solución:
Spoiler: mostrar
Lema: $(\sum_{i=0}^{p-1} 3^i) + (\sum_{j=0}^{q-1} 4^j) + (\sum_{k=0}^{r-1} 7^k) + 1 \geq mín\{3^p; 4^q; 7^r\}$.

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

$$\frac{1}{2}(3(3^p) + 2(4^q) + 7^r) + \frac{1}{3}(3(3^p) + 2(4^q) + 7^r) + \frac{1}{6}(3(3^p) + 2(4^q) + 7^r) < 3(3^p) + 2(4^q) + 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 $(\sum_{i=0}^{x} 3^i) + (\sum_{j=0}^{y} 4^j) + (\sum_{k=0}^{z} 7^k)$.

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