Etikett: konstruktionsproblem

Vi ska hitta på en sådan klippning för alla möjliga antal bitar, från och med 6.

Det känns lite omöljigt, hur ska vi kunna ge en lösning för alla tal som är större än eller lika med 6? Det tar ju oändligt lång tid att presentera! Men, uppgiften säger ”visa att”, det vill säga ”visa att det går” och det frågas inte hur, vilket är två olika saker. Det är skillnad på ”visa att ekvationen har en lösning” och ”bestäm en lösning för ekvationen”. På samma sätt som det är skillnad på ”visa att dinosaurierna levde på Jorden under hundra miljoner år” och ”hitta hundra miljoner årtal under vilka dinosaurierna levde”. Det kan vara subtil olikhet mellan de paren av påståenden, men det är bara så att det senare svaret skulle ge oss det tidigare men inte tvärtom. Man kanske vet att dinosaurierna levde under en viss period, men är osäker på under vilka årtal de säkerligen levde. Men ger någon oss årtal så är det klart att dinosaurierna levde i minst hundra miljoner år.

Men åter till problemet, hur ska man börja lösa det? Tvärtemot vad jag precis skrev om, ska man försöka konstruera lösningarna explicit för olika tal. Vilka n lyckas vi med? Det är en viktig metod i problemlösning, som säger att vi ska starta med små fall, trots att vi har godtyckligt stora framför oss. Små fall kommer ge oss en känsla för hur problemet funkar.

Ok, i hur många kvadrater kan du dela upp en stor kvadrat? Jag kan i 4! Visst, det ingick inte i problemet att lösa det för 4, men jag kan ändå:

Det går upprepa samma idé och få 9, 16, (och så vidare) kvadrater:  

Detta ger oss inte så mycket, bara alla kvadrattal, men vi har oändligt många kvar. Vad händer om vi änvänder ”samma konstruktion” som i fallet 4, fast på ett annat sätt? Jag menar så här:

Och vi kan givetvis fortsätta på samma sätt, splittrande en av kvadraterna i fyra små. Vi kan få 7 kvadrater som på bilden ovan och sedan också 10, 13 osv:

Det spelar ingen roll för oss vilken av de befintliga kvaraterna vi delar in i fyra nya. Det viktigaste är att antalet ökar med 3 hela tiden.

Vi har alltså fått svaret för 7, 10, 13, 16, 19, … Oändligt många svar, med det är ändå foftarande oändligt många kvar! Men ni kanske kan gissa att talen 6, 9, 12, 15, …. och talen 8, 11, 14, 17, …. kan fixas på samma sätt så fort vi hittar på någon lösning för 6 respektive 8 kvadrater. Notera då att alla tal större än 6 kommer vara fixade då.

Okej, försök att klura ut 6 eller 8 kvadrater själv innan du tittar nedan. Ett tips är att ha en motsatt taktik: i stället för att lägga till kvadrater till en befintlig konstruktion, försök att ta bort lite kvadrater.

För att få 6 kvarater tar jag bort lite från min konstruktion på 9 kvadrater:

 

På liknande sätt gör vi 8 kvadrater från 16:

Då är vi klara! Vi kan få alla konstruktioner från konstruktionerna med 6, 7 och 8 kvadrater genom att dela upp en kvadrat i fyra och därmed lägga till 3 till antalet.

Vad har då detta med induktion att göra?

Denna lösning, som går ut på metoden ”stegvis konstruering”, kan även anpassas till induktionsmodellen. I det här problemet består inte induktionssteget av ett enda ”steg”, från talet n till talet n+1, utan av tre fall som i och för sig löses på samma sätt (fallen är olika kongruensklasser modulo 3). Basen bestär också av olika fall. 

Uppgiften är löst, vi förstår hur lösningen funkar, det är nu vi kan baka in den i induktionsmodellen:

Bas:

n=6, n=7 och n=8:

Induktionssteg:

Induktionsantagandet är att det går att dela upp en stor kvadrat i n stycken mindre. Vi visar att det då går att dela upp i n+3 stycken mindre. Beviset är: skär en av gamla kvadraterna i fyra nya.

Slutsats:

Enligt inuktionsaxiomen och alla basfall modulo 3 visade kan vi dra slutsatsen att påståendet gäller för alla n>5.

Detta kanske inte var det bästa exemplet på att induktion kan vara bra. Lösningen ser mycket naturligare ut i den mindre formella beskrivningen. Men å andra sidan blir den mycket kortare och mer elegant formulerat i induktionstermer.