(IMO Shortlist 2008)
Sia data una sequenza infinita di interi positivi $ a_0,a_1,a_2,\ldots $ tale che $ \text{mcd}(a_{n+2},a_{n+1}) > a_n $ per ogni $ n \in \mathbb{N} $. Mostrare che $ a_n \ge 2^n $ per ogni $ n \in \mathbb{N} $.
mcd(a_{n+1},a_{n+2})>a_n per ogni n.
mcd(a_{n+1},a_{n+2})>a_n per ogni n.
The only goal of science is the honor of the human spirit.
-
exodd
- Messaggi: 728
- Iscritto il: 09 mar 2007, 19:46
- Località: sulle pendici della provincia più alta d'europa
notiamo innanzitutto che la sequenza è strettamente crescente
poniamo per assurdo che esista
$ a_n<2^n $
scopriamo che
$ mcd(a_{n-1},a_n)<2^{n-1} $
poichè, se
$ 2^{n-1}-1<mcd(a_{n-1},a_n)<2^n $
implicherebbe che
$ 2^{n-1}-1<a_{n-1}<2^n $
e
$ 2^n-1<x*2^{n-1}<=a_n $
assurdo
iterando il procedimento scopriamo che
$ mcd(a_i,a_{i+1})<2^i $
in particolare
$ mcd(a_1,a_2)=1<2 $
ma
$ a_0<mcd(a_1,a_2)=1 $
impossibile
poniamo per assurdo che esista
$ a_n<2^n $
scopriamo che
$ mcd(a_{n-1},a_n)<2^{n-1} $
poichè, se
$ 2^{n-1}-1<mcd(a_{n-1},a_n)<2^n $
implicherebbe che
$ 2^{n-1}-1<a_{n-1}<2^n $
e
$ 2^n-1<x*2^{n-1}<=a_n $
assurdo
iterando il procedimento scopriamo che
$ mcd(a_i,a_{i+1})<2^i $
in particolare
$ mcd(a_1,a_2)=1<2 $
ma
$ a_0<mcd(a_1,a_2)=1 $
impossibile
Tutto è possibile: L'impossibile richiede solo più tempo
in geometry, angles are angels
"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
ispiratore del BTAEvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
in geometry, angles are angels
"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"
@exodd: Uhm, il procedimento iniziale fa uso dell'ipotesi di assurdo. Non ho capito come fai a iterarlo. Non hai l'ipotesi di assurdo per tutti gli i ma solo per un certo i=n. Un piccolo suggerimento: il comando \ge produce il maggiore o uguale e il comando \le produce il minore o uguale (per esempio: $ 1\le 2 $).
Sotto ci sono i miei "aiutini" per la soluzione, se non vuoi leggerli non leggerli, odio postare in invisibile...
La mia idea per dimostrarlo era porre $ d_n=(a_n,a_{n+1}) $ e vedere che possiamo supporre che $ a_n=[d_n,d_{n-1}] $ senza perdita di generalità (perché?), dove le parentesi tonde sono il MCD e le quadre il mcm.
L'ipotesi diventa che $ d_n>[d_{n-1},d_{n-2}] $
Ora voglio dimostrare che $ a_n+(a_n,a_{n+1})\ge 2^{n+1} $ (che è più forte della tesi). Lo scrivo come $ [d_n,d_{n-1}]+d_n\ge 2^{n+1} $ e cerco di dimostrarlo per induzione (cioè voglio che $ [d_n,d_{n-1}]+d_n\ge 2[d_{n-1},d_{n-2}]+2d_{n-1} $ ). Hint: considerare $ d_n $ come variabile indipendente che rispetta la nostra ipotesi.
Sotto ci sono i miei "aiutini" per la soluzione, se non vuoi leggerli non leggerli, odio postare in invisibile...
La mia idea per dimostrarlo era porre $ d_n=(a_n,a_{n+1}) $ e vedere che possiamo supporre che $ a_n=[d_n,d_{n-1}] $ senza perdita di generalità (perché?), dove le parentesi tonde sono il MCD e le quadre il mcm.
L'ipotesi diventa che $ d_n>[d_{n-1},d_{n-2}] $
Ora voglio dimostrare che $ a_n+(a_n,a_{n+1})\ge 2^{n+1} $ (che è più forte della tesi). Lo scrivo come $ [d_n,d_{n-1}]+d_n\ge 2^{n+1} $ e cerco di dimostrarlo per induzione (cioè voglio che $ [d_n,d_{n-1}]+d_n\ge 2[d_{n-1},d_{n-2}]+2d_{n-1} $ ). Hint: considerare $ d_n $ come variabile indipendente che rispetta la nostra ipotesi.
"Sei la Barbara della situazione!" (Tap)