石取りゲームとFibonacci数
2人で次のようなゲームをします。
石が個積まれている(
)。交互に1つ以上の石を取り去り、最後の石を取れば勝ちである。ただし次のルールを守らなければいけない。
(1) 先手は最初に全ての石をとってはいけない。
(2) 相手が直前に取った石の数の2倍より多く取ってはいけない。
さて、このゲームに必勝法はあるのでしょうか?
実は次のことが成り立ちます。
ここでFibonacci数とはで定義される数列です。これを示すには次の事実を用います。
たとえばなどです。
証明. の時は明らか。
のとき
なる最大の
をとると、帰納法の仮定より
は一意的なZeckendorf表示を持つ。最大性より
のZeckendorf表示には
未満のFibonacci数のみ現れるので(そうでなければ
となってしまう)、これと
を合わせれば
のZeckendorf表示が得られる。
一意性を示すには、を使わなければならないことを示せばよい。
未満のFibonacci数のみを用いて表示できる最大の整数は
だが、これは漸化式より
以下であり、これらで
を表すことはできない(最後の式は帰納法で簡単に示せる)。
さて、Zeckendorf表示を使って上のゲームの必勝法を作ってみましょう。基本的なアイディアは「残りの石の数をZeckendorf表示したとき現れる最小のFibonacci数を取り除く」ことです。
命題の証明. 「のZeckendorf表示に現れる最小のFibonacci数」を
と書くことにする。
がFibonacci数でなければ、先手は
個だけ取る。するとZeckendorf表示の性質より残りの数
は
をみたす。このときFibonacci数の漸化式よりなので後手は
個以上の石を取ることができず、したがって全ての石を取ることはできない、これを繰り返せば勝てるので、後手が次に取る個数に関わらず繰り返せることを示そう。
後手が個取ったとし、残りの石の数
が
を満たすと仮定して矛盾を導く。
より真に大きい最小のFibonacci数を
とすると、仮定より特に
なので
一方で後手が操作する前には
だったのでの最小性から
等号が成立するときは
で、括弧内のZeckendorf表示が以下のFibonacci数を持つので仮定と矛盾。成立しないときは(1)と(2)を比較すれば
となり矛盾する(一般に
がFibonacci数の時
であることに注意せよ)。これで先手必勝がわかった。
がFibonacci数
だったとする。先手の操作後にまたFibonacci数
が残ると後手が勝つ。なぜなら先手が取る石の数は
であり、後手は
個の石をすべて取れるからである。そうでない場合、先ほどの議論を後手に適用することでやはり後手が勝てることがわかる.
こんな単純なゲームにFibonacci数が現れるのは面白いですね。