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: 206
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 8
Nivel: 3

Problema 2 APMO 2006

Mensaje sin leer por Matías »

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 OFO - Medalla de Plata-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años
OFO - Medalla de Plata-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: 58
Registrado: Lun 08 Oct, 2018 2:31 pm
Medallas: 11
Nivel: Exolímpico

Re: Problema 2 APMO 2006

Mensaje sin leer por NicoRicci »

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 FOFO 9 años - Jurado-FOFO 9 años 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 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Problema 2 APMO 2006

Mensaje sin leer por Gianni De Rico »

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$.
♪♫ do re mi función lineal ♪♫
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 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 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 460
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 16
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Re: Problema 2 APMO 2006

Mensaje sin leer por Joacoini »

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