La specie più intelligente

Home Forum Matematica Teoria dei numeri La specie più intelligente

Questo argomento contiene 4 risposte, ha 3 partecipanti, ed è stato aggiornato da MATHia MATHia 1 mese fa.

Stai vedendo 5 articoli - dal 1 a 5 (di 5 totali)
  • Autore
    Articoli
  • #19746
    MATHia
    MATHia
    Amministratore del forum

    Gli umani sono la specie più intelligente del pianeta Terra, dopo i delfini e i topi. Difatti, data una successione tale che $a_0=1$, $a_1=2$ e $a_n=a_{n-1}+12a_{n-2}$ per ogni $n\ge 2$, i topi sanno calcolare immediatamente quanto vale $a_{2016}+3a_{2015}. Gli umani invece possono al massimo determinare le ultime tre cifre di questo numero. Quali sono queste ultime tre cifre?

    #19754

    Jacoπo
    Partecipante
    Spoiler

    Si può esprimere il termine generale $x_n$ come segue:
    $x_n=\frac{2}{7}\cdot (-3)^n+\frac{5}{7}\cdot 4^n$
    dove $-3$ e $4$ sono le soluzioni di $x^2-x-12=0$ e $(\frac{2}{7},\frac{5}{7})$ è soluzione del sistema
    $\left{\begin{matrix}
    1=a+b & \
    2=-3a+4b &
    \end{matrix}\right.$
    Quindi $a_{2016}+3a_{2015}=\frac{2}{7}\cdot(-3)^{2016}+\frac{5}{7}\cdot 4^{2016}+3(\frac{2}{7}\cdot (-3)^{2015}+\frac{5}{7}\cdot 4^{2015})=(-3)^{2015}\cdot (\frac{2}{7}\cdot (-3+3))+4^{2015}\cdot (\frac{5}{7}\cdot (4+3))=5\cdot 4^{2015}$
    E per le ultime tre cifre: $4^{2015}\cdot 5\equiv 4^{15}\cdot 5\equiv 824\cdot 5\equiv 120\; mod 1000$

    [collapse]
    #19755

    Jacoπo
    Partecipante
    Spoiler

    Si può esprimere il termine generale $x_n$ come segue:
    $x_n=\frac{2}{7}\cdot (-3)^n+\frac{5}{7}\cdot 4^n$
    dove $-3$ e $4$ sono le soluzioni di $x^2-x-12=0$ e $(\frac{2}{7},\frac{5}{7})$ è soluzione del sistema
    $\left{\begin{matrix} 1=a+b & \ 2=-3a+4b & \end{matrix}\right.$
    Quindi $a_{2016}+3a_{2015}=\frac{2}{7}\cdot(-3)^{2016}+\frac{5}{7}\cdot 4^{2016}+3(\frac{2}{7}\cdot (-3)^{2015}+\frac{5}{7}\cdot 4^{2015})=(-3)^{2015}\cdot (\frac{2}{7}\cdot (-3+3))+4^{2015}\cdot (\frac{5}{7}\cdot (4+3))=5\cdot 4^{2015}$
    E per le ultime tre cifre: $4^{2015}\cdot 5\equiv 4^{15}\cdot 5\equiv 824\cdot 5\equiv 120\; mod 1000$

    [collapse]
    #19841
    Meceulero
    Meceulero
    Partecipante
    Spoiler

    noto che $$d_n:= a_{n}+3a_{n-1}=a_{n-1}+12a_{n-2}+3a_{n-1}=4d_{n-1}$$ quindi $$d_{2016}=4^{2015}d_1=4^{2015}(2+3)=2^{4029} \cdot 10$$ quindi l’ultima sua cifra sarà uno zero. Per scoprire le altre due cifre bisogna guardare $2^{4029}$ modulo $100$. Noto che $2^2$ è congruo a $2^{22}$ modulo $100$ quindi la congruenza modulo 100 delle potenze di 2 dal 4 in poi si ripete con ciclo lungo 20. Dato che $4029\equiv 9$ modulo $20$ allora $$2^{4029}\equiv 2^9 \equiv 12$$ modulo 100, quindi le ultime tre cifre di $d_{2016}$ sono $120$

    [collapse]
    #19843
    MATHia
    MATHia
    Amministratore del forum

    Corrette entrambe (scusa jacopo, ci ho messo un po’ a rispondere 🙂 )

    @meceulero: un’osservazione soltanto

    Spoiler

    hai trovato a mano la congruenza $2^2\equiv 2^{22}\pmod{100}$? Se la risposta è sì, non è un dramma, però forse potrebbe esserti utile un’occhiata alle Schede Olimpiche N10, riguardo al massimo ordine moltiplicativo.

    [collapse]
Stai vedendo 5 articoli - dal 1 a 5 (di 5 totali)

Devi essere loggato per rispondere a questa discussione.