Bonito problema de MCD.

Avatar de Usuario
Emerson Soriano

OFO - Mención-OFO 2015 OFO - Medalla de Oro-OFO 2016 OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Mención-OFO 2020
OFO - Medalla de Plata-OFO 2022
Mensajes: 826
Registrado: Mié 23 Jul, 2014 10:39 am
Medallas: 6

Bonito problema de MCD.

Mensaje sin leer por Emerson Soriano »

Sea $a_0$, $a_1$, $a_2$, ... una sucesión de enteros positivos tal que $\text{mcd}(a_{n+1}, a_n)>a_{n-1}$ para todo entero positivo $n$. Demostrar que $a_n\geq 2^n$ para todo entero $n\geq 0$.
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

Re: Bonito problema de MCD.

Mensaje sin leer por Matías »

Spoiler: mostrar
Tenemos que $a_n>a_{n-1}$ $\forall n\in N$ ya que si $a_n\leq a_{n-1}$ entonces $dcm(a_{n+1},a_n)\leq a_n\leq a_{n-1}$ cuando $dcm(a_{n+1},a_n)>a_{n-1}$ (absurdo).

Como $a_0$ es un número natural entonces $a_0\geq 1=2^0$, y como $dcm(a_2,a_1)>a_0\geq 1$ debe ser $a_1\geq 2=2^1$ ya que si $a_1=1$ entonces $dcm(a_2,a_1)=dcm(a_2,1)=1>a_0\geq 1$ (absurdo). Y tenemos que $a_2\geq 4=2^2$ ya que $a_2>a_1\geq 2$, entonces si $a_2<4$ debe ser $a_2=3$ y $a_1=2$, pero entonces $dcm(a_2,a_1)=dcm(3,2)=1>a_0\geq 1$ (absurdo).
También tenemos que $a_3\geq 8=2^3$ ya que como $dcm(a_3,a_2)>a_1\geq 2\implies a_3\geq 3+a_2$, si $a_3<8$ debe ser $a_3=7$ y $a_2=4$, pero entonces $dcm(a_3,a_2)=dcm(7,4)=1>a_1\geq 2$ (absurdo).

Ahora si para cierto $n\in N$, $n\geq 3$ tenemos que $a_i\geq 2^i$ $\forall(i\in N_0\wedge i\leq n)$ vamos a demostrar que $a_{n+1}\geq 2^{n+1}$:
De ser $a_n\geq 2^{n+1}$ ya tendríamos que $a_{n+1}>a_n\geq 2^{n+1}$, por lo tanto suponemos que $a_n<2^{n+1}$.

Llamemos $d=dcm(a_{n+1},a_{n})$. Como $2^{n+1}>a_n\geq d>a_{n-1}\geq 2^{n-1}$, tenemos que $\frac{a_n}{d}<\frac{2^{n+1}}{2^{n-1}}=4$, por lo tanto $a_n=d\vee a_n=2d\vee a_n=3d$.
Si $a_n=3d$ como $a_{n+1}>a_n$ y $d\mid a_{n+1}$ nos queda que $a_{n+1}\geq 4d>4\times 2^{n-1}=2^{n+1}$.
Si $a_n=d\geq 2^n$ como $a_{n+1}>a_n$ y $d\mid a_{n+1}$ nos queda que $a_{n+1}\geq 2d\geq 2\times 2^n=2^{n+1}$.
Si $a_n=2d$ como $a_{n+1}>a_n$ y $d\mid a_{n+1}$, de ser $a_{n+1}\neq 3d$ nos queda que $a_{n+1}\geq 4d\geq 4\times 2^{n-1}=2^{n+1}$.

Si $a_n=2d$ y $a_{n+1}=3d$, como tenemos que $d>a_{n-1}\geq 2^{n-1}$, nos queda que
-Si $dcm(a_n,a_{n-1})\leq\frac{a_{n-1}}{3}<\frac{d}{3}$, como $dcm(a_n,a_{n-1})>a_{n-2}\geq 2^{n-2}$ obtenemos que $\frac{d}{3}>2^{n-2}\implies a_{n+1}=3d>9\times 2^{n-2}>8\times 2^{n-2}=2^{n+1}$.
-Si $dcm(a_n,a_{n-1})=\frac{a_{n-1}}{2}\implies\exists k\in N, k>4/\frac{a_{n-1}}{2}k=a_n=2d\implies a_{n-1}=\frac{4}{k}d$, si $k\neq 5$ (nos queda que $k\geq 6$), como $a_{n-1}\geq 2^{n-1}$ obtenemos que $d\geq\frac{k}{4}2^{n-1}\geq 3\times 2^{n-2}\implies a_{n+1}=3d\geq 9\times 2^{n-2}>8\times 2^{n-2}=2^{n+1}$.
Si $a_{n-1}=\frac{4}{5}d$, como $dcm(a_n,a_{n-1})=dcm(2d,\frac{4}{5}d)=\frac{2}{5}d>a_{n-2}$ nos queda que
+Si $a_{n-2}<\frac{3}{8}d$, como $a_{n-2}\geq 2^{n-2}$ obtenemos que $d>\frac{8}{3}2^{n-2}=\frac{2^{n+1}}{3}\implies a_{n+1}=3d>2^{n+1}$.
+Si $\frac{3}{8}d\leq a_{n-2}<\frac{2}{5}d$ tenemos que $dcm(a_{n-1},a_{n-2})\leq\frac{a_{n-2}}{2}$ (ya que no puede ser $dcm(a_{n-1},a_{n-2})=a_{n-2}$ porque $3a_{n-2}\geq\frac{9}{8}d>\frac{4}{5}d=a_{n-1}>2a_{n-2}$) así que $dcm(a_{n-1},a_{n-2})\leq\frac{a_{n-2}}{2}\leq\frac{1}{2}\frac{3}{8}d=\frac{3}{16}d$, y como $dcm(a_{n-1},a_{n-2})>a_{n-3}\geq 2^{n-3}$ obtenemos que $d>\frac{16}{3}2^{n-3}=\frac{2^{n+1}}{3}\implies a_{n+1}=3d>2^{n+1}$.
-Si $dcm(a_n,a_{n-1})=a_{n-1}\implies\exists k\in N, k>2/a_{n-1}k=a_n=2d\implies a_{n-1}=\frac{2}{k}d$, como $a_{n-1}\geq 2^{n-1}$ obtenemos que $d\geq\frac{k}{2}2^{n-1}\geq 3\times 2^{n-2}\implies a_{n+1}=3d\geq 9\times 2^{n-2}>8\times 2^{n-2}=2^{n+1}$.

De esta forma completamos el paso inductivo y concluimos que $a_n\geq 2^n$ $\forall n\in N_0$.
Responder