Problema 2 APMO 2006

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

OFO - Medalla de Bronce-OFO 2016 OFO - Medalla de Bronce-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años
OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 202
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 8
Nivel: 3

Problema 2 APMO 2006

Mensaje sin leer por Matías » Mié 13 Sep, 2017 6:57 pm

Demostrar que todo entero positivo se puede escribir como una suma finita de potencias enteras distintas del número de oro $\varphi=\frac{1+\sqrt{5}}{2}$. Aquí, una potencia entera de $\varphi$ es de la forma $\varphi ^i$, donde $i$ es un entero (no necesariamente positivo).

Avatar de Usuario
NicoRicci

OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 26
Registrado: Lun 08 Oct, 2018 2:31 pm
Medallas: 3
Nivel: 2

Re: Problema 2 APMO 2006

Mensaje sin leer por NicoRicci » Lun 08 Jun, 2020 9:43 am

Pregunta:
Spoiler: mostrar
¿Se puede sumar dos o más veces la misma potencia?
OWEEEEEEE

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 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
Mensajes: 1291
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 7
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Problema 2 APMO 2006

Mensaje sin leer por Gianni De Rico » Lun 08 Jun, 2020 10:01 am

NicoRicci escribió:
Lun 08 Jun, 2020 9:43 am
Pregunta:
Spoiler: mostrar
¿Se puede sumar dos o más veces la misma potencia?
Respuesta:
Spoiler: mostrar
No, porque tienen que ser distintas. En caso contrario la solución sería simplemente $n=n\cdot \varphi ^0$.
Queda Elegantemente Demostrado

Avatar de Usuario
Joacoini

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-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
Mensajes: 356
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 7
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Re: Problema 2 APMO 2006

Mensaje sin leer por Joacoini » Mié 10 Jun, 2020 7:58 pm

Solución:
Spoiler: mostrar
Vamos a demostrar por inducción que todo entero positivo $n$ se puede expresar de la forma
$n=\varphi^{a_1}+\varphi^{a_2}+...+\varphi^{a_k}$
Donde $a_1<a_2<...<a_k$ y $a_{i+1}-a_i\geq 2$.

Para $n=1$ tenemos que $1=\varphi^{0}$, supongamos que para $n$ lo podemos construir, veamos que pasa para $n+1$.

Si $n=\varphi^{a_1}+\varphi^{a_2}+...+\varphi^{a_k}$ entonces $n+1=\varphi^{0}+\varphi^{a_1}+\varphi^{a_2}+...+\varphi^{a_k}$
Ahora vamos a realizar dos algoritmos, si existe $i$ tal que $a_i=0$ hacemos el algoritmo 1 y el 2, si no existe tal $i$ vamos directo al algoritmo 2.
En ambos algoritmos se va a utilizar que $\varphi^{n+2}=\varphi^{n+1}+\varphi^{n}$ lo cual es cierto ya que al multiplicar por $\varphi^{-n}$ obtenemos $\varphi^{2}=\varphi^{1}+1$.

Algoritmo 1
Si existe $i$ tal que $\varphi^{a_i}$ aparece dos veces en la suma reemplazamos uno de estos por $\varphi^{a_i-1}+\varphi^{a_1-2}$, si ahora existe un nuevo $i'$ tal que $\varphi^{a_{i'}}$ aparece dos veces en la suma entonces repetimos el algoritmo en caso contrario pasamos al algoritmo 2.

Veamos que este algoritmo termina, primero notemos que si antes de aplicarlo solo había una potencia de $\varphi$ que se repetía dos veces y su exponente se podía expresar como $a_i$ entonces luego de aplicar el algoritmo hay dos opciones, ya no se repite ninguna potencia de $\varphi$ por lo que el algoritmo termina o hay una nueva potencia de $\varphi$ que se repite dos veces, esta puede ser $\varphi^{a_i-1}$ ó/y $\varphi^{a_i-2}$, de esto sabemos que $i$ va decreciendo.
Si $\varphi^{a_i-1}$ es la que se repite entonces la otra copia es un $a_j$ ó apareció de aplicar el algoritmo en $a_{i}+1$ ó en $a_i$ (en $a_i$ es imposible porque $i$ va decreciendo), en el primer caso tenemos que $a_i-1=a_j\Rightarrow a_i-a_j=1$ contradicción, en el segundo caso como se aplico el algoritmo en $a_i+1$ existe un $j$ tal que $a_j=a_i+1\Rightarrow a_j-a_i=1$ contradicción por lo tanto $\varphi^{a_i-1}$ no se repite.
Si $\varphi^{a_i-2}$ es la que se repite entonces la otra copia es un $a_j$ ó apareció de aplicar el algoritmo en $a_{i}$ ó en $a_{i-1}$, en el primer caso volvemos a aplicar el algoritmo y el segundo caso contradice que $i$ decrece.
Como cada vez que se aplica el algoritmo $i>i'>0$ (en el caso de haber un $i'$) tenemos que este termina.

Algoritmo 2
Si en la suma están $\varphi^{m}$ y $\varphi^{m-1}$ y no esta $\varphi^{m+1}$ reemplazamos $\varphi^{m}+\varphi^{m-1}$ por $\varphi^{m+1}$, si esta situación sigue sucediendo aplicamos de vuelta el algoritmo en caso contrario finalizamos.

Este algoritmo termina ya que la cantidad de potencias de $\varphi$ se reduce en cada paso.


Una vez terminados ambos algoritmos nos queda $n+1=\varphi^{b_1}+\varphi^{b_2}+...+\varphi^{b_q}$, por el algoritmo 1 sabemos que todas las potencias son distintas, así que $b_1<b_2<...<b_q$, también se cumple que $b_{i+1}-b_i\geq 2$ ya que en caso contrario si $j$ es el mayor entero positivo que no cumple entonces $b_{j+1}-b_j=1$ y $b_{j+2}>b_{j+1}+1$ pero esto contradice que el algoritmo 2 haya terminado y con esto concluimos la inducción.
2  
NO HAY ANÁLISIS.

Responder