Mattebloggen

En tärning låg på bordet. Den flyttades ett steg i taget genom att rullas över på en ny sida (som gränsade till sidan som nyss var i kontakt med bordet). Till slut hamnade tärningen på samma plats som i början med samma sida uppåt. Kunde den översta sidan vrida sig 90 grader i förhållande till startläget?

Svar:

Nej, det kunde den inte.

Lösning:

Låt oss beteckna kubens hörn med (sidan ligger precis under sidan ). Föreställ er att finns en liten tetraeder som är gjord av ett annat material. Vi kommer att följa den tetraederns position allt eftersom tärningen rör sig.

Om tärningen rullas över en gång, kommer tetraedern befinna sig i samma läge som hade från början, fast parallellfärflyttad. Och vice versa, avbildas på en parallellförflyttning av tetraedern .

För att tärningen ska komma tillbaka tillsamma ruta, måste den rullas ett jämnt antal gånger (föreställ er ett schackbräde på bordet, då byter rutan färg efter varje steg). Det innebär att den annorlunda tetraedern kommer att avbildas på sig själv.

Men om den översta sidan vrids 90 grader, så avbildas sidan på sidan , men den sistnämnda ligger utanför tetraedern av annorlunda material. Motsägelse.

En sifferkod, som består av 7 olika siffror kallas för godkänd sifferkod. Man vet att ett kassaskåp har en viss okänd godkänd sifferkod.

Om man slår in någon godkänd kod och åtminstone en rätt siffra kommer på rätt plats, så öppnas kassaskåpet.

Kan man öppna kassaskåpet på färre än 7 försök?

Lösning:

Jupp, det kan man! Slå in följande sex koder en efter en (de är alla godkända koder):

1234567
2345617
3456127
4561237
5612347
6123457

Om nu kassaskåpet INTE skulle öppnas, så är det säkert att ingen av siffrorna 1, 2, 3, 4, 5, 6 förekommer på de första sex platserna.

Men det betyder att endast siffrorna 7, 8, 9, 0 förekommer på de första sex platserna. Men det är omöjligt (enligt lådprincipen), eftersom alla siffror i koden skulle ju vara olika.

Motsägelse! Alltså måste kassaskåpet öppnas för någon ut av de 6 koderna.

Det finns ett naturligt tal m, sådant att talet 2^m har siffersumma 8. Kan sista siffran i talet 2^m vara lika med 6?

Svar:

Det kan den inte! Jag har fått in tre stycken olika lösningar, så det är bara att välja och vraka.

För att kunna förstå lösningarna är det bra att kunna:

moduloräkning

Om två tal har lika rester vid division med ett och samma tal n, så säger man att de talen är kongruenta modulo n.

Till exempel så är talen 3 och 11 kongruenta modulo 4 eftersom båda ger rest 3 när man dividerar med 4. Även talet -1 är kongruent med 3 modulo 4.
Man kan också skriva 3 11 (mod 4)

delbarthetsprincipen för 3

Ett heltal är delbart med 3 om och endast om dess siffersumma är delbar med 3. Man kan också vara fancy och säga att ett tal är delbart med 3 om och endast om talets siffersumma är kongruent med 0 modulo 3.

Till exempel så är talet 450072456 inte delbart med 3, eftersom siffersumman är 4+5+0+0+7+2+4+5+7=34 och det talet går inte att dela jämnt på 3.

delbarthetsprincipen för 9

Liknar faktiskt delbarthetsprincipen för 3. Ett heltal är delbart med 9 om och endast om dess siffersumma är delbar med 9.

Till exempel så är talet 1111000011111 delbart med 9, eftersom siffersumman är lika med 9.

Det är även så att ett godtyckligt tal och dess siffersumma alltid ger samma rest vid division med 9, det vill säga det är kongruenta modulo 9.

Lösning 1 (den officiella):

Vi konstaterar att de första tvåpotenserna är 2, 4, 8, 16 och 32, samt att inget av dessa uppfyller kriterierna. Dock måste alla kandidater vara jämnt delbara med dessa tal.

Om ett tal har siffersumman 8 och slutar på 6 finns två möjligheter:

a) Talet har formen 2*10^k + 6 för något k>=1 (dvs 26, 206, 2006, osv.)

26 (=2*13) är inte en tvåpotens, alltså måste k>=2, men alla andra tal på formen
2*10^k är delbara med 8, medan 6 inte är delbart med 8. Således blir talet som
helhet (2*10^k + 6) ej delbart med 8. Vi kan alltså helt utesluta denna möjlighet.

b) Talet har formen 1*10^k + 1*10ⁿ + 6 för något k>n>=1 (dvs på formen 100..0100…06)

6 är inte delbart med 4, så resten får inte heller vara det, om summan skall vara delbart med 4. Det enda n sådant att 10ⁿ inte är delbart med 4 är n=1 (k kan inte vara så litet). Alltså måste talet ha formen 1*10^k + 16.

Vi ser dock på samma sätt att 16 inte är delbart med 32, så det får inte 10^k heller vara. För alla k>=5 är 10^k jämnt delbart med 32, så dessa förkastas.

Man kan nu pröva de återstående lösningarna (10016, 1016, 116) var och en, men närmare bestämt är 16 16 i modulo 32, så 10^k måste vara lika med 32-1616 (mod 32). Det enda k som uppfyller detta är k=4, vilket ger 10016 = 2⁵ * 313, som på intet vis är en tvåpotens. För säkerhets skull kan konstateras att 1016=2³*127 och 116=2²*29.

Lösning 2 (den med perioder):

Att siffersumman av 2^m 8, kräver att 2^m är kongruent med 8 modulo 9.

Att 2^m slutar på 6, kräver att 4|m. Detta ser man genom att helt enkelt
göra en tabell av potenser av 2, och ser att den har period 4, om man bara
betraktar sista siffran.
2, 4, 8 (1)6, (3)2,(6)4, (12)8, (25)6,…

Så, vi undrar egentligen om det finns heltal k, så att 2^4k 8 (mod 9).
Ekvivalent med att
16^k 8 (mod 9)<=>
7^k 8 (mod 9) (*)

Nu,
7¹ 7 (mod 9)
7² 4 (mod 9)
7³ 1 (mod 9)
och nu har vi nått 1, så denna sekvens kommer upprepa sig om och om igen.

Alltså kan högerledet aldrig bli 8, och (*) kan ej lösas. Att (*) ej kan lösas
implicerar att 2^m ej kan sluta på 6 och samtidigt ha siffersumma 8.

Lösning 3 (den snygga):

Antag att ett sådant tal finns. Notera att 2^k endast slutar på 6 om k är jämnt (t.o.m delbart med 4, men jämnt räcker).
Då har 2^k-1 siffersumma 7 och är inte delbart med 3. Men k=2n så
2²ⁿ-1=(2ⁿ-1)(2ⁿ+1).
Märk att talen 2ⁿ-1, 2ⁿ och 2ⁿ+1 är tre stycken på varandra följande, så något utav dessa måste vara delbar med 3. Men det kan inte vara 2ⁿ, eftersom det är en tvåpotens.
Någon av faktorerna i uttrycket är således delbar med 3 och vi får motsägelse.

Detta inlägg är fortsättning på del 1 om Cevas sats. Första delen förklarar satsens formulering och ger tips för hur man skulle kunna bevisa den. Den här delen innehåller själva beviset.

Cevas sats

Given är en triangel ABC. Tre cevianer AM, BL och CK skär varandra i samma punkt om och endast om 

Bevis:

Antag först att cevianerna skär varandra i en och samma punkt O. Vi skall visa att värdet av uttrycket verkligen är 1.

Notera till exempel att trianglarna COM och MOB har lika stora höjder utgående från punkten O, eftersom deras baser ligger på samma linje. Låt höjderna ha längden h. Därför kan vi enkelt uttrycka förhållandet mellan dessa två areor:

Eftersom trianglarna CAM och MAB också har lika långa höjder, utgående från A, så kommer deras areor också att förhålla sig som  

Låt  k (något reellt tal). Men om är k gånger större än och är k gånger större än , så är differensen, , också k gånger större än

Det vill säga

Med analogiska resonemang får vi förhållanden mellan de andra par av de färgade trianglarna:

Därför kan vi skriva om uttrycket:

eftersom allt förkortas i det omskrivna uttrycket.

Nu har vi kvar att bevisa att värdet på uttrycket inte kan vara 1 utan att cevianerna skär varandra. Vi antar motsatsen, det vill säga att värdet är 1, men cevianerna råkade inte skära varandra i samma punkt:

Nu är vi så smarta som möjligt och använder oss av del 1, som vi redan har bevisat. Precis som i följande berättelse:

En matematiker och en fysiker löser praktiska uppgifter. De blev tillsagda att koka upp 1 liter vatten med hjälp av en vattenkran och en vattenkokare. Båda fyller förstås sin vattenkokare med vatten och sätter på den.

Nästa uppgift är annorlunda: de får en vattenkokare full med vatten och ska nu igen koka upp 1 liter vatten.

Vad gör en fysiker? Han ställer vattenkokaren på plattan och sätter på den förstås.

Vad gör en matematiker? Han häller ut vattnet och därmed ska han lösa praktisk uppgift nummer ett, vilket han redan kan.

I detta fall är det förstås inga onödigheter vi sysslar med. Men på samma sätt som i berättelsen ska vi göra någonting, för att kunna använda oss av tidigare kunskaper. Vi drar en ny linje, för att få samma situation som förut. Dra linjen CK’, som går igenom skärningspunkten för cevianerna AM och BL.

Från del 1 vet vi att följande måste gälla:

Men enligt antagandet har vi också

Bland annat är uttrycken lika med varandra och på så sätt får vi  , vilket i sin tur implicerar att , vilket är omöjligt, eftersom BK<BK’ och K’A<KA. Motsägelse, alltså var situationen omöjlig!

Således så fort uttrycket är lika med 1, så måste cevianerna skära varandra i en punkt.

Användningar för satsen

På så sätt har vi i princip bevisat flera satser på en gång, till exempel att medianerna i en triangel skär varandra i en och samma punkt. Samma sak gäller för bisektriserna, samma för linjer som förbinder hörn och tangeringspunkter för den inskrivna cirkeln. Det lämnas åt läsaren att komma på hur man ska använda Cevas sats för att visa de egenskaperna.

Det finns en rutig remsa 1xn:

Anders och Filip spelar ett spel. De turas om att göra drag: Anders får sätta ett kryss i en tom ruta och Filip får sätta en ring i en tom ruta. Dock får inte två kryss hamna bredvid varandra och inte heller två ringar. Spelaren, som inte kan göra ett drag när det är hans tur, förlorar.

Anders gör det första draget. Vem har ett vinnarstrategi, det vill säga vem kan alltid vinna oavsett hur motståndaren spelar?

Lösning:

Det finns många sätt att lösa problemet, jag har fått in några fina lösningar, men den här är nog den enklaste.

För det första är n=1 ett specialfall. Det finns bara ett sätt som spelet kan gå till på, nämligen att Anders sätter kryss och Filip kan inte göra något drag längre och därför förlorar.

Men för alla andra storlekar på remsan så vinner Filip. Det roliga är att hans första drag måste vara speciell, men efteråt kan han spela hur som helst så länge hans drag är tillåtna och ändå alltid vinna, oavsett hur Anders spelar.

Anders börjar med att sätta kryss någonstans. Det kan vara på remsans ände eller så kan det vara någonstans däremellan. I vilket fall som helst kan Filip sätta ring i en av remsans ändrutor:

eller

De fortsätter spela under tillåtna regler (aldrig två kryss eller två ringar bredvid varandra). Låt oss säga nu att Filip på något sätt lyckas förlora. Det betyder att han i en viss situation har ingenstans att sätta sin ring och de har precis varit Anders tur.

Eftersom Anders började och det precis har varit hans tur, så har han gjort ett fler drag än Filip, det vill säga det finns ett fler kryss än ringar på remsan.

Men notera att i den här situationen måste två utsatta kryss ha en ring mellan dem. För att två kryss kan inte vara bredvid varandra, och hade det bara funnits tomma rutor mellan dem, så skulle Filip ha en möjlig drag.

Alltså finns det minst en ring mellan varje parav kryss. Om vi börjar räkna upp symboler från kanten där Filip gjorde sitt första drag (första ringen) kommer vi se: ring, kanske fler ringar, kryss, ringar, kryss, ringar, kryss, … , slutar med kryss eller ring. (Här betyder ”ringar” att det kan vara exakt en ring också). Schematiskt exempel: OXOOOXOOXOOOXOOOXOOX.

Men då ser vi att varje kryss har minst en ring strax till vänster om sig. Det betyder att antalet kryss kan i den här situationen inte vara fler än antalet ringar. Vårt antagande om att Filip inte kunde göra drag var fel, därmen kommer Filip alltid att kunna göra drag efter att Anders har gjort sitt. Alltså är det Anders som först inte kommer kunna göra drag och förlorar för n>1.

I ett tehus träffades 55 människor, de var indier och turkar. Varje person drack antingen te eller kaffe. När en indier dricker te så talar han alltid sanning och när han dricker kaffe så luras han alltid, turkarna är precis tvärtom. På frågan ”Dricker du kaffe?” svarade 44 personer ”ja”, ”Är du turk?” svarade 33 personer ”ja” och ”Regnar det ute?” svarade 22 personer ”ja” på. Hur många indier drack te på tehuset?

Notera att det är okänt huruvida det regnade eller inte. Teoretiskt finns det alltså två olika situationer. Men ställer man upp ekvationssystem, så kan man komma fram till att ena situationen (att det inte regnar ute) är omöjlig. Här nedan följer Johans lösning, som klarar sig galant utan ekvationer.

Lösning:

Vilka är det egentligen som svarar ”ja” på frågan om de dricker kaffe? De enda som svarar ”ja” är kaffedrickande turkar (som ju talar sanning) och tedrickande turkar (som ljuger om sitt tedrickande). Så antalet ”ja”-svar är precis antalet turkar. De som svarar ”nej” är tedrickande indier (som talar sanning) och kaffedrickande indier (som ljuger om sitt kaffedrickande). Så antalet turkar är 44 och alltså är antalet indier 11.

Vad säger oss svaren på frågan ”Är du turk?” egentligen? Det är kaffedrickarna som svarar ”ja” och tedrickarna som svarar ”nej” (oavsett nationalitet). Så antalet kaffedrickare är 33 och tedrickare 22.

Eftersom antalet indier är 11 och det är 33 personer som dricker kaffe, så måste minst 22 turkar dricka kaffe. Om exakt 22 turkar talar sanning (dricker kaffe), så dricker alla indier kaffe. I det fallet finns alltså 0 indier som dricker te. Då är det enbart de 22 kaffedrickande turkarna som talar sanning på det här tehuset och alltså regnar det ute (om det inte hade regnat, skulle 33 personer ha talat sanning).

Antalet ”ja”-svar på frågor stämmer i det här fallet, så noll tedrickande indier är en möjlig lösning. Vi måste dock kontrollera att inga andra varianter finns.

Tidigare kom vi fram till att antalet kaffedrickande turkar är minst 22. Det fallet vi inte har undersökt än när de fler än 22. De talar sanning och då kan det inte regna ute (för annars skulle vi fått fler än 22 ”ja”-svar).

Då är antalet sanningssägare 33 (för de andra 22 personerna ljög och sa att det regnade). Men vi vet att antalet sanningsägare
måste var ett jämt tal. Varför det?

Genomför följande experiment. Om en turk och en indier har olika innehåll i koppen låt de byta koppar med varandra. Men då går de antingen från att båda ljuger till att båda talar sanning eller tvärsom. Låt då alla turkar ta så mycket kaffe de kan genom sådana byten. Det finns 33 kaffekoppar, så till slut dricker 33 turkar kaffe och 11 indier dricker te (det enda de kan dricka efter experimentet). Så antalet sanningsägare har blivit 44. Men notera nu att vid varje byte så ökade antalet sanningssägare med 2 eller minskade med 2 (ändrade inte paritet). Så det måste ha varit ett jämnt antal sanningssägare från början. Vilket motsäger att 33 sanningsägare från början skulle varit möjligt.

Alltså är 0 tedrickande indier den enda möjligheten.

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.

Flera av mina bekanta har berättat för mig vad deras första möte med riktiga matematiska bevis var. Och man märker kanske inte först att det man läser eller hör om är så kallade riktiga bevis, förrän man läser ordet ”bevis” explicit. De första sådana för var och en kunde ha varit bevis för Pythagoras sats, något induktionsbevis eller motsägelsebevis.

Här tänkte jag berätta om den mest klassiska klassikern av motsägelsebevis, nämligen att roten ur 2 är ett irrationellt tal.

Vad betyder irrationellt?

Ett irrationellt tal är ett tal som inte går att få med hjälp av naturliga tal 0, 1, 2, 3 …. och de aritmetiska operationerna +, -, * och /. Talen som däremot går att få på det sättet kallas rationella, till exempel . Rationella tal kan alltså skrivas som bråk.

Irrationell och rationell är helt enkelt motsatser. På grund av den här negativa definitionen (det vill säga definiera något genom att använda ett ”inte”), är det naturligt med ett negativt bevis till påståendet (det vill säga motsägelsebevis).

Påstående: är ett irrationellt tal.

Tankegång: Vi skall alltså bevisa att inte är ett rationellt tal. Kan verka svårt först, vi kan ju inte riktigt testa alla möjligheter, alla bråk som överhuvudtaget går att få fram. T.ex. (bara ett exempel nu, helt onödigt för beviset!!!):

Är Nej, för då skulle deras kvadrater vara lika , vilket absolut inte är sant!

Men det finns oändligt många bråk, vi kan sitta och gissa bråk som är ungefär lika med roten ur 2 och sedan verifiera att de inte är exakt lika. Men bara för att vi inte kan hitta något bevisar inte att det inte finns!

Det är nu vi inser att det faktiskt skulle vara lättare att på något sätt testa alla möjligheter samtidigt. Med det menar jag att vi antar att det finns ett sådant bråk och vi sedan kommer fram till att det aldrig kan bli likhet med roten ur 2. Det är kärnan i alla så kallade motsägelsebevis: antag att det går (antag det positiva påståendet, det utan ”inte”) och kom fram till motsägelse.

Bevis: Antag att roten ur 2 är lika med något bråk. Förkorta bråket så långt det går, så att nämnaren och täljaren inte längre går att dela med samma heltal. Vi har alltså nu:

och a och b är heltal som inte har någon gemensam delare.

Som förut försöker vi kontrollera likheten genom att kvadrera:

,

så

.

Varför är denna likhet omöjligt då? Vi tar hjälp av talteori, läran om heltal och delbarheter.

Vänsterledet är ett jämnt tal, så högerledet, måste vara det också. Alltså går att dela med 2, dvs , där är ett heltal. Skriv om likheten:

.

MEN detta innebär ju att så med samma resonemang som förut får vi att är ett jämnt tal. Men nu kommer vi fram till motsägelse, eftersom i situtationen då både och är jämna går det faktiskt att förkorta bråket (med 2). Nu är vi faktiskt klara.

Vi blev klara så fort vi fick motsägelse i vår lösning. Det är därför det heter motsägelsebevis.