I codici di River (Coppa Gauss 2016)

Problematiche legate al funzionamento di questo forum o del sito OliMaTO.
Rispondi
Benny140
Messaggi: 40
Iscritto il: 23/11/2016, 18:13

I codici di River (Coppa Gauss 2016)

Messaggio da Benny140 »

Indagando per scoprire il codice di accesso alla stanza di comando di Miranda, River ha dapprima scoperto che tale codice è collegato a due numeri interi positivi [tex]a[/tex] e [tex]b[/tex] e ad elenchi di numeri positivi ottenuti secondo le regole seguenti:

[tex]A_{0} = a[/tex] [tex]A_{1} = b[/tex] [tex]A_{n+2} = A_{n} - A_{n+1}[/tex]


cioè, se [tex]A_{k}[/tex] non è positivo, l'elenco termina e [tex]A_{k}[/tex] non viene scritto. River ha anche scoperto che [tex]a[/tex] è 2016 e [tex]b[/tex] rende massimo il numero di termini dell'elenco. Quanto vale [tex]b[/tex]?

Ho trovato questo problema nella coppa gauss dell'anno scorso, ma non ho capito l'ultima parte della soluzione: me la potreste spiegare?

Grazie
Salvador
Messaggi: 266
Iscritto il: 26/11/2016, 11:55

Re: I codici di River (Coppa Gauss 2016)

Messaggio da Salvador »

$1246\approx\dfrac{\sqrt{5}-1}{2}*2016$ ?
Salvador
Messaggi: 266
Iscritto il: 26/11/2016, 11:55

Re: I codici di River (Coppa Gauss 2016)

Messaggio da Salvador »

Non so quale sia la soluzione che hai visto.
Io prima induttivamente trovo che i numeri della successione si alternano nelle forme $ka-hb$ e $ub-va$, dove $k,h,u,v$ sono interi non negativi, poi trovo di nuovo induttivamente che questi sono i numeri di Fibonacci e vado a scrivere $b>F_{n-1}/F_{n}$ e $b<F_{n}/F_{n+1}$ per ogni n. Arrivato a 34, trovo $b>21/34*2016=1245,176...$ e $b<34/55*2016=1246,254...$ e $55/89*2016=1245,842...$, da cui deduco $b=1246$.
afullo
Messaggi: 2030
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: I codici di River (Coppa Gauss 2016)

Messaggio da afullo »

È più o meno la dimostrazione che l'algoritmo di Euclide per la determinazione di [tex]MCD(a,b)[/tex], se [tex]a > b[/tex], termina in al più [tex]\dfrac{\ln a}{\ln \phi}[/tex] passi. ;)
Rispondi