How many numbers, from 1 to 50 (both included) can you arrange in a row (one of each) so that each one, except the first and the last, is the sum or difference of its two neighbours?

Example: 3, 10, 7, 17, 24, 41.

10 = 3+7, 7 = 17-10, 17 = 24-7, 24 = 41-17.

After a few attempts, it's easy to see if you have  a b c d e where c=b+d, then a must the sum of b and c and e must be the sum of c and d. If a or e were the difference, then a=c-b=d, or e=c-d=b

Similarly, we can see the number to the left of a must be a+b, as c is already the difference a-b. The sequence must expand out the same way on the right. Thus past a and e, the sequence must be increasing, and so the sequence is determined by b and d. We can see these are the two lowest numbers, so ideally we would like these to be as small as possible.

Starting with b=1, d=2, we get 5 4 1 3 2 5 7, which is a problem, since it repeats 5. With b=1, d=3, we get 17 11 6 5 1 4 3 7 10 17 which again repeats 17

So trying b=2 d=3 we get  41 25 16 9 7 2 5 3 8 11 19 30 49 which works for 13 terms.

In fact this is the only sequence with 13 terms, as trying b=1 and d=4 gives  13 7 6 1 5 4 9 13, b=2 d=4 gives 10 8 2 6 4 10 which both repeat numbers,

b=3 d=4 gives 46 23 13 10 3 7 4 11 15 26 41, and b=2 d=5 gives  31 20 11 9 2 7 5 12 17 29 46. Any other sequence would have terms greater than this one, thus no other sequence has 13 terms, (It also seems like from this, no sequence has 12 terms, other than b=2, d=3)

Posted by Gamer on 2008-11-22 04:22:39