石取りゲームとFibonacci数 - フィボナッチ・フリーク

2人で次のようなゲームをします。

石が $n$ 個積まれている( $n\geq2$ )。交互に1つ以上の石を取り去り、最後の石を取れば勝ちである。ただし次のルールを守らなければいけない。

(1) 先手は最初に全ての石をとってはいけない。

(2) 相手が直前に取った石の数の2倍より多く取ってはいけない。

さて、このゲームに必勝法はあるのでしょうか？

実は次のことが成り立ちます。

命題. 上のゲームは $n$ がFibonacci数のとき後手必勝、それ以外のとき先手必勝である。

ここでFibonacci数とは $F_1=F_2=1, F_{n+2}=F_{n+1}+F_n$ で定義される数列です。これを示すには次の事実を用います。

定理. 任意の正整数 $n$ は、隣り合わないいくつかのFibonacci数 $F_m(m\neq 1)$ の和に一意的に表される。これをZeckendorf表示という。

たとえば $53=34+13+5+1=F_9+F_7+F_5+F_2$ などです。

証明. $n=1$ の時は明らか。 $n\gt 1$ のとき $F_m\leq n$ なる最大の $m$ をとると、帰納法の仮定より $n-F_m$ は一意的なZeckendorf表示を持つ。最大性より $n-F_m$ のZeckendorf表示には $F_{m-1}$ 未満のFibonacci数のみ現れるので（そうでなければ $n\geq F_{m+1}$ となってしまう）、これと $F_m$ を合わせれば $n$ のZeckendorf表示が得られる。

一意性を示すには、 $F_m$ を使わなければならないことを示せばよい。 $F_m$ 未満のFibonacci数のみを用いて表示できる最大の整数は $F_{m-1}+F_{m-3}+\cdots+1$ だが、これは漸化式より $F_{m-2}+F_{m-3}+\cdots+F_1=F_m-1$ 以下であり、これらで $n$ を表すことはできない（最後の式は帰納法で簡単に示せる）。 $\square$

さて、Zeckendorf表示を使って上のゲームの必勝法を作ってみましょう。基本的なアイディアは「残りの石の数をZeckendorf表示したとき現れる最小のFibonacci数を取り除く」ことです。

命題の証明. 「 $x$ のZeckendorf表示に現れる最小のFibonacci数」を $F_{Z(x)}$ と書くことにする。

$n$ がFibonacci数でなければ、先手は $a=F_{Z(n)}$ 個だけ取る。するとZeckendorf表示の性質より残りの数 $n-a$ は

$Z(n-a)\geq Z(n)+2$

をみたす。このときFibonacci数の漸化式より $F_{Z(n)+2}\gt 2F_{Z(n)}$ なので後手は $F_{Z(n)+2}$ 個以上の石を取ることができず、したがって全ての石を取ることはできない、これを繰り返せば勝てるので、後手が次に取る個数に関わらず繰り返せることを示そう。

後手が $b$ 個取ったとし、残りの石の数 $n-a-b$ が $F_{Z(n-a-b)}\gt 2b$ を満たすと仮定して矛盾を導く。 $b$ より真に大きい最小のFibonacci数を $F_c$ とすると、仮定より特に

$F_{Z(n-a-b)}\gt 2b\geq 2F_{c-1}\geq F_c$

なので

$Z(n-a-b)\geq c+1.\tag{1}$

一方で後手が操作する前には

$F_{Z(n-a)}\geq F_{Z(n)+2}\gt 2F_{Z(n)}\geq b$

だったので $c$ の最小性から

$Z(n-a)\geq c.\tag{2}$

等号が成立するときは

$n-a-b=n-a-F_{Z(n-a)}+(F_{Z(n-a)}-b)$

で、括弧内のZeckendorf表示が $2b$ 以下のFibonacci数を持つので仮定と矛盾。成立しないときは(1)と(2)を比較すれば $Z(b)\geq c$ となり矛盾する（一般に $x$ がFibonacci数の時 $Z(x-y)\geq\min\{Z(x),Z(y)\}-1$ であることに注意せよ）。これで先手必勝がわかった。

$n$ がFibonacci数 $F_m$ だったとする。先手の操作後にまたFibonacci数 $F_{m'}$ が残ると後手が勝つ。なぜなら先手が取る石の数は $F_m-F_{m'}\geq F_{m-2}$ であり、後手は $F_{m'}(\leq F_{m-1}\leq 2F_{m-2})$ 個の石をすべて取れるからである。そうでない場合、先ほどの議論を後手に適用することでやはり後手が勝てることがわかる. $\square$

こんな単純なゲームにFibonacci数が現れるのは面白いですね。