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)?
from Hot Weekly Questions - Mathematics Stack Exchange
Rubenscube
Post a Comment