Solution to Problem 60

Congratulations to this week's winners

Nathan Pauli, Ray Kremer
Further correct solutions were also received from William Webb, Robert McQuaid, Brian Laughlin, Richard Oak, Burkart Venzke, Douglas Vander Griend, Jim Wang. Numerous incorrect solutions were submitted.

Let's start out by looking to see what numbers must be on the list. I'll assume the numbers are listed in increasing order, though this was not strictly a requirement. Clearly the number 1 must be the first number on the list, while 2 must be the second. As 3 cannot be written as the sum of smaller non-consecutive numbers on the list, it must be the third one. Now 4 = 1 + 3, but 5 must be added. Then 6 = 5 + 1, 7 = 5 + 2, but 8 must be added. Some patient experimenting will show you that the list must start with

1, 2, 3, 5, 8, 13, 21, 34, 55,... and you'll see that the next number you have to add is the sum of the previous two. This is, of course, the famous Fibonacci sequence.

An easy proof that this list will always work was offered by Douglas Vander Griend. Take a number N. If it's a Fibonacci number, it's on the list. Otherwise, subtract off the largest Fibonacci number, F less that N. The result will be a number strictly less than the Fibonacci number before F. Induction finishes the argument.

Burkart Venzke suggests modifying the third condition so that no n consecutive numbers on the list are allowed to appear in any one sum. With n = 3 the first few terms are

1, 2, 3, 4, 6, 9, 13, 28,... where each number now is the sum of the previous one and the one three steps before, that is a_k = a_k-1 + a_k-3. The general case leads to a_k = a_k-1 + a_k-n. Eliminating the condition on consecutive list numbers is the same as setting n = 0, which gives a list of powers of 2.

You are visitor number 3910 to this page.
Page last updated 8 April 1999.