Mattebloggen

I helgen har Sonja Kovalevsky-dagarna varit i Stockholm för andra året i rad. Och fjärde året i rad har jag hjälpt till med problemlösningsdelen :)

Här är tävlingsproblemen och lösningar för de intresserade.

Äntligen är de här, lösningarna till problemen som eleverna tävlade i under Sonja Kovalevsky-dagarna 2010!

Lösningar till alla 15 problem

Lösning:

(a) Det gäller alltså att hitta något villkor (som kan variera), som när det är uppfyllt ger upphov till exakt 12! olika fall. Det där låter lite luddigt om man inte har funderat på det, men här kommer det mer konkreta förklaringen.

Spader ess är fixt, det kan vi inte flytta på. Säg att vi har något snyggt sätt som kortleken är lagd på. Notera då att vi kan byta plats på alla treor och alla fyror i respektive färg (så hjärter tre och hjärter fyra byter plats osv.)

Men vi kan även byta plats på alla tvåor och kungar samtidigt. Vi kan egentligen byta plats på vilka valörer som helst så länge alla kort av den valören byts mot ett annat fixt valör och så länge essen inte flyttas (de får inte flyttas för spaderesset).

Eftersom man får byta plats på 12 valörer (man kan även byta fler än 2 valörer samtidigt, t.ex. tvåor byts mot treor, treor mot fyror och fyror mot tvåor), så finns 12! sådana byten. Därför är antalet snygga uppläggningar delbart med 12 fakultet.

”Villkoret” här var egentligen att vi fixerade vilken färg varje plats hade samt vilka platser som hade likadana valörer och alla essens platser var också bestämda. Det finns 12! sätt att nu placera ut de bestämda valörerna.

(b) Uppgiften kan ses på ett annat sätt. I fall det finns en 4×13-tabell, där raderna betecknar färger och kolonnerna betecknar valörer, så är antalet snygga sätt lika med antalet sätt som ett torn kan inuti tabellen så att den startar från säg vänstra övre hörnet, kommer till varje ruta en gång och sedan kommer tillbaka till sin egen plats. Kom ihåg att ett schacktorn kan gå lodrätt eller vågrätt godtyckligt många rutor.

Eftersom delen (a) är visat, räcker att bevisa att antalet sätt är delbart med 13. Klistra ihop tabellen längs de korta ändarna så att det bildas ett band med fyra rader. Om vi fixerar en rutt som börjar från spader ess så kan vi rotera bandet 12 steg så att det för varje steg bildas en ny rutt (som inte längre börjar med spader ess).

Vi visar att varje sådan falsk rutt kan göras om till en riktig och den kommer inte vara lika med den ursprungliga.

Varje falsk rutt går ändå igenom spader esset vid något tillfälle, och eftersom den kommer tillbaka till samma ruta som den startade ifrån så kan den lika gärna betraktas som en rutt som börjar i spader ess (som nu är tillåten).

Men varför är det inte lika med det ursprungliga? Då skulle rutten vid en viss rotation avbildas till sig sjäv. Betrakta då vilket som helst vågrätt drag (ett sådant måste finnas). Om vi gör rotationen 13 gånger så ser vi att alla rutor på den raden är startpunkter för vågräta drag (eftersom 13 är ett primtal). Men det kan inte vara möjligt, eftersom vi då inte kommer från den raden.

På så sätt delas rutter upp i grupper om 13 och alltså är antalet rutter delbart med 13!

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.

På ett papper finns en bild på en svart kvadrat. Du har tillgång till 7 kvadratformade brickor av samma storlek som den ritade kvadraten. Hur ska du göra för att täcka över kvadraten med brickorna så att inga brickor ligger på varandra och varje bricka täcker åtminstone en liten del av kvadraten (åtminstone en punkt inuti)?

Det kluriga ligger i att lista ut att man kan vrida på brickorna innan man lägger dem på kvadraten. Den lösningen kom de regelbundna lösarna Johan och Ove på, men också niorna Amanda, Elin, Emelie, Adam, Michaela och Hampus från Häggviksskolan i Stockholm. Författaren tackar Adam Jonsson, deras lärare, för hans engagemang!

Här är de inskickade lösningarna, som förstås är egentligen likadana. Notera dock att alla lösningar är fel för att kvadraten inte är svart ;)

Lösning:

På hur många sätt kan man skriva talet 2009 som en summa av några positiva nästan lika heltal? Talen kallas nästa lika om deras skillnad är (till beloppet) maximalt 1. Sätten betraktas som samma om det enda som skiljer dem åt är ordningen på termerna.

Diskussion:

Först och främst ska man pröva sig fram till lösningar, för att ”känna på” problemet. Det gäller alltså att komma på några sätt att dela 2009 i några nästan lika stora delar.  En första tanke är  att dela upp det som en summa av lika stora delar. Hur man göra det beror på vilka tal 2009 är delbart med.

2009 = 7*287 = 7*7*41

Så till exempel har vi uppdelningarna i exakt lika termer

2009 = 287 + 287 + 287 + 287 + 287 + 287 + 287

2009 = 1 + 1 + … + 1    (2009 stycken ettor)

2009 = 41 + 41 + … + 41    (49 stycken 41:or)

2009 = 2009

Men vad händer om vi försöker dela upp i ett visst antal termer, där antalet inte är en delare till 2009? Till exempel två termer? Då delar vi på två så gott det går, resultatet blir 1004 med rest. Men uppdelningen

2009 =  1004 + 1005

funkar ju, för att 1004 och 1005 är nästan lika.

Försök på samma sätt med tre termer. 2009 delat på 3 blir 669 och resten är 2. Då kan vi göra såhär:

2009 = 669 + 670 + 670

Den här idén med rester kommer vi att använda i lösningen.

Lösning:

Enligt villkoren måste varje sätt att summera upp till 2009 innehålla maximalt två sortes termer: ena kan uttryckas som x och andra som x+1. Ifall det fanns andra tal, skulle de inte vara nästan lika med x eller x+1.

Notera nu att för varje antal termer (beteckna antalet med n), så finns det ett sätt att dela upp 2009 i just så många nästan lika termer. Nämligen, dela 2009 med n med rest:

2009 = n*k + r

där k är kvoten och r är resten. Man vet att resten alltid är mindre än det man delade med, således mindre än antalet termer.

Likheten kan skrivas om:

2009 = k + k + … + k + r

där termen k förekommer n gånger. Men för att få just n stycken termer, fördelar vi r stycken ettor på r stycken k-termer. Det kan vi göra eftersom k är mindre än n. Således:

2009 = k + k + … + k + (k+1) + (k+1) + … + (k+1)

där termer av typen k förekommer (n-r) gånger och termer av typen (k+1) förekommer r gånger.

Så nu har vi 2009 stycken sätt att dela upp! Ett sätt för varje antal termer. Men finns det inga andra sätt?

Nej, faktiskt inte. Vi sa ju tidigare att termerna måste vara x och x+1. Har vi ett fixerat antal termer i summan

2009 = x + x + … + x + (x+1) + (x+1) + … + (x+1)

så kan vi inte ändra vare sig några x till x+1 eller tvärtom, för då skulle det hela inte summera upp till 2009.

Således är svaret: 2009 sätt.

Lägg ihop bitarna nedan till en figur, som har en symmetriaxel. Det betyder att figuren skall vara spegelsymmetrisk i en viss linje. Varje bit skall användas exakt en gång.

Lösning:

Johans lösning:

Två andra lösningar:

En dag bestämde sig en snigel för att starta en resa. Snigeln rörde sig framåt längs med en rak sträcka i 6 minuter tills det var nog för dagen. Under den tiden kom några människor och tittade på snigels underbara resa. Hela tiden var snigeln betraktad av åtminstone en människa. Det visade sig att varje människa kollade på snigeln i exakt 1 minut och under den tiden kröp den exakt 1 meter. Hur mycket kunde snigeln maximalt krypa under den dagen?

Uppgiften kunde misstolkas lite här och var, så det behövs lite förtydliganden. För det första så betraktade varje människa snigeln bara under resans gång. För det andra, så kollade varje människa på snigeln 1 minut i sträck och inte utspritt hur som helst.

I allmänhet, om problemvillkoren kan tolkas på flera sätt, tolka dem på det enklaste möjliga sättet. Vill jag ge en svårare uppgift, kommer jag poängtera det också.

Lösning:

Först ett litet lemma (hjälpsats). Jag påstår att snigeln aldrig kunde krypa mer än 2 meter under 1 minut. Varför det?

Om man fixerar en minut så kan det hända två saker. Antingen kollade en speciell människa på snigeln just den minuten och då kröp den exakt 1 meter. Eller så fanns ingen sån speciell människa.

Men någon kollade ju på snigeln hela tiden och en viss särskild människa, som började kolla innan den fixerade minuten, slutade kolla på den sist av alla (som började innan). Och på andra änden av den fixerade minuten finns en annan unik människa, som började kolla efter minuten började, men ändå var först av alla sådana människor. Den särskilda och den unika människan kommer tillsammans täcka hela minutintervallet på grund av hur vi valde dem. Var och en av dem bidrar med högst 1 meter till minuten, alltså max 2 meter totalt.

Då är det inte så mycket kvar av problemet!

Någon människa började ju kolla precis när snigeln startade sin resa. Det betyder att snigeln kröp exakt 1 meter under sin första minut. Samma sak gäller sista minuten, för någon var tvungen att kolla på snigeln precis in i det sista. Det är då 4 ”mittenminuter” kvar och på grund av lemmat kunde det sammalagt ge max 8 meter. Alltså kan avståndet maximalt vara 1+1+8=10 meter.

Nu ska vi bara lyckas hitta på en situation då snigeln kryper exakt 10 meter. Vi vet nu att varje ”mittenminut” måste uttnyttjas till max. Här är ett exempel:

Idén är att utnyttja tiderna maximalt: snigeln rör sig jättefort när bara människa kollar på den. Annars, om det inte är start- eller slutminut, så står snigeln stilla (och vilar). Klart!

Veckans hedersomnämnanden går till både Johan och Ove, som hade rätt idéer och nästan färdiga lösningar.

Rita två fyrkanter, som tillsammans kan läggas ihop till

(i) En triangel, men också en femkant

(ii) Både en triangel, en fyrkant och en femkant.

Med ”läggas ihop” menar jag förstås att fyrkanterna inte får överlappa varandra, inte heller får det bildas hål.

Lösning:

Löser man (ii), löser man förstås och (i). Hur tänker man då?

Det är ganska naturligt att utgå från en triangel, för att bitarna ska ändå kunna läggas ihop till en triangel och olika trianglar finns det färst av. Det vill säga, vi bör i princip pröva att skära itu spetsiga trianglar (såna som har alla vinklar mindre än 90°), trubbiga trianglar (såna som har en vinkel större än 90°) och också pröva med rätvinkliga trianglar.

Här nedan är Oves lösning (jag borde ha någon sorts topplista för att beröma honom). Han poängterade för mig att han löste det hela i stort sett med ”trial & error”-metoden. Och det är så konstruktionsproblem oftast löses.