Installment Plan - Futility Closet

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?

	Select Click for Answer
They cut a single link, the third one, dividing the chain into lengths of 1, 2, and 4. Now: On day 1 the traveler gives the innkeeper 1 link. On day 2 the traveler gives the innkeeper 2 links and accepts 1 in return. On day 3 the traveler gives the innkeeper 1 link. On day 4 the traveler gives the innkeeper 4 links and accepts 3 in return. On day 5 the traveler gives the innkeeper 1 link. On day 6 the traveler gives the innkeeper 2 links and accepts 1 in return. On day 7 the traveler gives the innkeeper 1 link. (In effect they’re counting in base 2.)

Click for Answer