8
$\begingroup$

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)?

$\endgroup$
3
  • 1
    $\begingroup$ 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). $\endgroup$ Nov 11 '20 at 0:07
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 11 '20 at 3:45
  • 1
    $\begingroup$ @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$. $\endgroup$
    – BillyJoe
    Nov 28 '20 at 15:20
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Cool paper, happy to help. I should tattoo on my arm "always search in OEIS" $\endgroup$ Dec 5 '20 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.