the gold train

Question

A traveler stops at a country inn and wants to stay 23 days. She has no money, but
she does have a piece of gold chain with 23 links. The innkeeper agrees to accept
one link per day in payment, provided that he has in his possession one link on the
first day, two links on the second day, and so on. The traveler agrees, but doesn’t
want to give the innkeeper more than he is entitled to each day. Further, she wants
to cut as few links as possible.
Instead of just cutting one link off of the end of the chain each day, the traveler can
cut a link not at the end to get pieces of chain of various lengths. When she does
that, the cut link becomes detached on both sides and becomes separate itself. For
example, if she were to cut the seventh link the first day, she would have a piece
with 6 links, a piece with 1 link, and a piece with 16 links. Also, each day she can
give the innkeeper new pieces of chain and take some previous pieces back to
make the right total. The innkeeper doesn’t mind getting links that have been cut.
What is the fewest number of links the traveler could cut and still be able give the
innkeeper exactly the number of links needed for each day?

Answer 1

It helps to understand positional number systems, like decimal and binary, to determine “as few links as possible.”  The numbers 1,2,4,8,16 are sufficient to count from 1 to 23 (this is binary).

 

The problem, however, specifies that a “cut” produces three segments –-  (x-1), 1, and (23-x).  The example with x=7 produces 6, 1, and 16.  This means that each internal “cut” produces a segment with 1 link.

 

So, with 2 “cuts” there must be 2 individual links, but that doesn’t help the need for 1,2,4,8,16.

 

However, 3 “cuts”does (it lets you replace all combinations of 1,2).

 

So, make cuts in positions 3, 8, and 17.  This gives links of length 2, 1, 4, 1, 8, 1, and 6 (note: this totals 23).

 

To check that all the numbers from 1 to 23 can be created from these values (which includes “taking back” links when appropriate):

1=1

2=1+1

3=1+1+1

4=4 (take back the three 1’s)

5=4+1

6=4+1+1

7=4+1+1+1

8=8 (trade again)

9=8+1

10=8+1+1

11=8+1+1+1

12=8+4 (trade again)

13=8+4+1

14=8+4+1+1

15=8+4+1+1+1

16=8+6+2 (trade again)

17=8+6+2+1

18=8+6+2+1+1

19=8+6+2+1+1+1

20=8+6+4+2  (trade again)

21=8+6+4+2+1

22=8+6+4+2+1+1

23=8+6+4+2+1+1+1  [that’s all the segments)

 

Three "cuts" (at positions 3, 8, and 17) are sufficient.