This question already has an answer here:
- The seven piece silver chain 1 answer
A traveling woman arrives in a new city. She enters the hotel of the main street and tells the innkeeper:
"I need to rent a room for 15 days. Unfortunately I have no money with me, however I own this jewelry that I can pawn to you right now." Saying so, she produces a gold chain composed of 15 identical links:
"Every link is pure gold; surely each one of these is sufficient to cover the cost of one night in your hotel. In 15 days I'll meet someone that owes me a large sum of money. Then I'll be able to pay you and I'll take back my chain."
"Well, young lady," replies the innkeeper "a pawn is fine, but I can't take the responsibility of keeping such a precious object for a long time. I'll tell you what we do. You keep the chain, but you leave me one golden link each day as security. After 15 days you pay me the room with the money you got, and I'll give you back the 15 links."
The woman stays pensive. She'll need a goldsmith to cut her chain, and the goldsmith will ask some money for each link he has to cut and to weld afterwards. Therefore it's better to cut as less links as possible.
After a moment, she finds the solution. What's the smallest number of cuts?
Note: one reader correctly pointed out a similar question with 7 links. How do you solve the problem for 15 links?