Math + CS = 11

After winter quarter started back up again, here at RIT, I found this neat problem dealing with Fibonacci numbers in a set of problems proposed by a few mathematical journals for a contest they were holding. Naturally, I had to give it a shot and it turned out to be a lot of fun! I was going to submit my solution to the contest, but I ended up not doing so and I kind of forgot about solving it. Since I just remembered it, I thought it would make a neat post! I had a lot of fun solving this problem and was very happy when I finally did solve it… not to mention that the idea behind this problem is extremely interesting.

Problem: Arrange the integers 1 through 34 in a sequence such that the sum of every pair on consecutive terms is a Fibonacci number.

I began this problem by first trying out some numbers and looking at how far I would get, but would always end up coming to a number where I have already used. The largest sum of two numbers that one can get from the numbers 1 through 34 is 67 (33 + 34) so I would only have to consider Fibonacci numbers from 1 to 55.

I soon realized that the solution rests in the way the sums of the Fibonacci numbers are related and listed out all the combinations for each Fibonacci number up to 55 using the numbers 1 through 34. By inspection, I found that 17 cannot be used for forming 34 and is only used to make 21 (17 + 4). Therefore, 17 and 4 would have to be the very last (or the very first) terms of the sequence. Following with the idea of picking numbers that occur least often, like 17, I looked for the number can occurs least often that forms a Fibonacci number when added with 4 which turns out the be 30. The next number is 25, then 9, then 12, 22, and so on.

Thus, the sequence is: 34, 21, 13, 8, 26, 29, 5, 16, 18, 3, 31, 24, 10, 11, 23, 32, 2, 19, 15, 6, 28, 27, 7, 14, 20, 1, 33, 22, 12, 9, 25, 30, 4, 17.