A traveler wants to stay at an inn for seven days. He has no money, but he has a gold chain with seven links. The innkeeper agrees to accept this in payment for the week’s stay, but the traveler is reluctant to part with all seven links at once. He prepares to cut the chain into seven pieces.
The innkeeper stops him. If the traveler is willing occasionally to accept change in the form of links previously paid, then they can work out a plan that minimizes damage to the chain and yet permits the traveler to pay only what he owes on each successive day. How many links must they cut?