フィボナッチ・フリーク

数学の小ネタ集。

石取りゲームと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-bF_{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となり矛盾する(一般に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数が現れるのは面白いですね。