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.
Relaterade
