# The golden chain [duplicate]

This question already has an answer here:

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:

ooooooooooooooo

"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?

## marked as duplicate by JonTheMon, Engineer Toast, Player One, Len, Cristian MarianOct 9 '15 at 6:45

• Really, both of these are too specific, and should be replaced with a question about the (2^n)-1 link chain. :P – Patrick N Oct 8 '15 at 21:40
• "I have this 4095-link chain, and I need to rent a room for the next 11 years and something. How do I make ten cuts to the chain?" – dr01 Oct 8 '15 at 21:45
• @PatrickN I'd vote to keep this open for an answer to the general problem. Probably better as a new question, though. – Mythi Oct 8 '15 at 22:31

You need to make

2 cuts

severing the chain into lengths of

1, 2, 4, and 8. That is, one cut to break into 6, 1, and 8, and then a second cut to break 6 into 2 and 4. I'd enumerate the different combinations, but thanks to binary math, we know that any number less than a given positive power of two can be formed by some sum of all the smaller positive powers of two.