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.
