Gold Links Puzzle


Source: Alok Goyal (Stellaris VP) puzzle blog

Problem:

This is another famous puzzle in the Martin Gardner collection, and variations of this puzzle exist in different “sizes”. This particular one has been picked up from The Colossal Book of Short Puzzles and Problems, Puzzle 9.18. Replicating the puzzle as is.

Lenox R. Lohr, president of the Museum of Science and Industry in Chicago, was kind enough to pass along the following deceptively simple version of a type of combinatorial problem that turns up in many fields of applied mathematics. A traveler finds himself in a strange town without funds; he expects a large check to arrive in a few weeks. His most valuable posession is a gold watch chain of 23 links. To pay for a room he arranges with a landlady to give her as collateral one link a day for 23 days. Naturally, the traveler wants to damage his watch chain as little as possible. Instead of giving the landlady a separate link each day he can give her one link the first day, then on the second day take back the link and give her a chain of two links. On the third day he can give her the single link again and on the fourth take back all she has and give her a chain of four links. All that matters is that each day she must be in possession of a number of links that corresponds to the number of days.
The traveler soon realizes that this can be accomplished by cutting the chain in many different ways. The problem is: What is the smallest number of links the traveler needs to cut to carry out his agreement for the full 23 days?

Comments

  1. Minimum links - 5. Length of each link - 1, 2, 4, 8, 8

    ReplyDelete
  2. You only need to cut 2 links. Specifically, if the links are numbered 1,2,...,23, then cut the links numbered 4 and 11. This gives you three chains of lengths 3, 6, and 12, plus the two broken links. This is optimal, since cutting a single link does not suffice.

    Here's how this works.

    Day 1: give her a broken link.
    Day 2: give her the second broken link.
    Day 3: give her the 3 chain, and take back the broken links as change.
    Days 4-5: repeat days 1 and 2.
    Day 6: give her the 6 chain, taking back the 3 chain and two broken links as change.
    Days 7-11: repeat days 1-5
    Day 12: give her the 12 chain, take back all previous pieces as change.
    Days 13-23: repeat days 1-11.

    ReplyDelete
    Replies
    1. Didn't really understand how you are breaking the chain. How are you getting "two broken links"?

      Delete
    2. There are two cuts, each of which passes through a single link. Before the cut, the link will look the letter O. After the cut, it looks like the letter C. The adjacent links can now be passed through the broken one.

      Delete
  3. This comment has been removed by the author.

    ReplyDelete
  4. I wrote sort of an evolutionary algorithm to explore more possibilities. Basically you cannot get there using 4 links since 4 digits in binary representation only get you up to 15. But 5 digits get you to 31, and that leaves some room for 23.
    Possible 5-link solutions I found:
    [1,2,3,5,12]
    [1,1,3,6,12]
    [1,2,4,7,9]
    [1,2,2,6,12]
    [1,2,4,5,11]
    [1,2,3,7,10]
    [1,2,4,8,8]
    [1,2,3,6,11]
    [1,2,4,4,12]
    [1,2,4,6,10]

    ReplyDelete
  5. according to the question, how many links needed to be cut?
    Its 4 as when we cut 4 links at 1,2,4 & 8 intervals from the begining we have finally 5 small chains of 1, 2, 4, 8 & 8 links in them but cut made is only 4 (i.e 4 individual links are cut down).

    ReplyDelete

Post a Comment