Rules of fibonacci nim:
Fibonacci nim is played by two players, who alternate removing coins or other counters from a pile. On the first move, a player is not allowed to take all of the coins, and on each subsequent move, the number of coins removed can be any number that is at most twice the previous move. According to the normal play convention, the player who takes the last coin wins.
And i have to show this 4 things:
1)prove that if on the beginning of the game on the table is $2F_n$ coins, then winning move is to take $F_{n-2}$ coins
2)designate winning move if on the beginning of the game on the table is $F_n-1$ coins
3)prove that if on the beginning of the game on the table is $F_n^2$ coins, then taking 1 coin is winning move
4)designate winning move if on the beginning of the game on the table is $4F_n$ coins
And we have that $F_0=1, F_1=2$ and then $F_n=F_{n-2}+F_{n-1}$
I know what is the winning strategy in fibonacci nim game, but i dont know how find zeckendorf representation of numbers in point $1-4$ 🙁
Best Answer
For $(1)$ note that $2F_n=F_n+(F_{n-1}+F_{n-2})=(F_{n+1}-F_{n-1})+(F_{n-1}+F_{n-2})$.
For $(2)$ prove by induction that
$$F_n-1=F_{n-1}+F_{n-3}+F_{n-5}+\ldots+F_m=\sum_{k=0}^{\lfloor n/2\rfloor-1}F_{n-(2k+1)}\;,$$
where
$$m=\begin{cases}1,&\text{if }n\text{ is even}\\ 2,&\text{if }n\text{ is odd}\;. \end{cases}$$
For $(3)$ I note the following Zeckendorf representations:
$$\begin{array}{c|c|r} n&F_n^2&\text{Zeckendorf}\\\hline 1&1&1\\ 2&1&\color{red}{1}\\ 3&4&101\\ 4&9&\color{red}{10001}\\ 5&25&1000101\\ 6&64&\color{red}{100010001}\\ 7&169&10001000101\\ 8&441&\color{red}{1000100010001}\\ 9&1156&100010001000101 \end{array}$$
This shows a pattern that suggests that $F_{n+2}^2=F_n^2+F_{2n+2}$, and this, if true, would allow an easy inductive proof of the claim. In fact this is an old identity due to Lucas; there is an easy combinatorial proof in this PDF (Theorem $4$).
For $(4)$, similar experimentation with the Zeckendorf representations of the numbers $4F_n$ will suggest an identity for $4F_n$ that yields a strategy for $n\ge 3$.