matematikk.net

Finn de tre siste sifrene i produktet 1·3·5·7·...·2009·2011

(vis en metode uten bruk av pc/kalkulator)

(oppgaven er fra finalen i Abelkonkurransen 2011)

Dette ble noe svineri, men:

Kaller tallet for N. Har at [tex]1 \cdot 3 \cdots 2011 \equiv (1 \cdot 3 \cdot 5 \cdot 7 \cdot 9)^{201} \equiv (1 \cdot 3 \cdot 5 \cdot (-3) \cdot (-1))^{201} \equiv (-5)^{201} \equiv 5 \ (\text{mod} \ 10)[/tex], så siste siffer er 5.

Videre er [tex]\frac{N-5}{10} = \frac{5(1 \cdot 3 \cdot 7 \cdot 9 \cdots 2011 - 1)}{10} = \frac{1 \cdot 3 \cdot 7 \cdots 2011 - 1}{2}[/tex]

Ser på telleren modulo 10. Her får vi [tex]1 \cdot 3 \cdot 7 \cdots 2011 - 1 \equiv (1 \cdot 3 \cdot 7 \cdot 9) \cdot 5^{200} - 1 \equiv -5-1 = -6 \equiv 4 \ (\text{mod} 10)[/tex], så siste siffer i telleren er 4. Når vi deler et slikt tall på 2 blir siste siffer i tallet enten 2 eller 7 (siden [tex]\frac{10k + 4}{2} = 5k+2[/tex] enten er kongruent med 2 modulo 10, hvis k er et partall, og kongruent med 5 + 2 = 7 hvis k er et oddetall). Så det nest siste sifferet i N er altså 2 eller 7. Vi har at [tex]1 \cdot 3 \cdot 7 \cdot 9 \cdots 2011 - 1 \equiv 1 \cdot (-1) \cdot (-1) \cdot 1 \cdot (-1) \cdots (-1) \equiv 2 \ (\text{mod} \ 4)[/tex]. Det gir at [tex]\frac{1 \cdot 3 \cdot 7 \cdot 9 \cdots 2011 - 1}{2}[/tex] er et oddetall, og kan ikke ha 2 som siste siffer. Det nest siste sifferet er altså 7.

Prosedyren gjentas igjen (dvs. trekker fra resten og deler på 10). Vi får da [tex]\frac{\frac{1 \cdot 3 \cdot 7 \cdots 2011 - 1}{2} - 7}{10} = \frac{1 \cdot 3^2 \cdot 7 \cdot 9 \cdot 11 \cdot 13 \cdot 17 \cdots 2011 - 3}{4}[/tex]. Nå blir telleren kongruent med 2 modulo 10. Når vi deler et slikt tall på 4 blir siste siffer enten 3 eller 8. På samme måte får vi her at hvis tallet går opp i 8 blir siste siffer 8, og hvis ikke blir det 3. Vi får her at [tex]1 \cdot 3^2 \cdot 7 \cdot 9 \cdot 11 \cdot 13 \cdot 17 \cdots 2011 - 3 \equiv 1 \cdot 1 \cdot (-1) \cdot 1 \cdot 3 \cdot (-3) \cdot (1 \cdot 3 \cdot (-3) \cdot 1)^{498} \cdot 1 \cdot 3 - 3 \equiv 3 - 3 = 0 \ (\text{mod} \ 8)[/tex]. Da er det tredje siste sifferet altså 8.

For å konkludere blir de tre siste sifrene 875.

Ser fint ut!

Gjorde det litt mer kompakt på en linje, men kan vente med å legge ut min løsning.

Var i finalen med denne oppgaven. Løsningen min var ikke særlig fin.

Så på produktet mod 1000, la til side 2001*2003*2005*2007*2009*2011
og klappet resten sammen til:
[tex](1*3*5*...*499)^4 mod 1000[/tex]
Hvilket må ende på 625:
[tex](10a + 5)**4=10^4a^4 + 2*10^4a^3 + 15*10^3a^2 + 5*10^3a + 625[/tex]

Deretter ganget jeg sammen 625 med tallene jeg la til siden i starten. Og sjekket de tre siste sifrene, hvilket er den langt mindre elegante delen...

Hadde en lignende fremgangsmåte som Brahmagupta, men fant ut at

[tex]5^4(2n+1)^2-5^4=5^4(4n^2+4n)\equiv 0\,mod(1000)[/tex]

, og tallet kan da skrives på formen [tex]5^4(2n+1)^2*11*9*7*5*3\equiv 5^4*11*...*3[/tex] mod 1000,

For øvrig er vel Vektormannens metode i prinsippet mer elegant, ja:)

Den løsningen som ble presentert i etterkant av konkurransen gikk ut på å vise at de 3 siste sifrene må dele 125, siden 1000 deler 125, hvilket gir 4 muligheter 125, 375, 625, 875, og deretter vise at kun en av disse er kongruent med produktet mod 8.

Synes den var ganske grei