Mattebloggen

Problem vecka 13

Kaniner (1 poäng).
En kaninmamma köpte 7 olika stora trummor och 7 olika stora trumpinnar-set åt sina 7 kaninbarn. Om en kanin ser att någon av syskonen har både mindre trumma och mindre trumpinnar, börjar den slå på trumman väldigt högt. Annars sitter kaninen tyst.

Vad är det största antalet kaniner som kan trumma högt?

Staket (3 poäng). I en liten stad finns 100 hus. Man får bara bygga slutna staket som omringar åtminstone ett hus. Olika staket får inte korsa varandra. Man får aldrig bygga flera staket som omsluter samma samling av hus.

Vilket är det största antalet staket som kan finnas i staden?

Visa lösningar

Kaniner (Toomas lösning):
Det optimala fallet är att alla kaniner trummor högt, de vill säga sju stycken. Den med minst trumma och trumpinne kan dock inte trumma högt, enligt villkoren. Nästkommande fall är då att sex kaniner trummar högt. Vi ser att detta går att göra, genom att ge den minsta trumman och de minsta trumpinnarna till en kanin, de näst minsta trumman och de näst minsta trumpinnarna till en annan kanin, och på detta sätt fortsätta, tills alla har en trumma och ett par trumpinnar. Alla utom kaninen med den minsta utrustningen kommer då trumma högt.

Staket (Skäggets lösning):
Vi låter ett stakets storlek beteckna antalet hus det innesluter, och S(n) får beteckna det maximala antalet staket som kan byggas i en stad med n hus. I ett sådan staketuppsättning observerar vi att bland annat varje enskilt hus ett staket runt bara sig.

I en stad med n hus kan vi alltid bygga ett till hus precis bredvid något annat (det vill säga så att inget staket finns mellan dem). Vi kan då bygga ett staket runt enbart det nya huset och ett staket runt det nya huset och dess granne. Alltså är S(n+1) större eller lika med S(n)+2.

Antag att S(n+1) är större än S(n)+2. Betrakta då en stad med n+1 hus och en maximal staketuppsättning, och bortse från alla triviala staket av storlek 1. Vi väljer där ett staket av minimal storlek. Detta måste vara storlek 2, ty annars kan vi välja 2 hus innanför staketet och bygga ett nytt staket som innesluter dem. Vi river att av de 2 hus det innesluter. I och med detta måste vi riva de staket av storlek 1 som innesluter de båda husen var för sig, ty annars bryter vi mot staketreglerna att inget staket får vara tomt och att inga två staket får innehålla samma samling hus (vårt staket av storlek 2 blir ju nu ett staket av storlek 1). Alltså har vi en uppsättning staket i en stad med n hus som innehåller S(n+1) – 2 hus. Men eftersom S(n+1) antagits vara större än S(n)+2 innebär detta att vi har fler staket än S(n) i vår stad med n hus, vilket motsäger vår definition av S(n).

Alltså har vi likhet: S(n+1) = S(n)+2. En stad med ett enda hus kan bara ha ett staket, och således är S(1) = 1. Vi får alltså att S(n) = 1 + 2(n-1) = 2n – 1.

För 100 hus gäller alltså att maximalt 2*100 – 1 = 199 staket kan byggas i enlighet med de angivna reglerna.

Problem vecka 12

Syskon (1 poäng). I en familj finns sex barn. Fem av barnen är 2, 6, 8, 12 respektive 14 år äldre än det minsta barnet. Alla åldrarna i familjen är primtal. Hur gammalt är det minsta barnet?

Primtal

Ett primtal är ett positivt heltal som har exakt två delare: 1 och talet självt.

Till exempel är 2, 3, 5 och 7 primtal.

Men 1, 4, 6, 8 och 9 är inte primtal: 1 har endast en delare (1), 4 har tre delare (1, 2, 4), 6 har fyra delare (1, 2, 3, 6), 8 har fyra delare (1, 2, 4, 8) och 9 har tre delare (1, 3, 9).

Sannolikheter (3 poäng). Två vänner singlar slant: den första singlar 10 gånger och den andra singlar 11 gånger. Hur stor är sannolikheten att den andra vännen får klave fler gånger än den första vännen?

Visa lösningar

Problem vecka 11

Nu kommer de svåraste problemen hittills! Nästa vecka återkommer jag till normal svårighetsgrad.

Skicka in lösningsförslag genom att klicka på länken under uppgifterna senast måndagen den 28 mars. Glöm inte att kolla reglerna och aktuella poängställningen.

Punkter (3 poäng). Sätt ut så många punkter på ett papper som möjligt, på så sätt att ingen trippel av punkter ligger på en och samma linje, utan utgör hörn till en likbent triangel. Du behöver inte bevisa att det inte går att sätta ut fler punkter med samma egenskap.

Likbent triangel

En likbent triangel är en triangel med två lika stora vinklar. En ekvivalent definition är att det är en triangel som har två lika stora sidor.

Här är några exempel:
Likbenta trianglar
Notera att en liksidig triangel är också likbent.

Trasig våg (7 poäng). Du har 3^2k mynt som ser likadana ut, men bland dem finns ett falskt mynt som väger lite mindre än alla andra. Du har också tillgång till tre balansvågar (varje balansvåg har två skålar). Du vet att två vågar är i gott skick, men en är trasig och du vet inte vilken det är. Den trasiga vågen kan visa både jämvikt och ojämvikt åt ena eller andra hållet oberoende av vad du lägger på skålarna.

Hur bestämmer du vilket mynt som är falskt på 3k+1 vägningar?

Visa lösningar

Punkter (Arvids lösning):
Det maximala antalet punkter är 6 i form av en liksidig pentagon (femhörning) med en sjätte punkt mitt i centrum av pentagonen.

Trasig våg (Davids lösning): vi börjar med k=1, alltså 9 mynt och 4 vägningar. Jag ser det som välkänt (för matteintresserade) hur man hittar det falska myntet bland 3^n mynt på n vägningar med en fungerande våg. Observera att om två vågar påstår samma sak så måste påståendet vara sant. Om två vågar motsäger varandra måste en av dessa vara trasig, så den tredje vågen fungerar.

Lägg mynten i 3×3-formation. Väg första raden mot andra i våg 1. Väg första kolumnen mot andra i våg 2. Nu har vi ett misstänkt falskt mynt, i rad A kolumn B säger vi. Vi kan kalla myntet AB :) Vår tredje vägning blir (rad A men inte kolumn B) mot (kolumn B men inte rad A) i våg 3.

Om (rad A men inte kolumn B) visas som lättast: våg 2 säger att falska myntet finns i kolumn B men våg 3 säger att det inte finns i kolumn B. Motsägelsen visar att våg 1 fungerar, falska myntet finns alltså i rad A och med vår sista vägning kan vi hitta det falska myntet bland de tre kandidaterna.

Om (kolumn B men inte rad A) visas som lättast: på samma sätt vet vi att våg 2 fungerar och kan hitta det falska myntet med vår sista vägning.

Om jämvikt visas: det finns tre alternativ på vilka två vågar som fungerar. Om 1 och 2 fungerar är AB såklart falskt. Om 1 och 3 fungerar vet vi att det falska myntet finns i (rad A men inte (rad A men inte kolumn B)), en mängd bestående endast av AB. Om 2 och 3 fungerar får vi också AB som falskt. Alltså måste AB vara falskt och vi har endast använt tre vägningar.

Slutsats: antingen har vi hittat myntet på tre vägningar eller så har vi hittat en fungerande våg och kan använda den för att hitta myntet på den fjärde vägningen. Så för k=2 kan vi stapla mynten i högar om 9. Har vi hittat den falska högen efter tre vägningar så kan vi hitta det falska myntet på resterande 4 vägningar. Annars blir det lätt med hjälp av den fungerande vågen. Vi kan fortsätta med samma princip upp till godtyckligt höga värden på k.

För godtyckligt k=p, stapla i högar om 3^(2p-2). Om vi hittar den falska högen på tre vägningar har vi reducerat problemet till k=p-1. Annars har vi en fungerande våg, vi har 3p-2 vägningar kvar (vilket är större än 2p för p>2) och 3^(2p) mynt att väga = lätt.

Prinsessan eller tigern? Dag 2

Den här interaktiva berättelsen har skrivits av Raymond Smullyan och ingår i boken ”The Lady or the Tiger?” Översättningen till svenska är min egen.

Gå till första kapitlet

Dag 2

”Igår gjorde vi bort oss”, sade kungen till sin rådgivare, ”alla tre klarade sig! Nåväl, idag har jag ytterligare fem, och jag kommer att hitta på något värre åt dem!”
Rådgivaren visade sitt stöd: ”En lysande idé, ers majestät!”

Denna dag hade kungen alltid densamma instruktion angående det första rummet: ”Om en prinsessa finns i rummet, är skylten på dörren sann, däremot om en tiger sitter där, är skylten falsk.”

På det andra rummet var allting tvärtom. Om en prinsessa satt där, var påståendet på skylten falskt och ifall det var en tiger, var det sant.

Återigen är det fullt möjligt att i båda rummen finns prinsessor eller att båda innehar tigrar eller att ett har en princessa och ett har en tiger.

Fjärde prövningen
Kungen förklarade reglerna för nästa fånge och pekade på två nya skyltar:

I
I båda rummen finns prinsessor

II
I båda rummen finns prinsessor

Vilket rum borde fången välja?

Visa svaret

Femte prövningen
Samma förutsättningar, men med dessa skyltar:

I
Åtminstone i ett av rummen finns en prinsessa

II
En prinsessa sitter i det första rummet

Visa svaret

Sjätte prövningen
Denna gåta var kungen särskilt stolt över, liksom gåtan därefter.

I
Vad du väljer spelar ingen roll

II
En prinsessa sitter i det första rummet

Visa svaret

Sjunde prövningen
Nu stod det:

I
Vad du väljer spelar stor roll

II
Det är bäst att välja det första rummet

Visa svaret

Åttonde prövningen
”Det finns ju inga skyltar på dörrarna!”, utropade fången.
”Helt korrekt”, sade kungen, ”de tillverkades precis och man hann inte sätta upp dem.”
”Hur ska jag då välja?”, frågade fången.
”Här har du skyltarna”, svarade kungen.

En tiger sitter i det här rummet

Tigrar sitter i båda rummen

”Vad trevligt”, sade fången oroligt, ”men vilken ska sitta var?”.
Kungen tänkte en stund.
”Det behöver du inte nödvändigtvis veta”, sade han till slut. ”Du kan lösa problemet ändå. Kom ihåg förstås att en prinsessa i första rummet innebär att påståendet på skylten är sant och en tiger i samma rum innebär att påståendet är falskt. För det andra rummet är allt tvärtom”, tillade han.

Vad är lösningen på problemet i så fall?

Visa svaret

Gå till tredje kapitlet

Problem vecka 10

Skicka in lösningsförslag genom att klicka på länken under uppgifterna senast måndagen den 21 mars. Glöm inte att kolla reglerna och aktuella poängställningen.

Blommor (2 poäng). Längs med vägen mellan Kalles och Kajsas stugor växte blommor på rad: 15 prästkragar och 15 tussilago huller om buller. När Kajsa var på väg till Kalle, vattnade hon alla blommor i rad. Men efter den 10:e tussilagon tog vattnet slut och 10 blommor förblev ovattnade.

Nästa dag gick Kalle hem till Kajsa och plockade blommorna i rad. Efter den 6:e tussilagon tyckte han att buketten var lagom stor. Hur många blommor fick växa kvar längs med vägen?

Familjealbum (5 poäng). I ett familjealbum finns 10 foton. Varje foto föreställer tre personer: i mitten står en man, på hans vänstra sida har han sin son och på hans högra sida har han sin bror.

Alla männen som står i mitten är olika personer. Vilket är det minsta antalet olika människor som kan finnas på bilderna i albumet?

Visa lösningar

Blommor (Daniels lösning):
Eftersom det sammanlagt finns 30 blommor (15+15) och efter den 10:e tussilagon så finns det 10 blommor kvar på raden. Kvar finns där 5 tussilagos och 5 prästkragar på raden. När Kalle plockar den 6:e tussilagon från andra hållet så blir det alltså samma tussilago som den 10:e från Kajsas håll.

De tio blommorna som är kvar efter den 10:e från Kajsas håll + den tionde tussilagon blir 10+1=11 blommor i buketten och 30-11=19 blommor kvar på raden.

Familjealbum (Johans lösning): Vi kan anta att på varje bild så är sonen den äldste sonen, och brodern den ”ett steg yngre” brodern (där den ett steg yngre bordern till den yngsta brodern i en grupp är det äldsta syskonet). Vi kan också anta att för varje broderssyskonskara som är med så är alltid det äldsta syskonet med som fader på något foto.

Antag att det går att skapa ett sådant familjealbum med endast 15 personer. På varje foto förekommer 2 typer av ”relationer”, nämligen X är äldste sonen till Y och X är ett steg yngre brodern till Y. Mellan två personer X, Y så kan endast en av dessa relationer försigkomma. Totalt så har vi 20 relationer i bilden.

Vi ritar en graf med de 15 personerna som noder och vi bildar kanter där vi har en relation (vi kan anta att grafen är sammanhängande). Ifall vi inte ritar ut relationerna där den äldste brodern anses ett steg yngre än den yngste så har vi en riktad graf utan loopar, dvs ett träd. Ett träd med 15 noder har 14 kanter.

Vi behöver alltså 6 relationer till. Dessa kan nu bara komma från yngste->äldste brodersrelationer, och vi kan bara få en sådan från varje syskongrupp. Vi måste alltså ha minst 6 syskongrupper, där varje person i syskongruppen är avbildad som fader på något foto (pga relationsegenskapen). En sådan grupp måste bestå av minst 2 personer. Då har vi minst 12 personer som är fäder på något foto. Detta motsäger att vi har 10 foton.

Här är exempel på ett släktträd med 16 män:

Ovanlig sudoku

Försök att lösa! Som vanligt ska varje stor ruta, varje rad och varje kolumn innehålla alla 9 siffrorna en gång var.

Rebus

Problem vecka 9

Skicka in lösningsförslag genom att klicka på länken under uppgifterna senast måndagen den 14 mars. Glöm inte att kolla reglerna och aktuella poängställningen.

Rebusen (1 poäng). Försök att läsa av ordet genom att använda nyckeln:
Rebus

Schackcirkeln (3 poäng). Det finns ett vanligt schackbräde med storleken 8×8. Hur stor radie har den största cirkeln man kan rita, som bara går igenom svarta rutor (det vill säga cirkelns rand finns aldrig i de vita rutornas inre)? Visa varför det inte går att hitta en större sådan cirkel.

Visa lösningar

Prinsessan eller tigern? Dag 1

Den här interaktiva berättelsen har skrivits av Raymond Smullyan och ingår i boken ”The Lady or the Tiger?” Översättningen till svenska är min egen.

Frank R. Stockton skrev en saga som heter “Prinsessan eller tigern?”. I sagan måste en fånge gissa, i vilket av rummen finns en prinsessa och i vilket en tiger. Om han gissar rätt rum, får han gifta sig med prinsessan. Om han gissar fel, kan tigern döda honom.

I ett kungarike bodde en kung. Han läste sagan och blev inspirerad. “Det här passar precis för mina fångar!”, sade han till sin rådgivare. Men jag vill inte lita på slumpen. Låt varje rum ha en skylt och säg någonting om skyltarna till fången. Om han inte är dum och kan resonera logiskt, kommer han inte bara ut med livet i behåll utan blir också gift med en vacker prinsessa! “Utmärkt idé, ers majestät!”, sade rådgivaren.

Dag 1

Den allra första dagen genomfördes tre prövningar. Kungen förklarade för fångarna om att det i varje prövning kommer finnas en prinsessa eller en tiger i varje rum. Det kan dock mycket väl hända att det finns en tiger i båda rummen eller att båda innehåller princessor.

Första prövningen
“Men vad händer, om båda rummen innehåller en tiger?”, frågade fången, “vad gör jag då?”
“Då har du otur”, svarade kungen.
“Om båda har en skönhet då?”, undrade fången.
“Då har du mycket tur”, sade kungen, “det hade du kunnat tänka ut själv!”
“Okej, men vad händer om ena rummet har en prinsessa och det andra en tiger?”, fortsatte fången undra.
“Då beror det bara på dig, eller hur?”
“Men hur ska jag veta vilket rum som har vad?”, suckade fången förtvivlat.
Då visade kungen på skyltarna som fanns på var sin dörr. Det stod:

I
I det här rummet finns en prinsessa och i det andra rummet sitter en tiger

II
I ett av dessa rum finns en prinsessa; dessutom, i ett av dessa rum sitter en tiger

“Är det sant, det som står här?”, frågade fången.
“Den ena skylten är sann, den andra är inte det”, svarade kungen.

Vilken dörr skulle du öppna om du var fången? (Om du föredrar en prinsessa framför en tiger förstås).

Visa svaret

Andra prövningen
Den första fången räddade sitt liv och lämnade fängelset lycklig tillsammans med sin prinsessa.
Skyltarna byttes då ut och rummen fick nya invånare. Nu kunde man läsa följande på skyltarna:

I
Åtminstone i ett av rummen finns en prinsessa

II
En tiger sitter i det första rummet

“Är det sant, det som står på skyltarna?”, undrade den andra fången. “Kanske är båda skyltarna sanna, kanske är båda falska”, svarade kungen.
Vilket rum borde den andra fången välja?

Visa svaret

Tredje prövningen
Även denna prövning sade kungen att antingen båda skyltarna stämde eller att båda var falska. Skyltarna sade:

I
Det sitter en tiger i det här rummet eller så sitter en prinsessa i det andra rummet

II
En prinsessa finns i det första rummet

Vem sitter i det första rummet, en prinsessa eller en tiger? I det andra rummet då?

Visa svaret

Gå till andra kapitlet

Mattebloggen

Problem vecka 13

Visa lösningar

Problem vecka 12

Primtal

Visa lösningar

Problem vecka 11

Likbent triangel

Visa lösningar

Prinsessan eller tigern? Dag 2

Dag 2

Problem vecka 10

Visa lösningar

Ovanlig sudoku

Problem vecka 9

Visa lösningar

Prinsessan eller tigern? Dag 1

Dag 1

Problem vecka 8. Tävlingsstart!

Visa lösningar

Lektion om potenser