TransWikia.com

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?

Mathematics Asked by Rubenscube on February 20, 2021

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

One Answer

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.

Correct answer by BillyJoe on February 20, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP