Problemløsingsteknikker
Lagt inn: 24/08-2007 15: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 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]
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]