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.

Problemløsingsteknikker

Innlegg daofeishi » 24/08-2007 14:54

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 endret av daofeishi den 28/01-2009 22:18, endret 20 ganger.
daofeishi offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 1486
Registrert: 13/06-2006 01:00
Bosted: Cambridge, Massachusetts, USA

Innlegg Sonki » 27/08-2007 18:14

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.
Sonki offline
Cayley
Cayley
Innlegg: 88
Registrert: 21/06-2007 12:31

Innlegg daofeishi » 27/08-2007 18:43

Stygg, stygg fortegnsfeil som nå er rettet opp i.
daofeishi offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 1486
Registrert: 13/06-2006 01:00
Bosted: Cambridge, Massachusetts, USA

Innlegg daofeishi » 28/09-2007 13:39

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 offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 1486
Registrert: 13/06-2006 01:00
Bosted: Cambridge, Massachusetts, USA

Re: Problemløsingsteknikker

Innlegg Ice » 18/10-2007 20:46

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

Innlegg TrulsBR » 18/10-2007 22:13

[tex](-1)^n= 3(-1)^n-2(-1)^n[/tex]
Deretter faktoriserer han ut 2-tallet.
TrulsBR offline
Dirichlet
Dirichlet
Innlegg: 155
Registrert: 19/04-2005 20:31
Bosted: Trondheim

Innlegg daofeishi » 19/10-2007 12:44

daofeishi offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 1486
Registrert: 13/06-2006 01:00
Bosted: Cambridge, Massachusetts, USA

Innlegg daofeishi » 20/10-2007 03:36

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".
daofeishi offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 1486
Registrert: 13/06-2006 01:00
Bosted: Cambridge, Massachusetts, USA

Rekke 3

Innlegg TrulsBR » 23/10-2007 21:48

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?
TrulsBR offline
Dirichlet
Dirichlet
Innlegg: 155
Registrert: 19/04-2005 20:31
Bosted: Trondheim

Innlegg Charlatan » 30/11-2007 21:52

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

svar på rekke 1 av teleskoprekkene

Innlegg orjan_s » 01/12-2007 00:27

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 endret av orjan_s den 01/12-2007 00:35, endret 1 gang
orjan_s offline
Cantor
Cantor
Innlegg: 141
Registrert: 13/02-2007 21:50

Innlegg Charlatan » 01/12-2007 00:33

liten feil der når du skrev leddene. når n=1, så er 1/(n+1)=1/2
så svaret blir 1/2
Charlatan offline
Guru
Guru
Innlegg: 2499
Registrert: 25/02-2007 17:19

Innlegg orjan_s » 01/12-2007 00:36

så det ja :P retta opp!
orjan_s offline
Cantor
Cantor
Innlegg: 141
Registrert: 13/02-2007 21:50

Innlegg daofeishi » 02/12-2007 11:54

Kjempeflott! Svarene over ser ut til å stemme, alle i hop.
daofeishi offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 1486
Registrert: 13/06-2006 01:00
Bosted: Cambridge, Massachusetts, USA

Innlegg TrulsBR » 13/07-2008 15:54

Inspirert av denne tråden:
http://www.matematikk.net/ressurser/matteprat/viewtopic.php?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 endret av TrulsBR den 14/07-2008 07:05, endret 2 ganger.
TrulsBR offline
Dirichlet
Dirichlet
Innlegg: 155
Registrert: 19/04-2005 20:31
Bosted: Trondheim

Neste

Hvem er i forumet

Brukere som leser i dette forumet: Ingen registrerte brukere og 5 gjester