Eccolo a voi... il + rognoso di tutti i problemi (almeno a mio parere...)
Non so in quanti l'abbiano (o meglio abbiamo) sbagliato, cmq ecco la traccia...
Sia data la successione:
$ x_1=2 $
$ x_(n+1)=2x_n^2-1 $
Dimostrare che $ n $ e $ x_n $ sono relativamente primi
ItaMO 2007 Problema 5
Re: ItaMO 2007 Problema 5
Questo era il problema più bello semmai!Alex89 ha scritto:Eccolo a voi... il + rognoso di tutti i problemi (almeno a mio parere...)
Troppo bello perchè nessuno l'avesse mai inventato 
http://www.mathlinks.ro/Forum/viewtopic.php?p=109517
http://www.mathlinks.ro/Forum/viewtopic.php?p=109517
no questo non me lo dovevi dire...edriv ha scritto:Troppo bello perchè nessuno l'avesse mai inventato
http://www.mathlinks.ro/Forum/viewtopic.php?p=109517
e io che ho perso un sacco di tempo per poi concludere con una dimostrazione ci sta anche sbagliata che la tesi era vera per le potenze del 2...lasciamo stare va
Ok, dopo la stronzata che ho detto mi rendo conto che in effetti perchè la tesi è vera per$ x_1=k $ , con $ k $ intero positivo qualsiasi... Non viene mai usato nella dimostrazione il fatto che $ x_1=2 $
Dai su, qualcuno ci provi che è bellino
Dai su, qualcuno ci provi che è bellino
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]
Visto che:
-a Cesenatico non l'ho risolto
- le soluzioni loro non le ho lette
- Nico ha tentato di spiegarmelo ma erano le due di notte e non ci ho capito na sega
ritengo di poter provare a scrivere una soluzione, visto che non se lo caga nessuno, soprattutto perchè devo imparare a scrivere come si deve le soluzioni.
La prima cosa da fare è considerare la sequenza modulo un qualsiasi primo $ ~p_k $.
E' chiaro che se due termini sono congrui tra loro modulo $ ~p_k $ , diciamo $ ~x_i $ e $ ~x_j $ (con i<j) allora si avrà $ x_{j+1}\equiv x_{i+1}\bmod p_k $ e cosi via; tutti i termini tra $ ~x_i $ (compreso) e $ ~x_j $(escluso) si ripetono quindi periodicamente. Segue che la successione, dopo al massimo $ p_k $ termini, è periodica modulo $ ~p_k $ (in quanto con $ p_k+1 $ termini ve ne saranno per il principio dei cassetti due congrui tra loro). Inoltre se un termine della successione è divisibile per $ p_k $, quello successivo è -1 e tutti i seguenti sono 1 $ \bmod p_k $. Questo significa che lo 0 non compare nel periodo.
Da ciò segue che, se esistesse un certo $ ~x_n $ tale che $ p_k|n, ~p_k|x_n $, dovrebbe essere $ n=p_k $. Inoltre tutti gli $ ~x_i $ con $ i<p_k $ dovrebbero rappresentare tutte le classi possibili (zero escluso) $ \bmod p_k $, altrimenti due sarebbero congrui tra loro e la successione risulterebbe già periodica. Ma in questo caso uno di essi deve essere 1 $ \bmod p_k $, e quindi tutti i successivi sono 1 (induzione). Da ciò segue che $ p_k\notvert x_{p_k} $. Di conseguenza si ha la tesi.
Ora la domanda è una: con una dimostrazione scritta così a cane quanti punti avrei preso/perso a Cese?
NOTA: non è mai stato usato il fatto che $ x_1=2 $
-a Cesenatico non l'ho risolto
- le soluzioni loro non le ho lette
- Nico ha tentato di spiegarmelo ma erano le due di notte e non ci ho capito na sega
ritengo di poter provare a scrivere una soluzione, visto che non se lo caga nessuno, soprattutto perchè devo imparare a scrivere come si deve le soluzioni.
La prima cosa da fare è considerare la sequenza modulo un qualsiasi primo $ ~p_k $.
E' chiaro che se due termini sono congrui tra loro modulo $ ~p_k $ , diciamo $ ~x_i $ e $ ~x_j $ (con i<j) allora si avrà $ x_{j+1}\equiv x_{i+1}\bmod p_k $ e cosi via; tutti i termini tra $ ~x_i $ (compreso) e $ ~x_j $(escluso) si ripetono quindi periodicamente. Segue che la successione, dopo al massimo $ p_k $ termini, è periodica modulo $ ~p_k $ (in quanto con $ p_k+1 $ termini ve ne saranno per il principio dei cassetti due congrui tra loro). Inoltre se un termine della successione è divisibile per $ p_k $, quello successivo è -1 e tutti i seguenti sono 1 $ \bmod p_k $. Questo significa che lo 0 non compare nel periodo.
Da ciò segue che, se esistesse un certo $ ~x_n $ tale che $ p_k|n, ~p_k|x_n $, dovrebbe essere $ n=p_k $. Inoltre tutti gli $ ~x_i $ con $ i<p_k $ dovrebbero rappresentare tutte le classi possibili (zero escluso) $ \bmod p_k $, altrimenti due sarebbero congrui tra loro e la successione risulterebbe già periodica. Ma in questo caso uno di essi deve essere 1 $ \bmod p_k $, e quindi tutti i successivi sono 1 (induzione). Da ciò segue che $ p_k\notvert x_{p_k} $. Di conseguenza si ha la tesi.
Ora la domanda è una: con una dimostrazione scritta così a cane quanti punti avrei preso/perso a Cese?
NOTA: non è mai stato usato il fatto che $ x_1=2 $
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]
