Problemlösning lådprincipen

Den här vårterminen har jag äran att tillsammans med en annan lärare leda problemlösningskursen på Katedralskolan i Uppsala! Vi håller 2 timmarslektioner för intresserade elever på skolan, samt för nior som ska börja läsa där.

Tanken med träffarna är att träna eleverna inför kommande tävlingen SMT (SM i matte för gymnasister) och utveckla elevernas problemlösningsförmåga. Framförallt ska vi ha kul och upptäcka spännande ny matte tillsammans.

Problemlösning intro
Problemlösning heltalsekvationer

Nedan är den tredje lektionen som jag höll i (femte lektionen totalt).

Problemlösning Katedralskolan, 2012-05-09

Lådprincipen

“Om tio duvor sitter i nio lådor, så måste någon låda innehålla minst två duvor”

0. På en skola går 400 elever. Visa att två av dem fyller år samma dag.

1. a) Niklas har en stor låda med vita och svarta strumpor. En morgon har han bråttom och vill få ett par matchande strumpor så snabbt som möjligt ur lådan. Hur många strumpor måste han dra upp på måfå för att vara säker på att få ett par av samma färg?

b) Samma fråga, men med tre färger.

c) Det finns nu 10 vita, 10 röda samt 10 vita strumpor i lådan. Hur många strumpor ska Niklas dra på måfå för att vara säker att få upp alla olika färger?

2. I en granskog växer en miljon granar. Varje gran har som mest 200000 barr. Visa att det finns två träd i skogen med samma antal barr.

3. Det finns 15 pyttesmå hål i en maläten matta 4m×4m. Visa att man kan klippa ut en liten matta av storlek 1m×1m som är utan hål.

4. a) Givet 10 positiva heltal, kan det hända att alla möjliga skillnaderna emellan dem är ej delbara med 10?
b) Givet 11 positiva heltal, kan det hända att alla möjliga skillnaderna emellan dem är ej delbara med 10?

5. På Jorden utgör havet mer än hälfen av planetens yta. Visa att det finns två diametralt motsatta punkter på planeten, som båda ligger i havet.

6. 65 elever gjorde nationella provet i Engelska B. På mutliga, skriftliga respektive förståelsedelen kunde man få IG, G, VG eller MVG. Stämmer det att man kan hitta två elever som fick samma betygskombination?

7. Visa att vilka fem personer man än tar, så har två av dem samma antal kompisar i den gruppen.

8. Visa att vilka 52 heltal man än tar, så går det att hitta två vars summa eller skillnad är delbar med 100.

9. På ett militärlager finns kängor i storlek 41, 42, 43, två hundra kängor av varje storlek. Totalt är det tre hundra vänsterkängor och tre hundra högerkängor. Visa att man kan bilda åtminstone 100 par kängor som matchar.

Extraproblem. Visa att bland 6 personer går det alltid att hitta tre som känner varandra eller tre som inte känner varandra.

Mattecirkel: lektion i lådprincipen

Vår mattecirkel tuffar på vidare. Den är fortfarande med Anna, men eftersom jag tänkte skriva lite fiktion här, så skriver jag inte ut det i titeln.

För nyligen läste jag i en klok bok om hur man lär ut induktion. Bland annat fanns en påhittad dialog mellan en elev och en lärare där bådas tankegångar var klara. Man kunde se vanliga tankefel hos eleven och hur man kunde sätta eleven på rätt tankespår genom ledande frågor.

Den senaste gången handlade vår lektion om lådprincipen, som är även känd under namnet Dirichlets princip. Här är några av problemen som löstes:

1. a) Bland 22 elever finns fler pojkar än flickor. De sitter på rad. Visa att de finns minst ett par pojkar som sitter sida vid sida.
b) Bland 21 elever finns fler pojkar än flickor. De sitter på rad. Kan man vara säker på att det finns minst ett par pojkar som sitter sida vid sida?

2. Det finns 15 små hål i en maläten matta 4×4 m. Visa att man kan klippa ut en liten matta  av storlek 1×1 som är utan hål eller med ett hål på kanten.

3. a) Givet 10 positiva heltal, kan det hända att alla möjliga skillnaderna emellan dem är ej delbara med 10?
b) Givet 11 positiva heltal, kan det hända att alla möjliga skillnaderna emellan dem är ej delbara med 10?

Och här är ett (!) utav möjliga scenarion för en genomgång om lådprincipen.

Läraren: Tänk på följande problem. I en kasse ligger vita och svarta strumpor. Hur många strumpor måste man som minst ta upp ur kassen (om man måste dra på måfå) för att garanterat få upp två strumpor av samma färg?

Eleven: Det måste ju vara 3 strumpor! Har vi maximalt otur kommer de första två strumporna vara av olika färger. Men då måste den tredje ha samma färg som nån av de första två. Så minsta antalet är 3 strumpor.

Läraren: Helt rätt! Men var försiktig med vad du menar med “maximal otur”. Till exempel, att först dra upp en vit strumpa och sedan en svart eller lika mycket otur som att först dra upp en svart strumpa och sedan dra upp en vit. Och i uppgiften är det inte viktigt att få upp strumporna så snabbt som möjligt, utan vara säker på att dra upp två lika för ett visst antal.

Nästa fråga: I en studentkorrior på 5 rum bor 6 personer. Visa att det finns ett rum med minst två personer.

Eleven: Enkelt! Sätter man in 1 person i varje rum så blir det 1 över och då måste den personen flytta in i något rum där det redan finns nån!

Läraren: Men varför måste det vara minst 1 person i varje rum, det stod det inget om i villkoren?

Eleven: Nej, ok, men det var det sämsta möjliga fallet.

Läraren: På sätt och vis är väl alla fallen “sämst” hur vi än gör, det blir ju minst 2 personer i något rum i alla fall? Varför skulle vi inte kunna omplacera personerna på något smart sätt så att det inte behöver vara 2 eller fler i något rum?

Eleven: Men det går ju inte! Om något rum blir tomt, så måste det bli fler med ett annat!

Läraren: Men nu utgår du ändå från att du först placerar in 1 person i varje rum.

Eleven: Ok, jag börjar om från början. Om det är 0 eller 1 personer placerade i varje rum, så räcker inte rummen till för 6 personer.

Läraren: Precis! Nu har du i stort sett bevisat lådprincipen. Om det finns n stycken rum och fler än n personer, och personerna bor i rummen, så måste något rum ha minst 2 personer. Eller, i en mer välkänd version:

Om n lådor innehåller minst n+1 duvor, så innehåller någon låda minst 2 duvor.

Bevis är precis som i problemet. Om varje låda skulle innehålla maximalt 1 duva, skulle n lådor maximalt innehålla n duvor. Motsägelse.

Lektioner fortsätter på liknande sätt och problemen ökar i svårighetsgrad. Problem nummer 2 skulle kunna vara följande:

I en granskog växer en miljon granar. Varje gran har som mest 200000 barr. Visa att det finns två träd i skogen med samma antal barr.

Oftast är det bra att poängtera när man går igenom lösningen vad som är lådor och vad som är duvor. Det är inte så självklart i problemen från utdraget ovan. Notera också att man oftast drar igenom beviset för lådprincipen varje gång istället för att bara citera den. Det är essentiellt för förståelsen av principen.

Tallskogen

Rekommenderad från: 12 år

På ett område 1km x 1km växer en tallskog. Alla tallarna har diametern 50 cm. Visa att en fältbiolog kan hitta en ledig rektangel 10m x 20m i skogen, för att kunna sola där med alla sina vänner om det finns a) 1200 b) 4200 c) 4500 d) 4600 träd i skogen.

SONY DSC

Visa lösningen