matematikk.net

Her følger en rekke problemløsingsoppgaver, blant annet i kombinatorikk og, tallteori. De er alle sammen konstruert for å introdusere oppgaveløseren for viktige konsepter i matematisk problemøsing av typen ofte funnet i dette forumet og imatematiske konkurranser (som Abelkonkurransen). Problemene varierer i vanskelighetsgrad. (Den enkleste oppgaven står ikke nødvendigvis først.) Først introduserer jeg et problemløsingsprinsipp, og de påfølgende oppgavene kan så løses ved hjelp av denne teknikken. At oppgavene kan løses med gitt teknikk betyr selvsagt ikke at de må løses slik. En hver teknikk som leder til en løsning kan brukes. Mange av oppgavene er hentet fra et dokument av David A. Santos ved navn "Number Theory for Mathematical Contests."

Dersom du ikke er særlig erfaren med bevisløsning gjør ikke det noen verdens ting. Prøv deg på et bevis og post det. Andre forumbrukere vil hjelpe til med å få beviset i mål. (Dette kan være en uhyre lærerik prosess!) Jeg foreslår at svar til oppgavene legges til i nøtte-forumet som nye poster, en post per problem, med tittel "Problemløsing: {oppgavenavn}"


Prinsipp 1: Dueboksprinsippet
Dette er et enkelt men kraftig problemløsningsverktøy. Prinsippet er som følger: Dersom du har m duer og n duebokser, vil det finnes en boks som inneholder minst [tex]\lceil \frac{m}{n} \rceil[/tex] duer. ([tex]\lceil x \rceil[/tex] er det minste heltallet større enn x)

Eksempel: Dersom du har 5 klinkekuler som skal puttes i 4 glass, må det finnes ett glass med minst [tex]\lceil \frac{5}{4}\rceil = 2[/tex] klinkekuler.


Småsteiner: Du har et kvadrat med sidelengde 1 meter. Bevis at dersom du plasserer 5 småsteiner i dette kvadratet, vil det finnes 2 steiner som er maksimum [tex]\frac{\sqrt 2}{2}[/tex] meter fra hverandre.

Mengde og sum: Bevis at dersom du plukker 7 tall fra mengden {1, 2, ... 11}, vil 2 av tallene du har valgt ha sum 12

Stoler: Rundt et rundt bord er det plassert nøyaktig 60 stoler. Det skal nå sette seg N mennesker rundt bordet, slik at når det setter seg ett menneske til, må dette mennesket sette seg ved siden av et annet menneske. Hva er den minste mulige verdien av N?

Bekjenskaper: Du befinner deg i et rom med 5 andre personer. Bevis at det i dette rommet befinner seg enten 3 personer som kjenner hverandre fra før av eller 3 personer som ikke har møtt hverandre før (eller begge deler).

Alfabetet: Anta at bokstavene i det engelske alfabetet (a til z) ordnet i en tilfeldig rekkefølge. (I engelsk er a, e, i, o, og u regnet som vokaler og y som konsonant.)
a) Vis at det må finnes 4 etterfølgende konsonanter.
b) Vis at det ikke nødvendigvis må finnes 5 etterfølgende konsonanter.
c) Vis at dersom alfabetet er ordnet i en sirkel, må det finnes 5 etterfølgende konsonanter.



Prinsipp 2: Matematisk induksjon
Dette er en bevisteknikk som benytter seg av en matematisk "dominoeffekt." La oss si at du har en egenskap du vil bevise for alle de naturlige tallene. Dersom du kan vise at egenskapen gjelder for n = 1, og også kan vise at dersom egenskapen stemmer for n vil den stemme for n+1, er beiset fullført. (Videre eksempler finnes i Wikipediaartikkelen linket over, og kan også lett finnes andre plasser på nettet.)

Eksempel: Bevis at [tex]f(n) = 2^n - (-1)^n[/tex] er delelig med 3 for alle naturlige tall [n.
Påstanden stemmer for f(1). Vi skal nå vise at dersom den stemmer for f(n), vil den stemme for f(n+1).
Anta at [tex]f(n) = 2^n - (-1)^n = 3k[/tex].
Vi skriver nå om f(n+1):
[tex]f(n + 1) \qquad = \qquad 2^{n+1} - (-1)^{n+1} \qquad = \qquad 2\cdot 2^n + (-1)^n \qquad = \qquad 2(2^n - (-1)^n) + 3(-1)^n \\ = \qquad 2f(n) + 3(-1)^n \qquad = \qquad 2(3k) + 3(-1)^n \qquad = \qquad 3(2k +(-1)^n)[/tex]
Og dermed er f(n+1) delelig med 3 dersom f(n) er det. Vi har dermed bevist at påstanden gjelder for alle naturlige tall n.


Fakultet-ulikhet: Bevis at [tex]n! > 2^n[/tex] for alle heltall n > 3.

Delelig med 4: Bevis at [tex]f(n) = 3^{n} - (-1)^n[/tex] er delelig med 4 for alle naturlige n

Delelig med 133: Bevis at [tex]f(n) = 11^{n+2} + 12^{2n+1}[/tex] er delelig med 133 for all naturlige n

Sum av kvadrater: Bevis at [tex]1^2 + 2^2 + ... + n^2 = \frac{n(n+1)(2n+1)}{6}[/tex]

Vinkelsum i n-kant: Bevis at summen av vinklene i en n-kant er [tex]180(n-2) ^\circ[/tex]

Røtter og cosinus: Bevis at [tex]\underbrace{\sqrt{2 + \sqrt{2 \ +sqrt{ 2 + ... + \sqrt{2}}}}} _{\rm{n rot-tegn}} = 2\cos \frac{\pi}{2^{n+1}}[/tex]

Sinus-sum: Vis at [tex]\sin(\theta) + \sin(2 \theta) + \sin(3 \theta) + ... + \sin(n\theta) = \frac{\sin \left( \frac{(n+1)\theta}{2} \right) \sin \left( \frac{n\theta}{2} \right)}{\sin \left( \frac{\theta}{2} \right)}[/tex]





Prinsipp 3: Teleskoprekker
Dette er et prinsipp som av og til kan brukes for å summere (endelige og uendelige) serier. Dersom du kan skrive en rekke som en sum av ledd slik at hvert nye ledd kansellerer det forrige, har du "foldet sammen" rekken, omtrent som med gamle uttrekksteleskop. Teknikken vises med et eksempel.

Eksempel: Finn summen [tex]S = \sum _{n=1} ^\infty \frac{1}{n(n+1)}[/tex]
Ved å bruke delbrøkoppspaltning kan vi skrive summen som
[tex] S \qquad = \qquad \sum _{n=0} ^\infty \left( \frac{1}{n} - \frac{1}{n+1} \right) \qquad \\ = \qquad \left(1 - \frac{1}{2} \right) + \left( \frac{1}{2} - \frac{1}{3} \right) + ... \\ = \qquad 1 + \left(-\frac{1}{2} + \frac{1}{2}\right) + \left( -\frac{1}{3} + \frac{1}{3} \right) + ... \\ = \qquad 1[/tex]


Rekke 1: Finn [tex] S = \sum _{n=1} ^\infty \frac{1}{n^2 + 3n + 2}[/tex]

Rekke 2: Finn summen [tex]\frac{1}{1\cdot3} + \frac{1}{3\cdot5} + \frac{1}{5\cdot7} + ... [/tex]

Rekke 3: Finn summen [tex]S = \sum _{n=1} ^{1024} 2\sin \left( \frac{\pi}{8} \right) \sin \left( \frac{(2n+1)\pi}{8} \right)[/tex]

Rekke 4: Finn summen [tex]S = \sum _{n=1} ^{\infty} \arctan \left( \frac{1}{n^2+n+1} \right) [/tex]

Angående Induksjonsbeviset antar at oppgaven er:
[tex]3^n+(-1)^{n-1}[/tex] er delelig på 4 for alle naturlige tall n
Samme feil er også gjort i eksempelet.

Stygg, stygg fortegnsfeil som nå er rettet opp i.

Løsningstråd for småsteinoppgaven. Og bump av denne tråden Det er flere oppgaver å ta fatt i her ennå!

Kom gjerne med forslag til forbedringer og retting av feil i teksten over. Hvis det er flere som prøver seg, legger jeg gjerne ut beskrivelser av et par prinsipper til.

Edit: Ser også at å klassifisere dette som bare "tallteori" kan være litt snevert - "problemløsningsteknikker" kunne kanskje være litt mer passende.

Edit 2: Hva med å gi denne posten et "sticky"-merke en liten stund, på samme måte som annonseringene i de andre forumene? Dette er jo tross alt matematiske bevisteknikker som ofte går igjen, og som kan være nyttige for løsning av andre oppgaver i dette forumet - og for evt. abeldeltakere?

daofeishi skrev:

[tex] \qquad 2\cdot 2^n + (-1)^n \qquad = \qquad 2(2^n - (-1)^n) + 3(-1)^n \\ [/tex]

Hva er det som skjer her daofeishi?

[tex](-1)^n= 3(-1)^n-2(-1)^n[/tex]
Deretter faktoriserer han ut 2-tallet.

Røtter og cosinus

Jeg har også utvidet med noen flere induksjonsoppgaver.

Hvis det er flere som prøver seg på oppgavene, kan jeg bygge på med en introduksjon til "genererende funksjoner".

Her er mitt forslag til løsning på rekke 3:

[tex]S = \sum\limits_{n = 1}^{1024} {2\sin \left( {\frac{\pi }{8}} \right)\sin \left( {\frac{{\left( {2n + 1} \right)\pi }}{8}} \right)} \\ = \sum\limits_{n = 1}^{1024} {2\sin \left( {\frac{\pi }{8}} \right)\sin \left( {\frac{{\pi n}}{4} + \frac{\pi }{8}} \right)} \\ = \sum\limits_{n = 1}^{1024} {2\sin \left( {\frac{\pi }{8}} \right)\left( {\sin \left( {\frac{\pi }{8}} \right)\cos \left( {\frac{{\pi n}}{4}} \right) + \sin \left( {\frac{{\pi n}}{4}} \right)\cos \left( {\frac{\pi }{8}} \right)} \right)} \\ = \sum\limits_{n = 1}^{1024} {\left( {2\sin ^2 \left( {\frac{\pi }{8}} \right)\cos \left( {\frac{{\pi n}}{4}} \right) + 2\sin \left( {\frac{{\pi n}}{4}} \right)\sin \left( {\frac{\pi }{8}} \right)\cos \left( {\frac{\pi }{8}} \right)} \right)} \\ = \sum\limits_{n = 1}^{1024} {\left( {2\sin ^2 \left( {\frac{\pi }{8}} \right)\cos \left( {\frac{{\pi n}}{4}} \right) + \sin \left( {\frac{{\pi n}}{4}} \right)\sin \left( {\frac{\pi }{4}} \right)} \right)} \\ = \sum\limits_{n = 1}^{1024} {\left( {\left( {1 - \cos \left( {\frac{\pi }{4}} \right)} \right)\cos \left( {\frac{{\pi n}}{4}} \right) + \sin \left( {\frac{{\pi n}}{4}} \right)\sin \left( {\frac{\pi }{4}} \right)} \right)} \\ = \sum\limits_{n = 1}^{1024} {\left( {\cos \left( {\frac{{\pi n}}{4}} \right) - \left( {\cos \left( {\frac{\pi }{4}} \right)\cos \left( {\frac{{\pi n}}{4}} \right) - \sin \left( {\frac{{\pi n}}{4}} \right)\sin \left( {\frac{\pi }{4}} \right)} \right)} \right)} \\ = \sum\limits_{n = 1}^{1024} {\left( {\cos \left( {\frac{{\pi n}}{4}} \right) - \cos \left( {\frac{{\left( {n + 1} \right)\pi }}{4}} \right)} \right)} \\ = \cos \left( {\frac{\pi }{4}} \right) - \cos \left( {\frac{{1025\pi }}{4}} \right) \\ = \cos \left( {\frac{\pi }{4}} \right) - \cos \left( {\frac{\pi }{4} + 128 \cdot 2\pi } \right) \\ = \cos \left( {\frac{\pi }{4}} \right) - \cos \left( {\frac{\pi }{4}} \right) \\ = 0 \\ [/tex]

Kan dette stemme?
Har eventuelt noen en enklere framgangsmåte?

[tex]\underbrace{\sqrt{2 + \sqrt{2 \ +sqrt{ 2 + ... + \sqrt{2}}}}} _{\rm{n rot-tegn}} = 2\cos \frac{\pi}{2^{n+1}} \ , \ n\in Z^+[/tex]

Induksjon:

(1) Hvis [tex]n=1[/tex] så er Venstre Side [tex]=\sqrt{2}[/tex] og Høyre Side [tex]=2\cos{\frac{\pi}{4}}=2\frac{\sqrt{2}}{2}=\sqrt{2}[/tex]
Det stemmer for n=1

(2) Hvis det stemmer for [tex]k[/tex], så er [tex]\underbrace{\sqrt{2 + \sqrt{2 \ +sqrt{ 2 + ... + \sqrt{2}}}}} _{\rm{k rot-tegn}} = 2\cos \frac{\pi}{2^{k+1}} \ ... \ (*)[/tex]

Nå er [tex]\sqrt{2+\underbrace{\sqrt{2 + \sqrt{2 \ +sqrt{ 2 + ... + \sqrt{2}}}}} _{\rm{k rot-tegn}}} = \sqrt{2+2\cos \frac{\pi}{2^{k+1}}} ... \text{ \{ bruker * \} } \\ = \sqrt{2+2\cos 2\frac{\pi}{2^{k+2}}} = \sqrt{2+2\cos 2\frac{\pi}{2^{k+2}}} = \sqrt{2+2(1-2\sin^2 \frac{\pi}{2^{k+2}})}=2\sqrt{1-\sin^2 \frac{\pi}{2^{k+2}}}=2\cos \frac{\pi}{2^{[k+1]+1}}[/tex]

Altså hvis det er sant for [tex]k[/tex], så er det sant for [tex]k+1[/tex], og det er sant for [tex]1[/tex]. Dermed er det sant for alle [tex]n \in \mathbb{Z^+}[/tex]

Gitt rekka:

[tex]\sum _{n=1} ^\infty \frac{1}{n^2 + 3n + 2}=\sum_{n=1}^\infty \frac{1}{(n+1)(n+2)}[/tex]

Delbrøksoppspalting gir:

[tex]\sum_{n=1}^\infty \frac{1}{(n+1)}-\frac{1}{(n+2)}[/tex]

Skriver ut en del av leddene:

[tex]\sum_{n=1}^k \frac{1}{(n+1)}-\frac{1}{(n+2)}=\frac{1}{2}-\frac{1}{3}+\frac{1}{3}-\frac{1}{4}+\frac{1}{4}...\frac{1}{k+1}-\frac{1}{k+2}[/tex]

Ser at vi kan stryke en del ledd, og står igjen med: [tex]\frac{1}{2}-\frac{1}{k+2}[/tex]

Grensen når $k \to \infty$

[tex]\lim_{k \rightarrow \infty}(\frac{1}{2}-\frac{1}{k+2}) = \frac{1}{2}-0=\frac{1}{2}[/tex]

Vi får da:

[tex]S=\sum _{n=1} ^\infty \frac{1}{n^2 + 3n + 2}=\frac{1}{2}[/tex]

liten feil der når du skrev leddene. når n=1, så er 1/(n+1)=1/2
så svaret blir 1/2

så det ja retta opp!

Kjempeflott! Svarene over ser ut til å stemme, alle i hop.

Inspirert av denne tråden:
http://www.matematikk.net/ressurser/mat ... hp?t=19417, prøver jeg meg på Rekke 4:

Ser at:
[tex]\arctan \left( {n} \right) - \arctan \left( {n + 1} \right) = \arctan \left( {\frac{{n - \left( {n + 1} \right)}}{{1 + n\left( {n + 1} \right)}}} \right) = - \arctan \left( {\frac{1}{{n^2 + n + 1}}} \right)[/tex]

Fordi [tex]\arctan \left( { - x} \right) = - \arctan \left( x \right)[/tex] og [tex]\arctan u + \arctan v = \arctan \left( \frac{u+v}{1-uv} \right)[/tex].

Dermed har vi:
\begin{align*}
S &= \sum_{n = 1}^\infty {\arctan \frac{1}{{n^2 + n + 1}}} \\
&= - \sum_{n = 1}^\infty {\arctan \left( n \right) - \arctan \left( {n + 1} \right)} \\
&= \lim_{n \to \infty } \arctan \left( n \right) - \arctan \left( 1 \right) \\
&= \frac{\pi}{4}
\end{align*}