OlympiadMediumCombinatorics5–6

Cutting the Gold Chain

Cortar a Corrente de Ouro

A traveller pays for $7$ nights with a chain of $7$ gold links, one link per night. Each morning the innkeeper must hold exactly as many links as nights already slept — no more, no less — but he may give change from links he already holds. What is the smallest number of links the traveller has to cut open?

Change may come back, so the traveller does not need a piece for every night — only pieces whose sizes can build every total from $1$ to $7$ .

Solution

Step 1 of 9

1.Cut open only the third link. The chain falls into three pieces: the single opened link, a piece of $2$ and a piece of $4$ .