You want to stay at an inn for seven nights. You only have a gold chain with seven links. The innkeeper agrees to accept this in payment for the stay, but you only want to pay for one night at a time.
You start to cut a link, but the innkeeper wants you to minimize the damage to the chain. What is the minimum number of cuts you must make, provided the provided the innkeeper is happy to return previously given links as change?
This is possible in one cut.
Cut a single link, the third one, dividing the chain into lengths of 1, 2, and 4. Then follow this day-by-day plan:
- Give 1 link.
- Give 2 links, get 1 link as change.
- Give 1 link.
- Give 4 links, get 3 links as change.
- Give 1 link.
- Give 2 links, get 1 link as change.
- Give 1 link.
This is equivalent to counting in binary.