Siste siffer i et tall.

Her kan du stille spørsmål vedrørende problemer og oppgaver i matematikk for videregående skole og oppover på høyskolenivå. Alle som føler trangen er velkommen til å svare.

Moderatorer: Aleks855, Gustav, Nebuchadnezzar, Janhaa, DennisChristensen, Emilga

DennisChristensen
Grothendieck
Grothendieck
Innlegg: 826
Registrert: 09/02-2015 23:28
Sted: Oslo

Gjest skrev:Enda en oppgave som på første øyekast virker umulig for meg:

Dersom [tex]a_0=0[/tex], [tex]a_1=1[/tex] og [tex]a_n=3a_{n-1}-2a_{n-2}[/tex] for [tex]n\geq 2[/tex]. Hva er siste siffer i [tex]a_{2014}[/tex].

Prøvde å først finne den eksplisitte formelen ut i fra den rekursive, men det gikk ikke. Vet at for å gå fra eksplisitt til rekursiv så regner man ut [tex]a_n-a_{n-1}[/tex].

[tex]a_n-a_{n-1}=3a_{n-1}-2a_{n-2 }\Rightarrow a_n=4a_{n-1}-2a_{n-2}[/tex] går ikke..

Prøve å angripe oppgaven annerledes da.

[tex]a_2=3a_{2-1}-2a_{2-2}=3a_1-2a_0=3*1-2*0=3[/tex]

[tex]a_3=3a_{3-1}-2a_{3-2}=3*3-2*1=7[/tex]

[tex]a_4=3a_{4-1}-2a_{4-2}=3*7-2*3=15[/tex]

Virker ikke som det er et lett gjennkjennelig møsnter her [tex]\left \{ a_0,a_1,a_2,a_3,a_4 \right \}\Rightarrow \left \{ 0,1,3,7,15 \right \}[/tex].

Uten at differansen mellom hvert ledd er et kvadrat tall? [tex]2^0,2^1,2^2,2^3...2^n..2^{n-1}[/tex] ? Vet ikke hva jeg skal jeg gjøre med denne informasjonen.

[tex]2014[/tex] er jo et partall så kanskje jeg burde uttrykke leddet på formen [tex]2n\pm 1[/tex]?

Siste siffer er vel kun avhengig av det siste sifferet i produktet av de siste sifrene i tallet, altså i [tex]a_{n-1}[/tex] og [tex]a_{n-2}[/tex] ?
Vi observerer at $$a_0 \equiv 0 \text{ }(\text{mod }10);$$ $$a_1 \equiv 1\text{ }(\text{mod }10);$$ $$ a_2 \equiv 3\text{ }(\text{mod }10);$$ $$a_3 \equiv 7\text{ }(\text{mod }10);$$ $$a_4 \equiv 5\text{ }(\text{mod }10);$$ $$a_5 \equiv 1\text{ }(\text{mod }10);$$ $$a_6 \equiv 3\text{ }(\text{mod }10).$$ Dermed vil denne syklusen gjenta seg ettersom $a_1, a_5$ og $a_2, a_6$ har samme siste siffer, henholdsvis. Ettersom $2014 = 2 + 4\cdot 503$ har vi altså at $a_{2014} \equiv a_2\text{ }(\text{mod }10);$, så siste siffer til $a_{2014}$ er lik $3$.
Gjest

DennisChristensen skrev: Vi observerer at $$a_0 \equiv 0 \text{ }(\text{mod }10);$$ $$a_1 \equiv 1\text{ }(\text{mod }10);$$ $$ a_2 \equiv 3\text{ }(\text{mod }10);$$ $$a_3 \equiv 7\text{ }(\text{mod }10);$$ $$a_4 \equiv 5\text{ }(\text{mod }10);$$ $$a_5 \equiv 1\text{ }(\text{mod }10);$$ $$a_6 \equiv 3\text{ }(\text{mod }10).$$ Dermed vil denne syklusen gjenta seg ettersom $a_1, a_5$ og $a_2, a_6$ har samme siste siffer, henholdsvis. Ettersom $2014 = 2 + 4\cdot 503$ har vi altså at $a_{2014} \equiv a_2\text{ }(\text{mod }10);$, så siste siffer til $a_{2014}$ er lik $3$.

Takk! Jeg var visst på bærtur.
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Bare for å være presis; hva er argumentet for at syklusen fortsetter 1, 3, 7, 5, 1, 3, 7, 5...?
Bilde
DennisChristensen
Grothendieck
Grothendieck
Innlegg: 826
Registrert: 09/02-2015 23:28
Sted: Oslo

Aleks855 skrev:Bare for å være presis; hva er argumentet for at syklusen fortsetter 1, 3, 7, 5, 1, 3, 7, 5...?
Ettersom det rekursive uttrykket kun er en lineær kombinasjon av tidligere ledd i følgen, vil et gitt ledd (mod 10) være entydig bestemt av de to forrige leddene (mod 10). Dette følger enkelt fra regneregler for modulær aritmetikk.
Svar