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
I codici di River (Coppa Gauss 2016)
Re: I codici di River (Coppa Gauss 2016)
$1246\approx\dfrac{\sqrt{5}-1}{2}*2016$ ?
Re: I codici di River (Coppa Gauss 2016)
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$.
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$.
Re: I codici di River (Coppa Gauss 2016)
È 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.