300 dvärgar ska gå över en bro mitt i polarnatten. Bron är ranglig och klarar av som mest två dvärgar i taget. Med sig har de en lykta som de måste ha med vid varje övergång. Dvärgarna behöver olika tid för att gå över bron: 1 min, 2 min, 3 min … respektive 300 min. När två dvärgar går över, så går de med den långsammastes hastighet. Ingen dvärg vill gå över bron fler än 3 gånger (dvs fram-tillbaka-fram). Vilken är den minsta tiden de klarar övergången på?
De kan göra det på 89551 minuter om de gör så här:
(1,2) går över
(1) går tillbaka
(3,4) går över
(2) går tillbaka
(5,6) går över
(3) går tillbaka
(7,8) får över
(4) går tillbaka
.
.
.
(299,300) går över
(150) går tillbaka
(1,2) går över
(151) går tillbaka
(3,4) går över
(152) går tillbaka
.
.
.
(295,296) går över
(298 går tillbaka)
(297,298) går över.
Alla är över!
Då har det tagit 1+2+3+4+…+298 = 44551 minuter att gå tillbaka, en i taget. Och det har tagit 2+4+6+…+298+300+2+4+6+….+298 = 22650 + 22350 = 45000 minuter att gå över. Totalt har det tagit 89551 minuter.
Vi motiverar varför det inte går att göra detta på kortare tid om man följer reglerna.
Varje gång lyktan går över-tillbaka är det max två dvärgar som går över och minst en som går tillbaka. Det betyder att lyktan går över-tillbaka minst 298 gånger, för att antal dvärgar på andra sidan ökar med max 1 per gång. I sista steget kan två dvärgar gå över och då får vi möjligheten att alla 300 dvärgarna är på andra sidan.
Det betyder att (minst) 298 gånger var det någon som gick tillbaka. En och samma dvärg kunde inte ha gått tillbaka flera gånger, för då skulle hen ha passerat bron minst fem gånger i slutändan. Alltså var det olika vaje gång. Övergångarna tillbaka tog alltså minst 1+2+3+4+…+298 = 44551 minuter.
Säg att dvärgarna skulle gå över själva varje gång och inte i par. Då skulle det ha tagit 2*(1+2+3+…+298)+299+300 = 89701 minuter. Men en del av den tiden kan besparas genom att dvärgarna går i par. Det är den snabbaste dvärgens tid som besparas.
I varje par som går över är den spenderade tiden minst 1 minut större än den besparade tiden. Så i alla paren tillsammans är den spenderade tiden minst 299 minuter större än den besparade tiden.
Antag att dvärgarna spenderade som mest 44999 minuter på att gå över. Då skulle de ha besparat som minst 89701-44999 = 44702 minuter. Men 44999 är bara 297 större än 44702, alltså får vi en motsägelse.
Det betyder att dvärgarna spenderade minst 45000 minuter på att gå över och totalt spenderade alltså minst 45000+44551 = 89551 minuter.
Tack för fin blogg. Försöker ta igen matte för att hjälpa min dotter med matten.
Men att skriva om 300 dvärgar är inte alls passande. Byt ut till 300 feta barn, 300 personer med funktionsvariationer, eller något annat, inget av detta är kul. Jag lovar, ingen dvärg skulle tycka detta vore kul. Annars, en superbra blogg!
Detta är en dvärg: https://sv.wikipedia.org/wiki/Dv%C3%A4rg_(fantasy) Det du syftar på kallas för en kortväxt person.
Åh, tack för info! Då ska jag ändra i min vokabulär. Jag ska även prata med mina barn och tala om att de som är kortväxta just kallas kortväxta, inget annat. Tack. God jul!
Men snälla någon…
Dvärg här är ju inte knutet till mänskliga fenomen utan snarare sagoväsen, tänk Snövit eller Sagan om ringen osv.
Dessutom är det högst motsägelsefullt att först klaga på dvärg och sen själv använda det 300 bajsnödiga föräldrar går över en bro skulle vara mer passande då ?
Dvärgar finns i sagor och de jobbar i gruvor punkt slut ?
Javisst, som jag skrev tidigare, har uppdaterat min vokabulär.