Pagina 1 di 1
ItaMO 2007 Problema 5
Inviato: 15 mag 2007, 19:30
da Alex89
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
Re: ItaMO 2007 Problema 5
Inviato: 15 mag 2007, 19:45
da giove
Alex89 ha scritto:Eccolo a voi... il + rognoso di tutti i problemi (almeno a mio parere...)
Questo era il problema più bello semmai!
Inviato: 15 mag 2007, 20:12
da Alex89
Bello era bello... però durante la gara nn sono riuscito a venirne a capo e ci ho perso 2 orette buone come risultato... magari in quel tempo mi sarei pure accorto di aver sbagliato il 4°...
Inviato: 15 mag 2007, 20:12
da edriv
Inviato: 15 mag 2007, 21:02
da EUCLA
no questo non me lo dovevi dire...
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
Inviato: 15 mag 2007, 21:12
da salva90
Faccio notare una cosa molto importante: in quello linkato da andrea si ha $ x_0=2 $, e non $ x_1=2 $
ACHTUNG!!!
Inviato: 15 mag 2007, 22:50
da Decan
Madaaai!
Inviato: 16 mag 2007, 07:31
da giove
salva90 ha scritto:Faccio notare una cosa molto importante: in quello linkato da andrea si ha $ x_0=2 $, e non $ x_1=2 $
ACHTUNG!!!
Penso che più o meno la soluzione sia la stessa... Tanto anche se $ x_1=7 $ il ragionamento dovrebbe essere uguale...
Inviato: 16 mag 2007, 20:38
da salva90
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
Inviato: 08 giu 2007, 13:31
da salva90
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 $
Inviato: 08 giu 2007, 14:02
da giove
Penso 6 o 7, io non l'ho scritta troppo meglio
