とあるゲームの必勝法を考えてみたらフィボナッチ数が現れた話
概要
先日，私の通う学校の期末テストで，次のような問題が出されました．
先手と後手が，次のようなゲームを行う．
・$n$を$2$以上の整数とする．はじめに$n$個の石がある．
・まず先手は$n-1$個以下の好きな数の石を取る．
・以降は，直前に相手が取った石の数の$2$倍以下の好きな数の石を取ることを繰り返す.
・最後の石を取った方が勝ちとなる．
(1) $n=5$のとき，先手と後手のどちらに必勝法があるか．
(2) $n=10$のとき，先手と後手のどちらに必勝法があるか．
しらみつぶしに書き出していけば，$n=5$のとき後手必勝．$n=10$のとき先手必勝であることは分かるでしょう．一般に$n$がどのような条件を満たせば先手必勝となるのかがやはり気になるところです．そこで$n=21$まで順番に試していったところ，次の興味深い事実に気づきました．
$n$がフィボナッチ数のとき後手必勝．フィボナッチ数でない時先手必勝となる
さらに，このゲームの必勝法は，次のように表現できる事にも気がつきました
$n$から始めて，「それ以下の最大のフィボナッチ数を引いていく」という操作を繰り返すことで，$n$をフィボナッチ数の和として表す．
たとえば$n=30$なら$30=21+8+1$，$n=100$なら$100=89+8+3$
このとき最後に現れるフィボナッチ数を$f(n)$と表すとする．
(上の例なら，$f(30)=1,f(100)=3$)
「$n$個の石があれば$f(n)$個の石を取る」がこのゲームの必勝法になる．
これらについて興味深い証明を考えついたので，紹介します.
証明
$n$番目のフィボナッチ数を$F_n$で表すとする．
準備として，正の整数$n$に対して，有限数列$
\lbrace k_i \rbrace _{i=1} ^{g(n)}
$および$
\lbrace a_i \rbrace _{i=0} ^{g(n)}
$を次のように定義する．
$a_0=n$とし，$a_i$以下の最大のフィボナッチ数を$F_{k_{i+1}}$（ただし$k_{i+1}\geq2$），
$a_{i+1}=a_i-F_{k_{i+1}}$とする．$a_i=0$となったら終了で，このときの$i$の値を$g(n)$で表す．また，$f(n)=F_{k_{g(n)}}$とする．すなわちこの$\{k_i\}_{i=1}^{g(n)}$は，以下のように$n$を異なるフィボナッチ数の和で表現する方法の一つに対応する．
$n=F_{k_1}+F_{k_2}+F_{k_3}+\ldots+F_{k_{g(n)}}$
次に，数列$\{k_i\}_{i=1}^{g(n)}$および$f(n)$について，次の2つの補題を用意する．
$1\le i< g(n)$に対して，$F_{k_i}>2F_{k_{i+1}}$が成立する．
$F_{k_i}\le2F_{k_{i+1}}$であるような$i$が存在すると仮定する．
定義より明らかに$k_i>k_{i+1}$である．$k_{i+1}\geq2$より，$2F_{k_{i+1}}< F_{k_{i+1}}+F_{k_{i+1}+1}=F_{k_{i+1}+2}$
であるから，$k_{i+1}+1=k_i$でなければならない．
$a_{i-1}=F_{k_i}+F_{k_{i+1}}+\ldots+F_{k_{g(n)}}\geq F_{k_{i+1}}+F_{k_i}$であり，$k_{i+1}=k_i-1$より，
$F_{k_{i+1}}+F_{k_i}=F_{k_i-1}+F_{k_i}=F_{k_i+1}$であるから，$a_{i-1}\geq F_{k_i+1}$となる．しかしこれは$F_{k_i}$が$a_{i-1}$を超えない最大のフィボナッチ数であることに矛盾．よって示された．
$n$を正の整数とし，$m$を$F_n>m$を満たす整数とする．
$f(F_n-m)\le2m$
が成立する．
$m$以下の最大のフィボナッチ数を$F_s$とする．すなわち$F_s\le m< F_{s+1}$が成り立つ．
$n=s+1$のとき，
$F_s\le m,\ \ F_{s+1}\le2F_s$より$F_{s+1}\le2m$であるから，
$f(F_{s+1}-m)=F_{k_{g(F_{s+1}-m)}}\le F_{k_1}+\ldots+F_{k_{g(F_{s+1}-m)}}=F_{s+1}-m\le2m-m=m<2m$
より成立．
$n=s+2$のときも同様に，
$f(F_{s+2}-m)\le F_{s+2}-m=F_s+F_{s+1}-m\le m+2m-m=2m$
より成立．
次に，任意の$n\geq s+3$に対して，$f(F_n-m)=f(F_{n-2}-m)$が成り立つことを示す．$F_n-m$を超えない最大のフィボナッチ数は$F_{n-1}$である．なぜなら，$F_n-m< F_n$であり，$F_n-m>F_n-F_{s+1}\geq F_n-F_{n-2}=F_{n-1}$だからである．
よって，$a_0=F_n-m$とすると，$\ a_1=F_n-F_{n-1}-m=F_{n-2}-m$である．
また，$a_0$に対する数列${k_{i+1}}$と，$a_1$に対する数列${k_i}$が一致することから，
$f(a_0)=f(a_1)$が成立するので，$f(F_n-m)=f(F_{n-2}-m)$は成立する．
$f(F_n-m)=f(F_{n-2}-m),\ f(F_{s+1}-m)<2m,\ f(F_{s+2}-m)\le2m$から，数学的帰納法により，任意の$n\geq s+1$に対し$f(F_n-m)\le2m$が成立する事がわかる．よって補題は示された．
次に， $n$がフィボナッチ数でないとき，先手必勝であることを証明する．
はじめに置かれていた石の個数を$n_0(=n)$とし，両者合わせてがi回操作を行ったあとの石の個数を$n_i$で表すとする．また，$g_i=g(n_i)$とする．
先手が次の操作に従ってゲームを行ったとする．
$n$個の石が置かれていれば，$f(n)$個の石を取り除く．
$n_0$がフィボナッチ数でないとき，次の2つの命題が成立することを数学的帰納法で示す．
- 先手はゲームが終了するまでこの操作を継続できる．
- 各段階において後手がすべての石を取れることはない．つまり先手必勝である．
- $i=0$のとき
まず，$n_0$はフィボナッチ数ではないので$f(n_0)\le n_0-1$であり，先手は操作を行える． - $i=2j$のとき成立すると仮定して，$i=2j+1,2j+2$のとき
$n_{2j}=F_{k_1}+F_{k_2}+\ldots+F_{k_{g_{2j}-1}}+F_{k_{g_{2j}}}$とすれば
$n_{2j+1}=n_{2j}-f(n_{2j})=F_{k_1}+F_{k_2}+\ldots+F_{k_{g_{2j}-1}}$である．
$g_{2j}=1$のときは$n_{2j+1}=0$より先手が勝つから，$g_{2j}\geq2$の時を考える．
ここで後手がとった石の個数を$m$とする．$m\le2F_{k_{g_{2j}}}$である必要がある．
補題1より$F_{k_{g_{2j}-1}}>2F_{k_{g_{2j}}}$なので，$m< F_{k_{g_{2j}-1}}$であるから，
後手はすべての石を取ることはできない．また，このとき
$n_{2j+2}=F_{k_1}+F_{k_2}+\ldots+F_{k_{g_{2j}-2}}+(F_{k_{g_{2j}-1}}-m)$
で，補題2から$f(n_{2j+2})=f(F_{k_{g_{2j}-1}}-m)\le2m$なので先手は操作を行える．
以上より，$n_0$がフィボナッチ数でないときは先手必勝である．
次に， $n$がフィボナッチ数でないとき，後手必勝であることを証明する．
$n=F_N$とする．先手が$m$個の石をとったとき，$F_N-m\le2m$すなわち$F_N\le3m$であれば，後手はすべての石を取る事ができるので勝てる．$F_N>3m$の時を考える．
$F_N-m$がフィボナッチ数でないとき，補題2より，$f(F_N-m)\le2m$なので，後手は$f(F_N-m)$の石を取り除くことで先手必勝の場合に帰着する．
また，$F_N>3m$であって，$F_N-m$がフィボナッチ数となるものは存在しない．このことを証明する．$F_N-m$がフィボナッチ数であると仮定して，$F_M=F_N-m$とおく．このとき，
$m=F_N-F_M\geq F_N-F_{N-1}=F_{N-2}$となる．しかし，$F_N=F_{N-1}+F_{N-2}=2F_{N-2}+F_{N-3}\le3F_{N-2}$より，$3m\geq3F_{N-2}\geq F_N$となって，$F_N>3m$に矛盾する．
よって$n$がフィボナッチ数であるとき，後手必勝である．
おまけ
証明でははじめに，「最大のフィボナッチ数を引いていく」操作によって自然数をフィボナッチ数の和として表現することを考えました．
これに関連して，「ゼッケンドルフの定理」という次の興味深い事実が知られています．
任意の正の整数は，連続しないフィボナッチ数の和として一意に表すことができる
このような表現は「ゼッケンドルフ表現」と呼ばれています．補題1で示したように，最大のフィボナッチ数を引いていくことで得られる数列には連続するフィボナッチ数が現れなません．つまりこれはゼッケンドルフ表現となっています．
連続しないフィボナッチ数の和で表す方法がこれ以外に存在しないというのが驚きですね．