Links from 1 to 63

Date: 02/19/2002 at 01:54:48
From: Anonymous
Subject: Adding all links can have 1-63

You arrive for your Club Mud vacation and are given 1 chain of 63 
links to use instead of money during your stay. Your task is to cut 
the chain in 3 places so that you'll be able to hand a person any 
number of links they ask for, from 1-63. A cut link still counts as a 
link.

I tried as follows: 
Since each cut will make 1 link separate from the chain, I'll have 3 
single links. But I could not decide how the other 3 numbers (part of 
chains that totals 60) could be found so as not to miss any number 
from 1-63 if added in possible combinations. I do not know whether my 
assuption that each cut could cause a single link isolated from the 
chain is right. Thanks!

Date: 02/19/2002 at 02:27:27
From: Doctor Jeremiah
Subject: Re: Adding all links can have 1-63

Hi there,

If you cut the second link, then the first link can be taken off the 
second link and the second link can be taken off the rest so you have 
two single links and a big string of links. And when you cut it again 
you will get more single links. That is important.

Since you are going to end up with three single links anyway, perhaps
the shortest chain should be 4 links. The reason for this is that
with three single links you can give 1, 2, or 3 links.

With an additional chain of 4 and three single links you can also give 
4. 4+1, 4+1+! and 4+1+1+1 links. So now you can give any value from 1 
to 7 links.

You cannot give 8 links, so the next chain you need is 8 links so that 
you can also give away 8, 8+1, 8+1+1, 8+1+1+!, 8+4, 8+4+1, 8+4+1+1, 
and 8+4+1+1+1 links. Now you can give any number from 1 to 15 links, 
so the next chain you want is 16 links.

So what you want to do is cut the 5th link, which gives you a single
and a chain of 4, and cut the 9th link in the remaining chain to get a 
single and a chain of 8, and cut the 17th link in the remaining chain 
to get a single and a chain of 16. That leaves a chain of 32.

Now look at the values:

  1 + !+! + 4 + 8 + 16 + 32 = 63

If we add two of the single links together we get powers of two:

  1 + 2 + 4 + 8 + 16 + 32 = 63

Powers of two can be arranged to add up to any value.

- Doctor Jeremiah, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 02/19/2002 at 22:14:58
From: Anonymous
Subject: Adding all links can have 1-63

Dear Dr. Math,

Thank you so much for your prompt reply. I guess, I did not follow up 
my reasoning further but you showed it to me in a very easy way.