Kinesys lands on Abakos with a dead engine and a navigator cheerfully flashing the wrong destination. To reach the nearest repair shop, seven days away, Liz has to rent a rocket sled.
The Abakian rental agent, however, doesn’t take galactic credits: he wants to be paid in barter, one gold link a day for each of the seven days. All Liz owns is a seven-link gold chain, an old family heirloom, and she would like to damage it as little as possible.
Dord finds breaking even a single link outrageous: “A chain is a closed and perfect system!” M00N gently points out that this chain isn’t even closed.
The Riddle
Liz owns a gold chain made of seven links, open at both ends (not joined into a loop). She has to rent a rocket sled for seven days, and the rental agent wants to be paid with the gold chain: one link a day for each of the seven days. What is the smallest number of links she must break to make this possible?
And what if the chain had 30 links and the rental lasted 30 days?
Hint
The rental agent can give pieces back: all that matters is that each evening he holds one more link than the evening before. Which piece lengths let you make every number from 1 to 7?
Solution
The problem is solved by breaking just one link: the third one. This gives a single link (the third), a two-link piece (the first and second), and a four-link piece (the fourth through the seventh). With these three pieces you can make every number from one to seven.
The key is that the agent must hold one link on the first day and, on each following day, one link more: he doesn’t need to receive a new link every day, because he can give pieces back. In practice:
- on day one, Liz hands over the single link;
- on day two, she hands over the two-link piece and gets the single link back;
- on day three, she adds the single link again;
- on day four, she hands over the four-link piece and gets the other three back;
- and so on, until on day seven she has handed them all over.
The usual stumbling block is taking “one link a day” literally, without considering that pieces can be given back.
For 30 links over 30 days, the solution is to break links 3, 9, and 21. This yields pieces of 1, 1, 1, 2, 5, 9, and 11 links: combined in the right way, they can make every number from 1 to 30.