I denne snutten skal vi snakke om induksjonsbevis, som er en måte å bevise påstander om naturlige tall, eller som er
knyttet til naturlige tall. Under induksjonsprinsippet ligger det en veldig enkel observasjon
som kan være grei å peke ut helt fra starten av. Det er at hvis jeg har tallinjen bortover her, så har jeg
de hele tallene. Jeg begynner på 1 og ikke på 0 denne gangen. Så det er 1, 2, 3, 4 osv. Så er det slik at
hvis jeg nå plukker ut et eller annet helt tall, uansett hvor stort det måtte være, borti her,
kanskje noen milliarder stort. Så lenge det er et helt tall, er det slik at når jeg starter på 1 og teller,
så til 2, så til 3, så til 4 osv. Hvis jeg bare fortsetter dette her lenge nok, så kommer jeg til det tallet der borte.
Det er i grunn det prinsippet som ligger under induksjon.
Men hva er så induksjon? Jo, induksjon handler om å bevise ting for alle naturlige tall. La meg starte med
et lite eksempel. Når du lærer å derivere, så oppdager du kanskje et mønster ganske fort. Hvis du prøver å
derivere potenser av x, så er det slik at når du deriverer x^2, så får du 2x. Når du deriverer x^3, så får du 3x^2.
Når du deriverer x^4, så får du 4x^3. Så det ser ut til å være et mønster her.
I hvert eneste tilfelle så ser det ut som den potensen her oppe kommer fram, 2-tallet kommer fram der,
3-tallet kommer fram der, 4-tallet kommer frem her. Og så det slik at potensen til x blir en mindre.
x^2 går til x, x^3 går til x^2, x^4 går til x^3.
Så det ser nesten ut til å være et generelt mønster her, slik at hvis jeg tar x opphøyd i et eller annet tall k
og deriverer det, så ser det ut som det kommer en k fram. Så får jeg en potens mindre,
nemlig x^(k-1).
Nå vet jo du fra videregående skole at dette faktisk er en formel som gjelder. Men hvis man ikke har
kommet så langt, hvis man bare har observert dette mønsteret; hvordan skulle man da vise at noe slikt holdt
for alle mulige naturlige tall? Det er det som er spørsmålet her.
Det første man gjorde, hvis man ikke så med en gang hvordan man fikk til dette, det var kanskje å teste denne
hypotesen litt mere. Kanskje for å regne ut hva ble (x^5)', hva blir (x^6)'. osv.
Det ville delvis være for å teste hypotesen, men kanskje også for å se om det er noe mønster, om det er
et system som gjør at vi får dette uttrykket. La oss teste litt videre. Hvis jeg nå prøver å regne ut
(x^5)' uten å kjenne denne generelle regelen. Hva vil jeg da gjøre? En mulighet, siden jeg
kjenner (x^4)', er å dele opp dette her som et produkt. Si at x^5, det er x^4 ganget med x. Så jeg kan derivere
det produktet der isteden. Hvis det da bruker produktregelen for derivasjon, så skal jeg først
derivere x^4, og den kjenner jeg allerede. Den er 4x^3. Da har jeg derivert den,
og så skal jeg bare la den stå.
Så jeg skal gange med x. Så får jeg en ny sum, hvor jeg skal la den første faktoren stå, x^4, og så skal jeg derivere x-en,
som da bare er 1. Og så kan vi samle det sammen. Vi ser at vi har x^4 begge steder.
De to kombinerer seg til x^4. Så jeg har 4x^4 her pluss en x^4 til der borte. Så jeg får 5x^4.
Det stemmer jo med hypotesen vår. Når jeg deriverer x^5, så får jeg 5-tallet ned foran, og så får jeg
en potens lavere, nemlig x^4.
Det fungerte bra, å gå fra x^4 til x^5. Hva med x^6 da? (x^6)', hvordan skulle jeg regne ut den?
Ja, nå jeg kjenner jeg jo den deriverte til x^5, så jeg kan tenke på x^6 som et produkt av x^5 ganget med x.
Så skal jeg derivere det produktet. Jeg følger akkurat samme strategi som i stad. Nå kjenner jeg
den deriverte til x^5, så jeg kan bruke produktregelen. Først deriverer jeg x^5. Da så vi ovenfor at
jeg fikk 5x^4. Så skal jeg la den x-en stå, den står bare der. Neste gang skal jeg la x^5 stå, så den
er bare med her. Og så skal jeg derivere x-en, og det gir meg 1.
Akkurat det samme skjer her som i stad. Her har jeg en x^5, eller jeg har 5 av dem. Her har jeg en x^5,
så i alt får jeg 6x^5. Igjen, passer med mønsteret. Deriverer jeg en potens av x, så får jeg potensen ned foran,
og så får jeg en eksponent lavere enn det jeg hadde i utgangspunktet. Alt dette her bekrefter hypotesen min.
Det er også et mønster her som gjør at vi vet hvordan vi skal gå frem for å teste hypotesen for x^7 nå.
Da skriver jeg bare x^7 som (x^6)*x, og så deriverer jeg på samme måten som her. Og så får jeg
forhåpentligvis fram at den deriverte av x^7 er 7x^6.
Vi skal bruke denne metoden for å derivere x i en veldig høy potens, x^10 000 eller noe sånt. Skal vi gå fram
fra x^6, til x^7, til x^8 osv, så blir det veldig tungt. Spørsmålet er, er det en metode, slik at vi kan bevise
dette her en gang for alle? Det er der induksjon kommer inn.
La oss prøve å se litt mer systematisk på hva vi har gjort. Vi har vel skaffet oss en liten hypotese
om hvordan det står til med derivasjon. Hvis jeg tar x^n og deriverer, så får jeg nx^(n-1).
Jeg har også testet dette her for forskjellige verdier av n.
Jeg kom så langt opp som til 6 på forrige tavle. Det betyr at jeg vet
at denne påstanden er sann for n=1,2,3 osv oppover. Men jeg vet også noe mer, for jeg
hadde jo en liten strategi for hvordan jeg skulle gå videre, hvordan jeg kommer fra 4 til 5, og fra 5 til 6.
Jeg antydet også at slik kunne vi komme fra 6 til 7. Hvordan er den metoden for å komme et skritt videre?
Jo, det vi tenkte oss var at hvis jeg nå visste at den formelen var sann for en k-verdi, altså at
jeg visste at den deriverte av x^k fulgte det mønsteret for en k, så var trikset å finne
den deriverte til x^(k+1). Det var å splitte den i to biter. x^k som den ene faktoren, og den kjenner jeg jo
den deriverte til, og en x etterpå. Kunne forsåvidt ha spaltet dette uttrykket som et produkt på
andre måter også, men for å holde litt systematikk så gjør jeg det på denne måten her hele tiden. Nå skal jeg
derivere dette produktet her. Da kan jeg bruke produktregelen, samt det jeg vet at regelen vår gjelder
for x^k. Deriverer jeg den, så får jeg på kx^k-1, og så må jeg huske på å ta med den x-en der.
Da har jeg derivert første leddet og latt andre stå. Nå skal jeg la første faktor stå, så da får jeg
x^k, og så skal jeg derivere x-en som er 1.
Så skjer akkurat det samme som i stad. Disse to her kan jeg slå sammen til x^k. Da har jeg k av
disse x-potensene der, en til der borte. Så jeg får (k + 1)x^k. Dermed ser jeg at denne regelen
gjelder også for k+1, for her har jeg tatt en potens av x og derivert den. Da får jeg eksponenten
foran som faktor, og så mister jeg et 1-tall oppi eksponenten, så jeg får fra k+1 til k.
Dette argumentet viser altså at dersom jeg vet at regelen gjelder for x^k, for et tall k jeg
ikke har spesifisert, så gjelder det også for k+1. Det er dette her som er hele poenget med induksjon.
La meg prøve å illustrere hva som foregår ved å tegne tallinjen bortover her. Så kan jeg sette opp tallene,
1, 2, 3, 4, 5, 6, 7, 8 og 9. Så skal jeg da prøve å markere de tallene hvor jeg vet at denne formelen holder.
Jeg hadde sjekket innledningsvis, den gjelder for n=1,2,3,4.
Så langt hadde jeg skrevet opp til å begynne med. Så viste jeg da at den gjelder for 5 og 6.
Så langt var jeg kommet tidligere.
I tillegg har jeg denne generelle formelen, etter utledningen jeg hadde her, som viser at hvis
noe gjelder for en k-verdi, hvis x^k følger dette mønsteret, så vil k+1 også gjøre det. Da kan jeg
gå videre. Jeg vet nå at formelen gjelder for k=6. Da sier det regnestykket her oppe at den også gjelder
for den neste k-verdien, altså for 7. Så siden jeg vet at den gjelder for 6, så viser dette argumentet her,
ved å bruke k=6, at den gjelder for 7. Nå kan jeg bruke dette argumentet her oppe med k=7. Da går jeg fra 7
til neste, og det er 8. Da vet jeg at det gjelder for 8. Så kan jeg bruke akkurat den samme formelen,
nå som jeg vet at den er sann for k=8. Da har jeg den der, da viser regnestykket at den gjelder for
neste k-verdi, altså for 9.
Sånn kan jeg gå hele veien utover. Neste gang får jeg 10, så får jeg 11 osv. Hvis jeg har et helt tall
her ute, uansett hvor stort det er, så vil denne prosessen før eller senere komme fram
til det tallet, og vise at formelen vår også er sann for dette tallet langt der ute. Men jeg slipper
å gjøre alle disse prosessene for hånd, fordi dette regnestykket gjelder for alle k, og viser oss at alle
disse sprangene vil gjelde. På denne måten, ved å gjøre et regnestykke for en generell k, så greier jeg å vise at
jeg alltid kan komme fra et tall til det neste. Hvis da ting er ok til å begynne med, det hadde vært nok
å vise at denne tingen her var sann for n=1, så kunne jeg alltid komme fra et tall til det neste,
og da får jeg dekket alle de naturlige tallene. Dette er ideen bak induksjonsbevis. Vi vet at en påstand
er sann til å begynne med,
her for n=1, og så viser vi at det nødvendigvis er sånn at hvis påstanden holder for et naturlig tall,
så holder den for det neste. Da vil denne hoppeprosessen her overbevise oss om at påstanden er sann for alle n.
Dette var et eksempel med den deriverte av x^n. Jeg skal nå skrive opp litt mer generelt hvordan vi kan
formulere induksjonsprinsippet.
La oss nå skrive opp dette prinsippet generelt som vi har sett i et spesielt eksempel så langt.
Vi kaller det prinsippet om induksjon, eller induksjonsprinsippet. Det vi hadde istad, var jo en påstand
for hvert naturlige tall n, nemlig at den deriverte av x^n hadde en spesiell form. I det generelle prinsippet
så har vi da bare en påstand. "Anta at vi har en påstand." Det er bare et utsagn som enten er sant eller galt.
"en påstand P(n) om hvert naturlige tall n, altså n=1,2,3..."
og så videre oppover.
"... slik at" vi vet følgende to ting. For det første, at det første utsagnet blir P1, siden vi begynner
å telle på 1. "P(1) er sann". Så det andre utsagnet, som var måten jeg kommer fra et tall til det neste på.
"Hver gang P(k) er sann, så er P(k+1) også sann". Med det mener jeg å si at hver gang vi har et tall k
slik at P(k) er sann, så er også det påfølgende utsagnet P(k+1) sant. Da sier dette prinsippet;
"Da er P(n) sann for alle n=1,2,3,..." osv oppover. Det er det generelle prinsippet
om induksjon. Vi har en påstand for hvert av de naturlig tallene, og så vet vi da to ting om
disse påstandene, nemlig at den første påstanden er sann. Hver gang vi har etablert at en påstand er sann,
så er nødvendigvis den neste sann. Ut ifra de to forutsetningene, kan vi trekke konklusjonen at P(n) er sann
for alle naturlige tall. Ideen, grunnen til at dette holder, er akkurat den samme figuren som
jeg hadde i stad. Hvis jeg tegner heltallene utover her; 1, 2, 3, 4, 5 osv. og jeg markerer de tallene der
påstanden er sann, så vet jeg jo at P(1) er sann, for det ligger i den første premissen her. Så vet jeg jo at
siden P(1) er sann, så må P(2) nødvendigvis være det. Det er slik at hver gang påstanden er sann for et tall,
så er den også sann for det påfølgende tallet. Hvis P(1) er sann, så må P(2) nødvendigvis være det.
Men når jeg nå vet at P(2) er sann, så må P(3) være sann, og når jeg vet at P(3) er sann, så må P(4) være sann.
Jeg kan fortsette på den måten. Vi var jo enige om at jeg kom til et hvilken som helst
naturlig tall, hvis jeg bare holdt på lenge nok å gå fra 1, så har jeg et naturlig tall her nede.
Så vil denne prosessen, før eller senere, nå opp til det tallet og etablere at P for det tallet er sann.
Siden dette er et hvilket som helst tall, så betyr det at P(n) må være sann for alle P.
Så dette er det abstrakte induksjonsprinsippet. Det sier at hvis vi ønsker å bevise noe for et hvilket
som helst tall n, altså en påstand P(1) for en hvilken som helst n, ja så kan det ofte være lurt å
første etablere at P(1) er sann, bare sjekke det. Så ved et abstrakt resonnement vise at dersom
påstanden er sann for en k, så er den sann for den neste k. Da forteller induksjonsprinsippet oss
og dette argumentet som ligger bak, at påstanden er sann for alle n.
Det er det abstrakte prinsippet. Nå skal vi se på hvordan det kan brukes på to eksempler til.
La oss se på et eksempel til hvor vi kan bruke induksjon. Det jeg skal se på, er summer av oddetall.
Det første oddetallet er 1. Det neste oddetallet er 3. Hvis jeg legger sammen de to første oddetallene,
så får jeg 1+3. Så kan jeg fortsette og ta et oddetall til. 1 + 3 + 5, det neste er 7. 1 + 3 + 5 + 7 osv. Her har jeg tatt summen av
bare det første oddetallet, her har jeg tatt summen av de to første, her har jeg tatt summen av de tre første,
og her har jeg tatt summen av de fire første. Hvis vi nå regner ut hva disse summene er, hva får jeg da?
Her får jeg 1 selvfølgelig. Her får jeg 1+3=4. Her får jeg 1+3=4+5=9 og så får jeg
de første her summert opp til 9, og så får jeg 7 til, det blir 16.
Vi ser at de tallene som fremkommer her, det er faktisk de første kvadrattallene. Dette her er 1^2.
Dette er 2^2. Dette er 3^2, og dette er 4^2. Så det ser ut som summen av de
n første kvadrattallene, om det er 1, 2, 3 eller 4, alltid er dette tallet kvadrert. Man kan jo bli litt tvilende
og lure på om dette fortsetter. Hvis vi tar med det femte, hva får vi da? Altså 1+3+5+7+9, hvor mye har
vi da? Fra i stad vet jeg at jeg hvis jeg summerer de første opp til 7, så har jeg 16. Så legger jeg til 9,
da får jeg 25, som er 5^2.
Vi får en sterkere og sterkere indikasjon på at vi har en sammenheng her. Jeg kan lage
en hypotese om at summen av de n første oddetallene er n^2.
La oss skrive opp denne hypotesen. "Summen av de n første oddetallene er n^2."
Denne hypotesen har jeg akkurat på den formen som vi hadde i stad, nemlig et utsagn om hver n.
Kan tenke på P(n) som utsagnet, summen av de n første oddetallene, er n^2. at Så har vi sjekket at
dette utsagnet holder for de første verdiene av n. Her er det naturlig å prøve å bruke induksjon
på å bevise denne hypotesen her.
Siden vi allerede vet at påstanden gjelder for n=1, så er det da ifølge induksjonsprinsippet
nok å vise at vi kan gå fra et tall til det neste, altså at hvis P(k) gjelder, så gjelder nødvendigvis P(k+1).
Så det er strategien for å prøve å bevise at dette her er et generelt utsagn.
Den prosedyren vi har sett på hittil, den er ganske illustrerende, for det er sånn det ofte skjer at
matematikere kommer borti problemer de kan løse ved induksjon, nemlig at de oppdager et mønster som gjelder
for de første heltallsverdiene. Så eksperimenter de litt, ser at det holder videre, så danner de seg en hypotese
om at dette må være et generelt mønster. Det våpenet man da som regel bruker for å bevise at dette
faktisk er riktig, det er induksjon. Den første eksperimenterende fasen her er ofte viktig. Det er ikke alltid den
synes i matematikkoppgaver, for da har ofte noen gjort det arbeidet for oss, og så har de bare stilt opp
hypotesen uten at vi får være med på eksperimentet til å begynne med.
Her har vi en hypotese, og den må vi prøve å bevise. Nå er kanskje den hypotesen
foreløpig på litt ikke-matematisk form, eller litt for verbal form. Vi har jo bare skrevet den opp
med ord. Vi har ikke skrevet den opp med en formel. Før vi går videre, må vi kanskje prøve å matematisere
den littegranne, slik at vi får den på formelform. Så er det lettere å regne med den.
Hva sier denne her som en formel? Den handler jo om oddetall. Et typisk oddetall ser ut som 2 ganger
et tall i, minus 1. Slik ser et oddetall ut. Setter jeg inn i=1, så får jeg 2-1=1. Det er
det første oddetallet. Setter jeg inn i=2, så får jeg 2*2-1=3, som er det andre oddetallet osv.
Dette her er oddetall nummer i. Det jeg skal summere opp,
det er summen av de n første oddetallene, så det betyr at jeg må summere fra det første oddetallet
i=1, opp til det n-te oddetallet, som jeg får ved å sette inn n her oppe. Dette er matematisk sett
summen av de n første oddetallene. Det påstanden sier, er at den summen skal være lik n^2.
Dette er bare en omformulering av den påstanden der oppe, i en litt mer matematisk form.
Kanskje litt vanskeligere å se hva den betyr med en gang, men den er lettere å regne med og vi må
regne med denne her for å til et bevis.
La oss se om vi kan bevise hypotesen vår. Vi har sjekket at den stemmer for P(1).
Ifølge induksjonsprinsippet er det da nok å vise at vi alltid kan komme fra påstand nummer k
til påstand nummer k+1. Vi antar at påstand P(k) er sann for en k. Hva betyr det? Jo, det betyr at
dette uttrykket her borte er sant når jeg setter inn k Istedenfor n. Så jeg antar altså at summen
fra i=1 til k blir det, av 2i-1, det er lik k^2.
Den antar jeg er sann, så må jeg da vise at jeg alltid kan få den neste. "Må vise at P(k+1) er sann."
Hvordan gjør jeg det? Vel, hva sier P(k+1)? Kanskje vi skal skrive den opp den her borte, så vi vet
hva vi sikter på. P(k+1) er jo dette utsagnet her med k+1 satt inn for n. Så P(k+1), den vi
satser på er riktig, den sier da rett og slett at summen fra 1 til k+1 (setter inn k+1 for n), av 2i-1,
den er (k+1)^2. Det er dette vi skal vise er riktig. Det er greit å skrive det opp,
for da vet vi hva vi sikter på.
Ok, da skriver jeg opp det uttrykket som står på venstresiden der. Det jeg skal vise,
er at summen i går fra 1 til k+1 av 2i-1. Det er den jeg skal vise nå,
det er den som inngår i påstanden der borte. Det jeg vet noe om, det er P(k), og det er jo akkurat den samme summen,
bortsett fra at den går opp til k istedenfor k+1. Hvis jeg deler denne summen i to biter.
Først tar jeg med de k første leddene, de som inngår i summen her, og så tar jeg det (k+1)-leddet for seg.
Så får jeg summen i går fra 1 til k, av 2i-1. Der har jeg tatt med de k første leddene.
Grunnen til at jeg tar med de for seg, er at de vet jeg noe om herfra. Men når jeg har tatt med de k første leddene,
så har jeg glemt ledd k+1, så det må jeg ta med i tillegg her. Tar med k+1.
Da skal jeg sette inn i=k+1. Så må jeg huske å trekke fra den -1.
Dette ser fryktelig ut. Hvordan skal jeg få til noe her? Vel, jeg får hjelp av induksjonshypotesen, for jeg vet at
den første summen her er lik k^2. Hele det første uttrykket er lik k^2. Her bruker jeg det
jeg allerede vet, nemlig at P(k) er sann.
Da kan jeg rydde opp litt bak her. 2*k+1, da tar jeg først 2*k. Så får jeg 2*1=2,
så skal jeg trekke fra 1, så jeg får 2-1=1.
Jeg får at den summen her borte, er lik dette uttrykket. Det jeg ønsket å vise, var at den summen var lik (k+1)^2.
Men her stemmer algebraen ganske godt. Det uttrykket der er jo første kvadratsetning.
(k+1)^2. Så jeg har faktisk vist akkurat det jeg var
på jakt etter, nemlig at summen fra 1 til k+1 er (k+1)^2. Akkurat det som var påstanden P(k+1).
Da har jeg vist at dersom jeg antar at P(k) er sann (den antagelsen brukte jeg når jeg satte den
stygge summen der lik k^2), dersom jeg antar at P(k) er sann, så viser dette argumentet at P(k+1) er sann.
Siden det åpenbart gjelder for en hvilken som helst k, så kan jeg da alltid komme et skritt videre.
Induksjonsprinsippet sikrer hypotesen min, nemlig at denne påstanden er sann for alle naturlige tall n.
Det siste eksempelet vi skal se på med induksjon handler om en turnering i et spill. Spillet kan ikke
ende uavgjort. Vi kan tenke på badminton eller biljard. Vi har en turnering
med n spillere. De spiller alle mot alle, og hver spiller spiller en kamp mot alle de andre.
Etter at turneringen er over, så prøver vi å lage en slags uformell rangeringsliste på følgende måte.
Jeg skal ha en liste over alle spillerne som var med i turneringen. Så skal listen være slik at
hver spiller har slått den neste på listen. Spiller nr. 1 har slått spiller nr. 2, spiller nr 2 har slått
spiller nr. 3 og så videre bortover. Det kan selvfølgelig godt tenkes at spiller nr. 4 har slått
spiller nr. 1 i deres innbyrdes oppgjør, det er ikke noe galt. Det skal bare være slik at hver spiller
har slått den neste på listen. Spørsmålet er, er det alltid mulig å lage en slik, liste uansett hvor mange
spillere som er med i turneringen?
Dette er jo noe som egner seg for induksjon, i hvert fall i den forstand at vi har en påstand for hver n,
nemlig at i en turnering med n spillere, så kan vi alltid lage en slik rangeringsliste etterpå, som inneholder
alle spillerne og der hver spiller på listen har slått nestemann i deres innbyrdes oppgjør.
Hvis vi skal bevise noe sånt, må vi kanskje begynne å sjekke nedenfra, med turneringer for
få spillere. En turnering med en spiller er ikke så veldig mye tess, så vi får kanskje begynne å
sjekke i en turnering med to spillere. Er det alltid mulig i en slik turnering å rangere spillerne
etter hverandre? Det er det helt åpenbart her. Er det to spillere, så er det bare spilt et spill,
nemlig de to imellom. Da har selvfølgelig en vunnet og en tapt i det spillet, siden dette ikke kan ende uavgjort.
Da setter jeg bare vinneren først og taperen bakerst, så har jeg laget listen. Det viser at
i turneringer med to spillere, det minst fornuftige tallet, så går dette her greit. Nå så skal jeg prøve
å bruke induksjon til å komme videre, komme fra k til k+1. Jeg antar at
jeg allerede vet at i en turnering med to spillere så er dette her alltid mulig. Så skal jeg vise at
da er det også mulig, i en hvilken som helst turnering,
med k+1 spillere. Jeg antar altså at P(k) er sann, nemlig at i enhver turnering med k spillere,
kan jeg lage en slik liste. Jeg må vise at P(k+1) er sann, nemlig at i enhver turnering med k+1 spillere,
er det også mulig å lage en slik liste. Hvis vi har vist at vi kan komme fra P(k) til P(k+1),
så tar induksjonsprinsippet hånd om resten.
Hvordan kommer jeg fra P(k) til P(k+1)? Jeg må vise at dersom jeg har en turnering med k+1 spillere,
så kan jeg lage slik liste. Jeg vet at det kunne jeg gjort, dersom turneringen bare hadde
hatt k spillere. Da tar vi ganske frekt bort en spiller til å begynne med.
Jeg plukker en spiller, trekker han ut, sier at vi ser bort ifra dine kamper. Da er det som står igjen,
å regne som en turnering mellom de k andre spillerne. Etter at jeg har fjernet en spiller, står jeg igjen
med k. Disse kan jeg rangere etter prinsippet vårt, nemlig at hver spiller har slått den neste
på lista, rett og slett fordi P(k) er jo antatt å være sann. Her har jeg listen over disse k spillerne,
hver av dem har slått den neste på lista.
Spørsmålet nå er om vi kan få puttet inn den siste spilleren, han vi fjernet, på en fornuftig måte
uten å ødelegge systemet? Systemet er jo at hver spiller skal ha slått den neste på lista.
Da er det tre tilfeller vi må se på. To enkle, og en litt mer komplisert. Det aller enkleste som kan skje her,
er jo at denne spilleren vi har tatt ut, han har faktisk slått førstemann på lista. Hvis han har slått førstemann
på den lista over de andre spillerne, så kan jeg jo bare putte han på først og så er alt i orden.
Han har slått nestemann og så vet vi jo at mønsteret holder hele veien ellers. Hvis vår spiller,
han som vi tok ut av gruppen, faktisk har slått førstemann her, er det lett å lage en liste
over de P(k+1) spillerne som vi egentlig er interessert i. Tilsvarende, hvis vår spiller,
han vi tok ut, har tapt for sistemann på lista, så kan jeg føre ham på bakerst her.
Så er alt i orden.
Problemet, det vanskelige tilfellet, er når vår spiller
ikke har vunnet over han her borte, og heller ikke tapt for den spilleren der. Da må vi gå inn
og se på mønsteret. Hvis vi ser på den spilleren her, så var jo forutsetningen at han her vant over vår spiller.
Så det er en vinner i duellen med vår spiller. Sistemann her, han hadde jo tapt for vår spiller.
Hvis han hadde vunnet over vår spiller, kunne vi bare puttet vår spiller bakerst her. Vi vet at han her
har vunnet over vår spiller, han har tapt for vår spiller. Et eller annet sted inni her må vi skifte fra V-er til T-er.
Kanskje han har vunnet over vår spiller, han har vunnet over vår spiller, men før eller senere
må den første T-en dukke opp. Det er en til slutt, så før eller senere må det komme en T.
Så disse her vunnet over vår spiller, denne har tapt for vår spiller.
Men da kan vi bare ta vår spiller, han vi tok ut av gruppen i stad, og putte ham inn
på listen der sånn. Da er den overgangen der riktig. Den spilleren har vunnet over vår, så det er riktig.
Den spilleren har tapt for vår, så den overgangen er også riktig. Alle de andre overgangene er riktig,
for det er jo bygget inn i det opprinnelige systemet når vi bare så på de k spillerne. Ved å putte inn
vår spiller på det punktet der, når vi går over fra V til T, så har vi laget en liste over de k+1 spillerne
i den opprinnelige turneringen, som faktisk tilfredsstiller kravene.
Det viser altså at dersom P(k) er sann, dersom vi alltid kan lage en liste over k spillere
som tilfredsstiller kriteriene, så kan vi alltid lage en liste over en turnering med k+1 spillere.
Dermed har vi gått fra P(k) til P(k+1), og så tar induksjonen seg av resten. Det betyr at i en hvilken som turnering med n spillere,
uansett hvor stor n er, så kan vi alltid lage en liste av denne typen her.