Problem om att ta sig över till andra sidan


Året var 1997. Det var då jag började ha matematiska framgångar och blev därmed skickad på en resa till den stora staden Moskva. Där skulle jag och andra 6:or och 7:or tävla i problemlösning. Som jag minns det gick det hyfsat ok för mig, men ett problem kunde inte de flesta deltagarna lösa:

En familj kommer fram till en bro mitt i natten. Pappan kan gå över bron på 1 minut, mamman – på 2 minuter, barnet – på 5 minuter och mormorn – på 10 minuter. De har bara en lykta. Bron håller bara för två personer åt gången. Hur ska alla ta sig över till andra sidan på 17 minuter? (Om två personer går över samtidigt, går båda lika snabbt som den långsammaste av dem. Man får inte gå på bron utan lyktan. Man får inte lysa långt bortifrån. De får inte bära varandra.)

Ännu tidigare i min matematiska karriär hörde jag talas om problemet om Bonden och hans ägodelar:

En man ska ta sig över en å i en roddbåt. Han medför en varg, en get och ett kålhuvud. Han kan inte ta med sig mer än en av ägodelarna åt gången. Vargen kan inte lämnas ensam med geten och geten kan inte lämnas ensam med kålhuvudet. Hur skall mannen bära sig åt för att klara övergången?

Kanske vet du lösningen, kanske inte. Det är roliga är att numera finns problemet i form av ett spel!

Prova även att få över missionärer och kannibalen till andra sidan. Båten rymmer två, men blir det fler kannibaler än missionärer på någon sida, blir missionärerna uppätna.

Och till slut kan du prova att få över familjen med lyktan på andra sidan. Den här familjen är dock lite större än i problemet i början, och har lite annorlunda tider. Men illustrationen till problemet är suverän.

Alla ni som tyckte om problemen om familjerna, kan försöka lösa det generella fallet. Vilket är den minsta tiden att ta alla över till andra sidan, om familjen har n medlemmar som tar sig över på a_1, a_2, \ldots, a_n minuter där a_1\leq a_2\leq\ldots\leq a_n?

13 reaktioner till “Problem om att ta sig över till andra sidan”

  1. Är det ens möjligt? Jag vet ett enkelt sätt att få över alla på 19 minuter, men 17? Hur ska det gå till?

  2. Spoiler: Det gäller att komma på att när den långsammaste går över, så kan man passa på att gå över med den näst långsammaste samtidigt, ty det ändå går på samma tid.

  3. Jaha, nu fattar jag. Jag har löst den. :D Tack för tipset! Då får vi gå på problemet med fem personer och generaliseringen. ;)

  4. Ja du, det generella fallet är nog betydligt svårare. En tanke är att hitta en algoritm för att ta över personerna, och sedan bevisa att det är den effektivaste, samt med hjälp av den beräkna tiden. För att konstruera algoritmen, måste vi iaktta för vilka värden det är värt att låta den långsammaste personen gå med den snabbaste och för vilka värden den bör ta med sig den näst långsammaste. Naturligt skulle vara, om det fanns en brytpunkt, ett förhållande mellan deras tider, där det ena fallet blir snabbare än det andra. En sådan går nog att hitta med hjälp av ett datorprogram, fast sedan återstår det fortfarande att bevisa att det är det effektivaste. Det kanske går med hjälp av tricotami och motsägelse.

  5. Ta hjälp av Toomas ledtråd och tänk lite till. ;) Den näst långsammaste ska över samtidigt som den långsammaste. Vem ska springa tillbaka med lyktan?

  6. Trikotami betyder treskärelse, och innebär att ett uttryck alltid är mindre än, lika med eller större än ett annat. Man borde kunna visa detta med hjälp av urvalsaxiomet. Detta kan användas för att bevisa saker och ting, genom att finna motsägelser i alla olika fall förutom det rätta. Ett bra problem som utnyttjar det här är finalproblem sex från Högstadiets Matematiktävling 2002/2003.

  7. Skoj! Skulle sitta uppe och läsa
    om musikestetik men nu grubblar jag över
    bonden och hans ägodelar.

    Hade ett spel som barn med ett liknande problem
    Spelplanen föreställde en bondgård där olika
    djur hade problem med varandra. Spelplanen var
    delad i ett antal delar som man skulle lägga
    så att inte djur som bråkade hamnade
    bredvid varandra.

    Minns inte vad spelet hette exakt dock
    men jag tror det är en klassiker

    /sofia.

  8. Pappan=1minut , Mamman=2minuter barnet=5minuter mormor=10minuter
    först som ska gå över bron med lycktan är Pappan och mamman = 2minuter sedan pappan går tillbaka med lycktan= 1minut
    andra som ska gå över bron med lycktan är barnet och mormor=10minuter sedan mamman går tillbaka med lycktan=2minuter
    tredje som ska gå över bron är pappan och mamman med lycktan= 2minuter totalt blir 17minuter.

Kommentera