Bruten kedja

Du har en halskedja i tio bitar med 9, 8, 6, 6, 6, 4, 4, 3, 2 och 2 länkar per bit. Juveleraren som ska sätta ihop kedjan tar 4 kronor för att öppna en länk och 10 kronor för att stänga en. Men du vill betala högst 100 kronor. Räcker det eller måste du hitta en annan utväg?

Facit: Bruten kedja

Om man öppnar en länk i ena änden av varje bit och kopplar biten med nästa kostar det 10x(4+10) = 140 kronor. Det blir billigare att öppna alla länkar i den längsta biten och sätta ihop hela kedjan med dessa. Kostnad: 9x(4+10) = 126 kr. Men billigast är att öppna länkarna i de tre kortaste bitarna och sätta ihop kedjan med dem. Kostnaden blir 7x(4+10) = 98 kr.