# For which $N$ is it possible to arrange all whole numbers from $1$ to $N$ in such a way that every adjacent pair sums up to a Fibonacci number?

Recently I came up with a problem regarding Fibonacci numbers:

For which $$N$$ is it possible to arrange all whole numbers from $$1$$ to $$N$$ in such a way that every adjacent pair sums up to a Fibonacci number?

I have manually tested a bunch of cases and I was also able to prove almost every case. The results that I was able to prove are the following:

• If $$N$$ is a Fibonacci number or exactly one less than a Fibonacci number, I was able to prove that an arrangement exists. I used an argument by induction to achieve this.
• If $$F_k+2 \leq N \leq F_{k+1} -3$$ , it is completely impossible, because the numbers $$F_k$$, $$F_k + 1$$ and $$F_k + 2$$ have only one possible pair and therefore have to be at the end of the arragement. This obviously gives a contradiction, because arrangements only have two ends (the first number and the last number).

The cases I was not able to solve are $$N=F_k+1$$ and $$N=F_k-2$$. My theory is that $$N=9$$ is the only working case of the form $$N=F_k+1$$, and $$N=11$$ the only working case of the form $$F_k-2$$. I expect every other $$N$$ of these two forms to be impossible.

Does anybody know a full proof to this problem or maybe the name of the official theorem (if this exists)?

• I ran some code to check if there are solutions for small numbers. everything you said checks out so far - 1-5, 7,8,9, 11 solvable, and also 12,13, 20,21, 33,34, 54,55. none of the others are solvable. I checked up to 55 so far. I'm gonna run the code at night, but I don't think it's gonna get much farther than that (the code isn't too smart). Nov 11 '20 at 0:07
• The only sequence in the OEIS matching these conditions is oeis.org/A259624, which it sounds like is not your sequence if $N=6$ cannot be done. If you have confirmed values for $N$ up to $34$ or so, you may wish to submit it as a new sesquence. Nov 11 '20 at 3:45
• @RavenclawPrefect problem is OEIS search engine finds $2,3,4,5,7,8,9,11,12,13,20,21,33,34,54,55$ but no result for $1,2,3,4,5,7,8,9,11,12,13,20,21,33,34,54,55$. Nov 28 '20 at 15:20

Thanks to @Rei Henigman data, I could find OEIS sequence A079734 and from there the "Fibonacci Plays Billiards" paper by Elwyn Berlekamp and Richard Guy, where they state with theorem 1 on page 3, that the only solutions are $$N = 9$$, $$N = 11$$, $$N = F_k$$, $$N = F_k − 1$$ for $$k \ge 4$$. Note that $$1$$ is excluded from the OEIS sequence.