Problemløsingsteknikker

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

daofeishi
Tyrann
Tyrann
Innlegg: 1486
Registrert: 13/06-2006 02:00
Sted: Cambridge, Massachusetts, USA

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 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, 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]
Sist redigert av daofeishi den 28/01-2009 22:18, redigert 20 ganger totalt.
Sonki
Cayley
Cayley
Innlegg: 88
Registrert: 21/06-2007 13:31

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.
daofeishi
Tyrann
Tyrann
Innlegg: 1486
Registrert: 13/06-2006 02:00
Sted: Cambridge, Massachusetts, USA

Stygg, stygg fortegnsfeil som nå er rettet opp i.
daofeishi
Tyrann
Tyrann
Innlegg: 1486
Registrert: 13/06-2006 02:00
Sted: Cambridge, Massachusetts, USA

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?
Ice
Cayley
Cayley
Innlegg: 79
Registrert: 13/01-2006 23:34
Sted: Trøndelag

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?
Èg er Islendingur :P
TrulsBR
Dirichlet
Dirichlet
Innlegg: 155
Registrert: 19/04-2005 21:31
Sted: Trondheim

[tex](-1)^n= 3(-1)^n-2(-1)^n[/tex]
Deretter faktoriserer han ut 2-tallet.
daofeishi
Tyrann
Tyrann
Innlegg: 1486
Registrert: 13/06-2006 02:00
Sted: Cambridge, Massachusetts, USA

daofeishi
Tyrann
Tyrann
Innlegg: 1486
Registrert: 13/06-2006 02:00
Sted: Cambridge, Massachusetts, USA

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".
TrulsBR
Dirichlet
Dirichlet
Innlegg: 155
Registrert: 19/04-2005 21:31
Sted: Trondheim

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?
Charlatan
Guru
Guru
Innlegg: 2499
Registrert: 25/02-2007 17:19

[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]
orjan_s
Cantor
Cantor
Innlegg: 141
Registrert: 13/02-2007 21:50

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]
Sist redigert av orjan_s den 01/12-2007 00:35, redigert 1 gang totalt.
Charlatan
Guru
Guru
Innlegg: 2499
Registrert: 25/02-2007 17:19

liten feil der når du skrev leddene. når n=1, så er 1/(n+1)=1/2
så svaret blir 1/2
orjan_s
Cantor
Cantor
Innlegg: 141
Registrert: 13/02-2007 21:50

så det ja :P retta opp!
daofeishi
Tyrann
Tyrann
Innlegg: 1486
Registrert: 13/06-2006 02:00
Sted: Cambridge, Massachusetts, USA

Kjempeflott! Svarene over ser ut til å stemme, alle i hop.
TrulsBR
Dirichlet
Dirichlet
Innlegg: 155
Registrert: 19/04-2005 21:31
Sted: Trondheim

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*}
Sist redigert av TrulsBR den 14/07-2008 08:05, redigert 2 ganger totalt.
Svar