Skulle jeg levert inn dette til en Abelfinale ville jeg ført et litt mer nøyktig bevis, men her er tegninga:
Oddetallene er gitt ved [tex]o_n = 2n+1[/tex]. Dette kan skrives som [tex]o_n = n^2 + 2n + 1 - n^2 = (n+1)^2 - n^2[/tex], og vi har vist første del.
Vi skal nå vise at følgen vi ønsker eksisterer, ved å vise hvordan en kan konstrueres.
La [tex]a_1[/tex] være odde (f.eks. 3). Da er [tex]a_1^2[/tex] også odde, og vi kan som vi ser over finne tall slik at
[tex]a_1^2 = n_1^2 - a_2^2 \\ a_1^2 + a_2^2 = n_1^2[/tex]
Siden et hvert kvadrattall er kongruent til 0 eller 1 modulo 4, må [tex]a_2^2[/tex] være partallig og [tex]n_1^2[/tex] være odde.
Dette betyr at vi kan gjenta prosessen:
[tex]n_1^2 = n_2^2-a_3^2 \\ a_1^2 + a_2^2 + a_3^2 = n_2^2[/tex]
og som vi ser, gjeder det samme her. Denne prosessen kan fortsette indefinitt, og en følge kan konstrueres.
Eksempelvis, dersom vi starter med 3, får vi følgen {3, 4, 12, 84, 3612, ...)
Julenøttstafett
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
La oss ta fram en oppgave som kan løses med grafteori (men som ikke krever det, selvfølgelig.) Også fra en Abelfinale:
Nøtt 34
I en gruppe på 20 personer sender hver person på et tidspunkt brev til 10 av de andre. Vis at det da finnes 2 personer som sender brev til hverandre.
Nøtt 34
I en gruppe på 20 personer sender hver person på et tidspunkt brev til 10 av de andre. Vis at det da finnes 2 personer som sender brev til hverandre.
Løser den med grafteori. For en kort og fin representasjon se daofeishis innlegg her i denne tråden på side 4!
La grafen G representere hver person som en node, og at et brev som sendes for en kant mellom to noder.
Siden hver person sender 10 brev, betyr det at det finnes [tex]10 \cdot 20 = 200[/tex] brev som sendes. Altså at antall kanter i grafen G er 200. Ved duehullprinsippet eksisterer det da minst én node som har en grad på 20 eller mer. Dette betyr at det finnes minst én person som sender eller mottar 20 brev eller mer.
Anta at ingen personer sender til hverandre. (EDIT: Det vil si at ingen personer sender et brev, og mottar et brev fra den samme personen) Det vil si at det ikke eksisterer et par med noder som har to kanter mellom seg. Men hver node har 19 muligheter for en kant mellom andre noder. Det betyr at det ikke eksisterer en node med en grad over 19. Men siden vi har vist at det eksisterer minst én node med en grad på 20 eller mer, har vi oppnådd en motsigelse. Da kan vi konkludere med at det eksisterer minst én node med to kanter til en annen, og derfor at det eksisterer to personer som sender til hverandre.
Nøtt nr 35:
Vis at hvis ni av de tolv første positive heltallene er tilfeldig plukket ut, så inneholder utplukkingen minst tre par slik at summen til disse er tretten.
La grafen G representere hver person som en node, og at et brev som sendes for en kant mellom to noder.
Siden hver person sender 10 brev, betyr det at det finnes [tex]10 \cdot 20 = 200[/tex] brev som sendes. Altså at antall kanter i grafen G er 200. Ved duehullprinsippet eksisterer det da minst én node som har en grad på 20 eller mer. Dette betyr at det finnes minst én person som sender eller mottar 20 brev eller mer.
Anta at ingen personer sender til hverandre. (EDIT: Det vil si at ingen personer sender et brev, og mottar et brev fra den samme personen) Det vil si at det ikke eksisterer et par med noder som har to kanter mellom seg. Men hver node har 19 muligheter for en kant mellom andre noder. Det betyr at det ikke eksisterer en node med en grad over 19. Men siden vi har vist at det eksisterer minst én node med en grad på 20 eller mer, har vi oppnådd en motsigelse. Da kan vi konkludere med at det eksisterer minst én node med to kanter til en annen, og derfor at det eksisterer to personer som sender til hverandre.
Nøtt nr 35:
Vis at hvis ni av de tolv første positive heltallene er tilfeldig plukket ut, så inneholder utplukkingen minst tre par slik at summen til disse er tretten.
-
Matematikkk
- Cayley
- Innlegg: 88
- Registrert: 21/07-2004 22:01
- Sted: Trondheim
Vi ser at blandt talla frå 1 til 12 så finnes det 6 par som tilsammen blir 13. 1+12, 2+11..osv. Vi skal velge ut 9, eller sagt på en anna måte, ta bort 3 av dei 12 tala. Når vi tar bort 3 tall, vil minst tre slike heile par stå igjen.
Nøtt nr 36:
Hva er det minste positive heltall x slik at summen x+2x+3x+...+99x er et kvadrattall.
Nøtt nr 36:
Hva er det minste positive heltall x slik at summen x+2x+3x+...+99x er et kvadrattall.
[tex]x+2x + 3x + \cdots + 99x = x\cdot\frac{(99+1)\cdot 99}{2} = 4950x = 495\cdot 10 x = 2\cdot 5^2\cdot 3^2\cdot 11 x[/tex]
Dermed må minste være [tex]x=11\cdot 2 = 22[/tex]
37
Bestem mulige verdier av [tex]x + \frac{1}{x}[/tex], der [tex]x[/tex] tilfredstiller [tex]x^4 + 5x^3 - 4x^2 + 5x + 1 = 0[/tex], og løs denne ligningen.
(x reell)
Dermed må minste være [tex]x=11\cdot 2 = 22[/tex]
37
Bestem mulige verdier av [tex]x + \frac{1}{x}[/tex], der [tex]x[/tex] tilfredstiller [tex]x^4 + 5x^3 - 4x^2 + 5x + 1 = 0[/tex], og løs denne ligningen.
(x reell)
La [tex]u = x + \frac 1 x[/tex]
Vi skriver om likningen:
[tex]x^4+5x^3-4x^2+5x+1=0 \\ x^2 + 5x -4 + \frac 5 x + \frac{1}{x^2} = 0 \\ (x + \frac 1 x)^2 + 5(x + \frac 1 x) - 6 = 0 \\ u^2 + 5u - 6 = 0 \\ (u - 1)(u + 6)=0[/tex]
Dette gir at
[tex]x + \frac 1 x = 1[/tex] eller [tex]x + \frac 1 x = -6[/tex]
Dersom x er reell, ser vi at eneste mulighet er [tex]x + \frac 1 x = -6[/tex], siden den andre løsningen gir opphav til en ikke-reduserbar annengradslikning.
Nøtt 38
Forenkle:
[tex]\left( 1 + \frac{1}{a}\right)\left( 1 + \frac{1}{a^2}\right) \left( 1 + \frac{1}{a^4}\right)...\left( 1 + \frac{1}{a^{2^{100}}}\right)[/tex]
Vi skriver om likningen:
[tex]x^4+5x^3-4x^2+5x+1=0 \\ x^2 + 5x -4 + \frac 5 x + \frac{1}{x^2} = 0 \\ (x + \frac 1 x)^2 + 5(x + \frac 1 x) - 6 = 0 \\ u^2 + 5u - 6 = 0 \\ (u - 1)(u + 6)=0[/tex]
Dette gir at
[tex]x + \frac 1 x = 1[/tex] eller [tex]x + \frac 1 x = -6[/tex]
Dersom x er reell, ser vi at eneste mulighet er [tex]x + \frac 1 x = -6[/tex], siden den andre løsningen gir opphav til en ikke-reduserbar annengradslikning.
Nøtt 38
Forenkle:
[tex]\left( 1 + \frac{1}{a}\right)\left( 1 + \frac{1}{a^2}\right) \left( 1 + \frac{1}{a^4}\right)...\left( 1 + \frac{1}{a^{2^{100}}}\right)[/tex]
Vi ser på produktrekken [tex]A_n=(1+\frac{1}{a})(1+\frac{1}{a^2})(1+\frac{1}{a^4}) \ ... \ (1+\frac{1}{a^{2^n}})[/tex]Nøtt 38
Forenkle:
[tex]\left( 1 + \frac{1}{a}\right)\left( 1 + \frac{1}{a^2}\right) \left( 1 + \frac{1}{a^4}\right)...\left( 1 + \frac{1}{a^{2^{100}}}\right)[/tex]
Vi observerer at
[tex]A_1=1+\frac{1}{a}[/tex]
[tex]A_2=1+\frac{1+a+a^2}{a^{2^0+2^1}[/tex]
[tex]A_3=1+\frac{1+a+a^2+a^3+a^4+a^5+a^6}{a^{2^0+2^1+2^2}[/tex]
Det kan se ut som at vi kan generalisere dette.
Først ser vi på den geometriske følgen
[tex]u_r=2^{r-1}[/tex]
Da kan summen av denne til n'te ledd skrives slik:
[tex]s_n=2^{n+1}-1[/tex]
Vi ser nå på følgen
[tex]u_s=a^{s-1}[/tex]
Vi ser at i produktrekken [tex]A_n[/tex] så er graden av det største leddet i rekken i telleren alltid én verdi mindre enn graden av nevneren. Da kan summen av denne til n'te ledd skrives slik:
[tex]s_n=\frac{a^{2^{n+1}-1}-1}{a-1}[/tex]
Da blir
[tex]A_n=1+\frac{a^{2^{n+1}-1}-1}{(a-1)(a^{2^{n+1}-1})}[/tex]
Dette kan forkortes til
[tex]A_n=\frac{a}{a-1}(1-a^{-2^{n+1}})[/tex]
Vi viser at dette er riktig ved induksjon:
Vi ser det er riktig for [tex]n=0[/tex],
[tex]A_0=1+\frac{1}{a^{2^{0}}}=1+a^{-1}[/tex]
[tex]A_0=\frac{a}{a-1}(1-a^{-2})=1+a^{-1}[/tex]
[tex]A_{n+1}=\frac{a}{a-1}(1-a^{-2^{n+1}})(1+\frac{1}{a^{2^{n+1}}}) = \frac{a}{a-1}(1-a^{-2^{n+1}})(1+{a^{-2^{n+1}}}) = \frac{a}{a-1}(1-a^{-2^{n+2}}) \\ = \frac{a}{a-1}(1-a^{-2^{[n+1]+1}})[/tex]
Da har vi bevist at [tex]A_n=\frac{a}{a-1}(1-a^{-2^{n+1}})[/tex]
Og følgelig er [tex]A_{100}=\frac{a}{a-1}(1-a^{-2^{101}})[/tex]
Tror dette er penest forkortet.
Kan nevne at [tex]A_{\infty}=\frac{a}{a-1}[/tex]
Gidder noen andre å slenge inn en oppgave?
Flott Jarle. En annen mulighet er:
[tex]P = \left( 1 + \frac{1}{a} \right)\left( 1 + \frac{1}{a^2}\right) \left( 1 + \frac{1}{a^4}\right)...\left( 1 + \frac{1}{a^{2^{100}}}\right) \\ \begin{align} \left(1 - \frac 1 a \right) P &= \left(1 - \frac 1 a \right) \left( 1 + \frac{1}{a} \right) \left( 1 + \frac{1}{a^2}\right) \left( 1 + \frac{1}{a^4}\right)...\left( 1 + \frac{1}{a^{2^{100}}}\right) \\ &= \left( 1- \frac{1}{a^2} \right) \left( 1 + \frac{1}{a^2}\right) \left( 1 + \frac{1}{a^4}\right)...\left( 1 + \frac{1}{a^{2^{100}}}\right) \\ &= \left( 1 - \frac{1}{a^4} \right) \left(1+ \frac{1}{a^4}\right)...\left( 1 + \frac{1}{a^{2^{100}}}\right) \\ &= ... \\ &= 1 - \frac{1}{a^2^{101}}\end{align} [/tex]
Og derfra følger svaret.
Nøtt 39:
Vis at [tex]1^3 + 3^3 + 5^3 + ... + (2n-1)^3[/tex] er delelig på [tex]n^2[/tex]
[tex]P = \left( 1 + \frac{1}{a} \right)\left( 1 + \frac{1}{a^2}\right) \left( 1 + \frac{1}{a^4}\right)...\left( 1 + \frac{1}{a^{2^{100}}}\right) \\ \begin{align} \left(1 - \frac 1 a \right) P &= \left(1 - \frac 1 a \right) \left( 1 + \frac{1}{a} \right) \left( 1 + \frac{1}{a^2}\right) \left( 1 + \frac{1}{a^4}\right)...\left( 1 + \frac{1}{a^{2^{100}}}\right) \\ &= \left( 1- \frac{1}{a^2} \right) \left( 1 + \frac{1}{a^2}\right) \left( 1 + \frac{1}{a^4}\right)...\left( 1 + \frac{1}{a^{2^{100}}}\right) \\ &= \left( 1 - \frac{1}{a^4} \right) \left(1+ \frac{1}{a^4}\right)...\left( 1 + \frac{1}{a^{2^{100}}}\right) \\ &= ... \\ &= 1 - \frac{1}{a^2^{101}}\end{align} [/tex]
Og derfra følger svaret.
Nøtt 39:
Vis at [tex]1^3 + 3^3 + 5^3 + ... + (2n-1)^3[/tex] er delelig på [tex]n^2[/tex]
Bruker uten bevis at
[tex]S_1 = 1^3 + 2^3 + \cdots + (2n)^3 = \frac{(2n)^2\cdot (2n+1)^2}{4}[/tex]
Derfra følger det at [tex]S_1 \equiv 0 \pmod{n^2}[/tex]
Deretter betrakter vi
[tex]S_2 = 2^3 + 4^3 + 6^3 + 8^3 + \cdots + (2n)^3 = 2^3(1+2^3 + 3^3 + 4^3 + \cdots + n^3) = 2^3\cdot \frac{n^2\cdot (n+1)^2}{4}[/tex]
Så [tex]S_2 \equiv 0 \pmod{n^2}[/tex]
Definerer så
[tex]S_3 = 1^3 + 3^3 + 5^3 + \cdots + (2n-1)^3[/tex]
og observerer at [tex]S_3 = S_1 - S_2 \Rightarrow S_3\equiv 0 \pmod{n^2}[/tex]
Nøtt 40
Bestem største positive heltall [tex]n[/tex] slik at [tex]n+10 | n^3+100[/tex]
[tex]S_1 = 1^3 + 2^3 + \cdots + (2n)^3 = \frac{(2n)^2\cdot (2n+1)^2}{4}[/tex]
Derfra følger det at [tex]S_1 \equiv 0 \pmod{n^2}[/tex]
Deretter betrakter vi
[tex]S_2 = 2^3 + 4^3 + 6^3 + 8^3 + \cdots + (2n)^3 = 2^3(1+2^3 + 3^3 + 4^3 + \cdots + n^3) = 2^3\cdot \frac{n^2\cdot (n+1)^2}{4}[/tex]
Så [tex]S_2 \equiv 0 \pmod{n^2}[/tex]
Definerer så
[tex]S_3 = 1^3 + 3^3 + 5^3 + \cdots + (2n-1)^3[/tex]
og observerer at [tex]S_3 = S_1 - S_2 \Rightarrow S_3\equiv 0 \pmod{n^2}[/tex]
Nøtt 40
Bestem største positive heltall [tex]n[/tex] slik at [tex]n+10 | n^3+100[/tex]
n+10 er faktor av [tex]n^3+100[/tex] hvis og bare hvis [tex]\gcd(n+10, n^3+100) = n+10[/tex]Magnus skrev:Bestem største positive heltall [tex]n[/tex] slik at [tex]n+10 | n^3+100[/tex]
[tex]n^3+10 = n^2(n+10)+(100-10n^2) \\ 100-10n^2 = -10n(n+10)+(100n+100) \\ 100n+100 = 100(n+10) - 900[/tex]
Dette betyr at
[tex]\gcd(n+10, n^3+100) = \gcd(n+10, 900)[/tex]
Og vi ser at største n som tilfredsstiller [tex]\gcd(n+10, 900) = n+10[/tex] er [tex]n=890[/tex]
Det største heltallet som oppfyller kravet er dermed 890.
Nøtt 41
Finn alle hele tall k slik at både (k + 1) og (16k + 1) er kvadrattall.
-
mrcreosote
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
La k+1 være kvadratet på a og 16k+1 kvadratet på b. Da er [tex]16a^2-b^2 = (4a-b)(4a+b) = 16(k+1)-(16k+1) = 15[/tex] så 4a-b og 4a+b er begge faktorer i 15 og problemet er redusert til å undersøke noen få tilfeller og enda færre om man observerer at (a,b) er ei løsning nøyaktig når (-a,-b) er det. (Det holder dermed å se på de positive divisorene av 15.)
4a-b=1, 4a+b=15 gir 8a=16, a=2 og b må også være heltall, så denne er god; k=3. Faktorene 3 og 5 gir på samme måte a=1 og k=0. De to siste tilfellene gir intet nytt, men vi kunne argumentert for ikke å trenge å sjekke disse.
Føler meg litt beæret som får presentere Nøtt 42:
Løs systemet
xy=z
yz=x
zx=y
i reelle tall
4a-b=1, 4a+b=15 gir 8a=16, a=2 og b må også være heltall, så denne er god; k=3. Faktorene 3 og 5 gir på samme måte a=1 og k=0. De to siste tilfellene gir intet nytt, men vi kunne argumentert for ikke å trenge å sjekke disse.
Føler meg litt beæret som får presentere Nøtt 42:
Løs systemet
xy=z
yz=x
zx=y
i reelle tall
I: xy = z
II: yz = x
III: zx = y
Vi ser at dersom en av variablene er 0, må alle være det. Vi antar nå at ingen av x, y, z er 0. Bruk I til å eliminere z i II. Vi får [tex]xy^2 = x[/tex], som betyr at [tex]y = \pm 1[/tex]. På samme måte kan vi eliminere de andre variablene, og vi ser at alle sammen er positiv/negativ 1.
Vi ser at eneste mulighet da er at alle variablene er positiv 1, eller at to av dem er -1 og en av dem 1. Følgende ordnede par løser systemet:
(0, 0, 0) (1, 1, 1) (-1, -1, 1) (-1, 1, -1) (1, -1, -1)
Nøtt 43
Finn en funksjon slik at [tex]f(t^2 + t + 1) = t[/tex] for alle [tex]t \geq 0[/tex]
II: yz = x
III: zx = y
Vi ser at dersom en av variablene er 0, må alle være det. Vi antar nå at ingen av x, y, z er 0. Bruk I til å eliminere z i II. Vi får [tex]xy^2 = x[/tex], som betyr at [tex]y = \pm 1[/tex]. På samme måte kan vi eliminere de andre variablene, og vi ser at alle sammen er positiv/negativ 1.
Vi ser at eneste mulighet da er at alle variablene er positiv 1, eller at to av dem er -1 og en av dem 1. Følgende ordnede par løser systemet:
(0, 0, 0) (1, 1, 1) (-1, -1, 1) (-1, 1, -1) (1, -1, -1)
Nøtt 43
Finn en funksjon slik at [tex]f(t^2 + t + 1) = t[/tex] for alle [tex]t \geq 0[/tex]
Funksjonen er:daofeishi skrev: Nøtt 43
Finn en funksjon slik at [tex]f(t^2 + t + 1) = t[/tex] for alle [tex]t \geq 0[/tex]
[tex]f(t)=\sqrt{t-\sqrt{t+\sqrt{t-\sqrt{t+\sqrt{t-\cdot\cdot\cdot}}}}}[/tex]
Nøtt 43B
Bevis eller motbevis påstanden.
Dette tilsvarer å finne en invers funksjon til [tex]f(u) = u^2+u+1[/tex]
Vi setter [tex]x=t^2+t+1 \Rightarrow t=\frac{-1 \pm \sqrt{4x-3}}{2}[/tex]
Siden bunnpunktet til grafen av [tex]y=t^2+t+1[/tex] er [tex](-\frac{1}{2},\frac{3}{4})[/tex] så er den originale funksjonen en én til én funksjon og har dermed en invers. Når t stiger i den originale grafen, vil også [tex]t^2+t+1[/tex] stige. Da kan vi konkludere med at funksjonen [tex]f(x) = \frac{\sqrt{4x-3}-1}{2}[/tex], [tex]1\leq x[/tex] (x er over 1 siden når t er lik null, er x lik 1)
Dette stemmer godt når vi skisserer grafene sammen.
Vi setter [tex]x=t^2+t+1 \Rightarrow t=\frac{-1 \pm \sqrt{4x-3}}{2}[/tex]
Siden bunnpunktet til grafen av [tex]y=t^2+t+1[/tex] er [tex](-\frac{1}{2},\frac{3}{4})[/tex] så er den originale funksjonen en én til én funksjon og har dermed en invers. Når t stiger i den originale grafen, vil også [tex]t^2+t+1[/tex] stige. Da kan vi konkludere med at funksjonen [tex]f(x) = \frac{\sqrt{4x-3}-1}{2}[/tex], [tex]1\leq x[/tex] (x er over 1 siden når t er lik null, er x lik 1)
Dette stemmer godt når vi skisserer grafene sammen.