0
$\begingroup$

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?

$\endgroup$
4
  • 4
    $\begingroup$ Really, both of these are too specific, and should be replaced with a question about the (2^n)-1 link chain. :P $\endgroup$
    – Patrick N
    Commented Oct 8, 2015 at 21:40
  • 3
    $\begingroup$ "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?" $\endgroup$
    – dr_
    Commented Oct 8, 2015 at 21:45
  • 1
    $\begingroup$ @PatrickN I'd vote to keep this open for an answer to the general problem. Probably better as a new question, though. $\endgroup$
    – Mythi
    Commented Oct 8, 2015 at 22:31
  • $\begingroup$ Is it possible to prove that the chosen answer is optimal ? In general, it does seem that the intuitive approach is to divide a chain that is 2^n -1 links long into units of length 1, 2, 4, ..etc. But, how do we prove that it is the optimal division ? $\endgroup$ Commented Jul 6, 2021 at 23:29

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.