Homepage
Novemberproblemen 2002
1. Ett mycket litet kungarike har formen av en kvadrat med sidan 30 km. Riket har fyra små städer, en i varje hörn, men inga moderna vägar. Rita ett vägnät som binder samman de fyra städerna. Kungen har pengar till högst 82 km väg.
2. Lille Martin sitter och leker med lego-klossar. Han har klossar i fyra olika färger och med hjälp av dessa roar han sig med att bygga 24 olika torn, som alla består av fyra olikfärgade klossar. Då kommer pappa Anders in och funderar: Om man istället bygger ett högt torn, där alla de 24 småtornen kan återfinnas någonstans i det höga tornet, så borde man kunna göra det med betydligt färre klossar. Vilket är det minsta antalet lego-bitar som behövs till ett sådant torn?
Lösningar
1. Låt L vara den totala vägsträckan i km. Ett bra försök är att binda samman hörnen med ett kryss. Det ger den totala vägsträckan
Inte tillräckligt bra alltså (sqrt(2) betyder kvadratroten ur 2). Ett bättre försök visas i figuren nedan.
Uppenbarligen gäller här L = 4*a + b. Med hjälp av pythagoras sats kan b och därmed också L uttryckas som en funktion av a
Om vi väljer a = 17 så får vi b = 14 och L = 82, dvs en tillräckligt bra lösning. Genom att lösa ekvationen L(a) = 82 hittar man också lösningen a = 53/3. En undersökning av derivatan L'(a) visar att L(a) < 82 då 17 < a < 53/3. Den optimala lösningen
erhålls då L'(a) = 0. Det inträffar för
Då gäller också u = v = 120o, dvs alla tre vinklar kring en trekorsning är lika.
/Jonas
2. Först kan man konstatera att problemet går att lösa med 33 stycken klossar på följande sätt:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| + | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 |
Det är lätt att kontrollera att alla de 24 småtornen finns med.
Går det att klara med färre klossar? Det bästa vore om man fick ett nytt småtorn för varje påbyggd kloss, så att det bara blir 27 (24 + 3 startklossar) stycken bitar i tornet. Tyvärr går inte detta eftersom det blir upprepningar, tex efter 7 steg,
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
vill man bygga på med en blå bit, men det småtornet man då får finns redan med allra först, så det går inte skapa ett nytt småtorn här, utan man får en "lucka". Om man istället fortsätter med en röd kloss (enda möjligheten om inte luckan ska bli längre), går det bra ända tills man kommer till nivå 13, där det blir en ny lucka, osv.
Nu kunde man hoppas att det åtminstopne går med 32 bitar (24 + 3 + 5 luckor) men det återstår ett problem: Vid nivå 18 hjälper inte en lucka, 18: grön och 19: blå gör att man kommer tillbaka till det första småtornet, så man måste ta till ännu en lucka för att bryta repetitionen. 33 klossar en därmed det minsta antalet.
/Erik
Sidansvarig: jana.bjorn@liu.se
Senast uppdaterad: 2019-12-03