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