ItaMO 2007 Problema 5

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Alex89
Messaggi: 366
Iscritto il: 29 gen 2006, 16:57

ItaMO 2007 Problema 5

Messaggio da Alex89 » 15 mag 2007, 19:30

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

Avatar utente
giove
Messaggi: 519
Iscritto il: 22 mag 2006, 14:56
Località: Pisa / Brescia

Re: ItaMO 2007 Problema 5

Messaggio da giove » 15 mag 2007, 19:45

Alex89 ha scritto:Eccolo a voi... il + rognoso di tutti i problemi (almeno a mio parere...)
Questo era il problema più bello semmai! :twisted:

Alex89
Messaggi: 366
Iscritto il: 29 gen 2006, 16:57

Messaggio da Alex89 » 15 mag 2007, 20:12

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°...

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 15 mag 2007, 20:12

Troppo bello perchè nessuno l'avesse mai inventato :D

http://www.mathlinks.ro/Forum/viewtopic.php?p=109517

Avatar utente
EUCLA
Messaggi: 771
Iscritto il: 21 apr 2005, 19:20
Località: Prato

Messaggio da EUCLA » 15 mag 2007, 21:02

edriv ha scritto:Troppo bello perchè nessuno l'avesse mai inventato :D

http://www.mathlinks.ro/Forum/viewtopic.php?p=109517
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 :cry:

Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

Messaggio da salva90 » 15 mag 2007, 21:12

Faccio notare una cosa molto importante: in quello linkato da andrea si ha $ x_0=2 $, e non $ x_1=2 $


ACHTUNG!!!
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]

Avatar utente
Decan
Messaggi: 48
Iscritto il: 01 gen 1970, 01:00
Località: San Martino Valle Caudina (AV)
Contatta:

Messaggio da Decan » 15 mag 2007, 22:50

Madaaai!
"I' vo gridando: pace, pace, pace!" (F. Petrarca)
Presidente dell'EATO
Membro della Lega anti-Mickey Mouse 2

Avatar utente
giove
Messaggi: 519
Iscritto il: 22 mag 2006, 14:56
Località: Pisa / Brescia

Messaggio da giove » 16 mag 2007, 07:31

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...

Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

Messaggio da salva90 » 16 mag 2007, 20:38

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 :P
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]

Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

Messaggio da salva90 » 08 giu 2007, 13:31

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 $
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]

Avatar utente
giove
Messaggi: 519
Iscritto il: 22 mag 2006, 14:56
Località: Pisa / Brescia

Messaggio da giove » 08 giu 2007, 14:02

Penso 6 o 7, io non l'ho scritta troppo meglio :wink:

Rispondi