I en av oppgavene plutarco la ut som øving til Abelkonkurransen, skulle man finne ut om $1234567891011 \dots 9899100$ var delelig på 3. Hintet sa at hvis dette skulle være sant måtte tverrsummen være delelig på $3$. Jeg begynte å tenke over hvorfor det må være sånn, og tenkte på om følgende er bevis på hintet.
La oss si at vi har et fem-sifret tall $n$:
$n = a \cdot 10^4 + b \cdot 10^3 + c \cdot 10^2 + d \cdot 10^1 + e$
$n = a(9999 + 1) + b(999+1) + c(99+1) + d(9+1) + e$
$n = 9999a + 999b + 99c + 9d + a + b + c + d + e$.
Siden alle tall som skrives på formen $999$, $9999999$ osv har $3$ som faktor må alle slike tall være delelig på $3$ (de kan skrives som $3^2(10^n + 10^{n-1} + \dots + 10^0)$). I dette tilfellet får vi:
$n = 3(3333a + 333b + 33c + 3d) + a + b + c + d + e$
Hvis $n$ skal være delelig på $3$ må altså $a+b+c+d+e$ være delelig på $3$, slik at $3$ er en felles faktor for alle leddene i $n$.
Siden $a+b+c+d+e$ er tverrsummen betyr det altså at tverrsummen må være delelig på $3$. Dette stemmer for alle tall med $k$ siffer, da hver tierplass, hundrerplass, tusenplass, titusenplass osv. kan skrives på formen $10^m-1+1$.
Fungerer argumentasjonen, og kan man med samme argumentasjon også vise at hvis et tall er delelig på $9$, må også tverrsummen være delelig på $9$?
Divisjonsregler for 3 og 9
Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Det er helt riktig.
Påstandene er også bevist her https://artofproblemsolving.com/wiki/in ... nd_9_proof
Påstandene er også bevist her https://artofproblemsolving.com/wiki/in ... nd_9_proof
Okei - jeg tror jeg har noe som kan ligne på et bevis nå.
Jeg bruker lemmaen (muligens ikke helt rett ordbruk?) din om at $2^n \mid 10^m, \forall m \geq n$
La oss si at $N$ er et $6$-sifret tall, da har vi at:
$N = a \cdot 10^5 + b \cdot 10^4 + c \cdot 10^3 + d \cdot 10^2 + e \cdot 10 + f$
Hvis for eksempel $2 \mid f$, følger det også at $2 \mid 10, 10^2, \dots, 10^5$ av lemmaen.
Da vil alle følgende leddene i $N$ være delelig på $2$, da $10^m$ er en faktor i alle, og $m \geq 1$.
Hvis for eksempel $2^3 \mid d \cdot 10^2 + e \cdot 10 + f$, følger det også at $2^3 \mid 10^3, 10^4, 10^5$, og siden $10^3, 10^4, 10^5$ er faktorer i de neste kommende leddene i $N$ betyr det at $2^3 | a \cdot 10^5 + b \cdot 10^4 + c \cdot 10^3$.
Kan dette ligne på noe? Jeg sliter dog med å generalisere og å vise hvis og bare hvis-delen.
Jeg bruker lemmaen (muligens ikke helt rett ordbruk?) din om at $2^n \mid 10^m, \forall m \geq n$
La oss si at $N$ er et $6$-sifret tall, da har vi at:
$N = a \cdot 10^5 + b \cdot 10^4 + c \cdot 10^3 + d \cdot 10^2 + e \cdot 10 + f$
Hvis for eksempel $2 \mid f$, følger det også at $2 \mid 10, 10^2, \dots, 10^5$ av lemmaen.
Da vil alle følgende leddene i $N$ være delelig på $2$, da $10^m$ er en faktor i alle, og $m \geq 1$.
Hvis for eksempel $2^3 \mid d \cdot 10^2 + e \cdot 10 + f$, følger det også at $2^3 \mid 10^3, 10^4, 10^5$, og siden $10^3, 10^4, 10^5$ er faktorer i de neste kommende leddene i $N$ betyr det at $2^3 | a \cdot 10^5 + b \cdot 10^4 + c \cdot 10^3$.
Kan dette ligne på noe? Jeg sliter dog med å generalisere og å vise hvis og bare hvis-delen.
Helt rett det du skriver ja. Vi kan generalisere på følgende måte:
Skriv $N=\sum_{i=0}^m a_i 10^{i}$.
$\Rightarrow$: Anta at $2^n$ deler $N$ der $0<n\leq m$ (tilfellene $n=0$ og $n=m+1$ er trivielle). Siden $2^n$ deler $10^i$ for alle $i\geq n$, så vil $2^n$ dele $\sum_{i=n}^ma_i 10^i$ og dermed også $N-\sum_{i=n}^ma_i 10^i=\sum_{i=0}^{n-1} a_i 10^i$.
$\Leftarrow$: Anta at $2^n$ deler de $n$ siste sifrene, $\sum_{i=0}^{n-1} a_i 10^i$. Da vil $2^n$ dele $\sum_{i=n}^ma_i 10^i + \sum_{i=0}^{n-1} a_i 10^i = N$.
PS: Det samme vil jo funke med $5^n$ istedet for $2^n$
Skriv $N=\sum_{i=0}^m a_i 10^{i}$.
$\Rightarrow$: Anta at $2^n$ deler $N$ der $0<n\leq m$ (tilfellene $n=0$ og $n=m+1$ er trivielle). Siden $2^n$ deler $10^i$ for alle $i\geq n$, så vil $2^n$ dele $\sum_{i=n}^ma_i 10^i$ og dermed også $N-\sum_{i=n}^ma_i 10^i=\sum_{i=0}^{n-1} a_i 10^i$.
$\Leftarrow$: Anta at $2^n$ deler de $n$ siste sifrene, $\sum_{i=0}^{n-1} a_i 10^i$. Da vil $2^n$ dele $\sum_{i=n}^ma_i 10^i + \sum_{i=0}^{n-1} a_i 10^i = N$.
PS: Det samme vil jo funke med $5^n$ istedet for $2^n$
Takker for generaliseringen! 
Det vil også funke med $5^n$ fordi $10^n = 5^n \cdot 2^n$?
Og til hvis og bare hvis-delen: Hvis $2^n$ ikke deler de $n$ siste siffene, impliserer det nødvendigvis til at $N$ ikke er delelig med $2^n$? Beklager hvis jeg spør dumt, men er ikke så veldig god på bevis.
Det vil også funke med $5^n$ fordi $10^n = 5^n \cdot 2^n$?
Og til hvis og bare hvis-delen: Hvis $2^n$ ikke deler de $n$ siste siffene, impliserer det nødvendigvis til at $N$ ikke er delelig med $2^n$? Beklager hvis jeg spør dumt, men er ikke så veldig god på bevis.
- Det stemmer!
- Tenk Venn-diagram i slike tilfeller. A,B er to sirkler som representerer to utsagn. Implikasjonen $A \Rightarrow B$ betyr at sirkel A ligger inni sirkel B. $B \Rightarrow A$ betyr at sirkel B ligger inni A. $A \Leftrightarrow B$, som er det samme som hvis og bare hvis, betyr at sirkel A og B overlapper perfekt.
- Tenk Venn-diagram i slike tilfeller. A,B er to sirkler som representerer to utsagn. Implikasjonen $A \Rightarrow B$ betyr at sirkel A ligger inni sirkel B. $B \Rightarrow A$ betyr at sirkel B ligger inni A. $A \Leftrightarrow B$, som er det samme som hvis og bare hvis, betyr at sirkel A og B overlapper perfekt.
Det var en veldig fin måte å fremstille det på. Det oppklarte det, tusen takk!Gustav wrote:- Det stemmer!
- Tenk Venn-diagram i slike tilfeller. A,B er to sirkler som representerer to utsagn. Implikasjonen $A \Rightarrow B$ betyr at sirkel A ligger inni sirkel B. $B \Rightarrow A$ betyr at sirkel B ligger inni A. $A \Leftrightarrow B$, som er det samme som hvis og bare hvis, betyr at sirkel A og B overlapper perfekt.