A traveler owing a gold chain with 7 links is accepted at an inn on condition that he pay one link of the chain for each day he stays. if the traveler is to pay daily and may be given links already used in payment as change, show that he only needs to take out one of the links of the chain in order to pay each day for 7 days. (note: if he takes out the nth link he has 3 pieces of lengths i-1,1,7-i.)
Can you generalize this to n links? - how many links does he need to take out to pay for n days ?
This is a very famous logic puzzle and its solution is given below:
Remove the third link. You have 3 pieces with lengths 1,2,4:
On the first day he gives the innkeeper 1 link.
On the second day he takes one link back from the innkeeper and gives him 2 links.
On the third day he gives the innkeeper 1 link.
On the fourth day he takes back 3 links and gives the innkeeper 4 links.
On the fifth day he gives the innkeeper 1 link.
On the sixth day ...
Chain breaking puzzles are analyzed. The links of the chain are examined.