Puzzle #139: Gold Links

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? More advanced mathematicians may wish to obtain a general formula for the longest chain that can be used in this manner after n cuts are made at the optimum places.

As always, please send your answers as comments within the blog (preferred), or send an e-mail to alokgoyal_2001@yahoo.com. Please do share the puzzle with others if you like, and please also send puzzles that you have come across that you think I can share in this blog.

Happy gold digging!

This entry was posted in Puzzles and tagged , . Bookmark the permalink.

5 Responses to Puzzle #139: Gold Links

  1. Abhinav Jain says:

    Segments of 1,1,3,6,12 will do it

  2. Binary representation of numbers.
    1 is required for sure.
    Case 1: Have another 1. Then we need 3, 6, 12. -> 1,1,3,6,12
    Case 2: Have a 2. Then we need 4, 8, 8. -> `1,2,4,8,8

  3. Praneeth Kumar says:

    1,2,4,8,8

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s