フィボナッチニム
フィボナッチ・ニムは、数学的な引き算ゲームであり、ニムゲームのバリエーションです。プレイヤーは交互に山札からコインを取り除き、各手番で最大で前の手番の2倍のコインを取り、最後のコインを取ることで勝利します。このゲームではフィボナッチ数列が重要な役割を担っており、特に、最初のプレイヤーが勝利できるのは、開始時のコインの枚数がフィボナッチ数列でない場合のみです。完全な戦略は、カウンターの山が1つしかないゲームでは最善のプレイとして知られていますが、複数の山があるゲームのバリエーションではそうではありません。
ルールと歴史
フィボナッチ・ニムは2人のプレイヤーが交互に山札からコインやその他のカウンターを取り除きながらプレイします。最初の手では、プレイヤーはすべてのコインを取ることはできません。その後の手番では、取り除くコインの枚数は、前の手番の2倍までとします。通常のプレイルールでは、最後にコインを取ったプレイヤーが勝ちます。[ 1 ]
このゲームは1963年にマイケル・J・ウィニハンによって初めて記述され、オレゴン州立大学の数学者ロバート・E・ガスケルの発明とされています。このゲームはフィボナッチ数列を解析に多く用いることから「フィボナッチ・ニム」と呼ばれています。 [ 2 ]
このゲームは、フィボナッチニムとも呼ばれる別のゲームとは区別されるべきである。このゲームでは、プレイヤーは各動きごとにフィボナッチ数のコインを取り除くことができる。[ 3 ]
戦略
フィボナッチニムで最善の戦略は、現在のコインの枚数をフィボナッチ数列の和として考えることです。[ 2 ]数をフィボナッチ数列の和として表す方法は数多くありますが、各フィボナッチ数を最大でも1回しか使用せず、フィボナッチ数列の連続するペアを避ける表現方法は1つだけです。この唯一の表現はゼッケンドルフ表現として知られています。例えば、10のゼッケンドルフ表現は8 + 2です。 10は5 + 5や5 + 3 + 2など他の方法でもフィボナッチ数列の和として表すことができますが、これらの他の方法では、各フィボナッチ数を1回だけ使用し、2と3、3と5などの連続したフィボナッチ数列を避けるという条件を満たしていません。任意の数のゼッケンドルフ表現は、可能な限り最大のフィボナッチ数を繰り返し減算してゼロに達する貪欲アルゴリズムによって見つけることができます。[ 4 ]
このゲームの戦略には、「クォータ」と呼ばれる数値も関係します。これはqと表記されることもあります。これは、現在取り除くことができるコインの最大枚数です。最初の動きでは、1枚を除くすべてのコインを取り除くことができるため、コインの枚数がn 枚の場合、クォータはq = n − 1となります。その後の動きでは、クォータは前の動きの2倍になります。[ 2 ]
これらの定義に基づくと、qがゼッケンドルフ表現における最小のフィボナッチ数以上の場合は、今まさに動こうとしているプレイヤーは勝つことができ、そうでない場合は（対戦相手が最善を尽くしても）負ける。勝ちの局面では、（許可されている場合）すべてのコインを取り除くか、そうでない場合はゼッケンドルフ表現における最小のフィボナッチ数に等しい数のコインを取り除くことが常に勝ちの局面となる。これが可能な場合、対戦相手は必然的に負けの局面に直面する。なぜなら、新しいクォータは、残りのコイン数のゼッケンドルフ表現における最小のフィボナッチ数よりも小さくなるからである。[ 2 ]他の勝ちの局面も可能である。[ 5 ]しかし、負けの局面からは、すべての動きが勝ちの局面につながる。[ 2 ]
フィボナッチ数のゼッケンドルフ表現は、その1つの数から構成されます。そのため、開始時の山札のコインの枚数がフィボナッチ数nの場合、ゼッケンドルフ表現における最小のフィボナッチ数はnとなり、開始時の割り当て枚数n − 1よりも大きくなります。したがって、開始時の山札がフィボナッチ数の場合、最初のプレイヤーは負け、2番目のプレイヤーは勝ちとなります。ただし、開始時のコイン枚数がフィボナッチ数でない場合は、ゼッケンドルフ表現においてより小さなフィボナッチ数となります。これらの数は開始時の割り当て枚数よりも大きくないため、開始時のコイン枚数がフィボナッチ数でない場合は、常に最初のプレイヤーが勝つことができます。[ 1 ]
例
例えば、最初に10枚のコインがあったとします。[ 6 ]
- 10のゼッケンドルフ表現は10 = 8 + 2で、最初のノルマは9です。これはゼッケンドルフ表現における最小のフィボナッチ数2よりも大きいため、先攻プレイヤーが勝利します。先攻プレイヤーの勝利への一つの動きは、この表現における最小のフィボナッチ数である2を取り除いて、コインを8枚残すことです。
- この動きの後、残りコインは8枚で、ゼッケンドルフ表現は8です。新しいクォータは4です。つまり、後手は最大4枚のコインしか取り除くことができません。ゼッケンドルフ表現の最小値に達するには足りません。3枚か4枚のコインを取り除くと、先手はすぐに勝利できます。しかし、後手が2枚のコインを取ったと仮定しましょう。
- 残りは6 = 5 + 1枚のコインで、割り当ては4となり、ゼッケンドルフ表現の1よりも大きくなります。最初のプレイヤーは再びこの表現における最小のフィボナッチ数である1を取り、コインを5枚残します。
- 5枚のコインの山の場合、ゼッケンドルフ表現は5ですが、割り当ては2と小さくなります。2番目のプレイヤーは2枚のコインを取ることもできますが、これもまた即座に負けとなるため、2番目のプレイヤーは1枚のコインしか取らないと仮定します。
- この動きの後、コインの数は 4 = 3 + 1 となり、割り当ては 2 になります。最初のプレイヤーは再びゼッケンドルフ表現の最小のフィボナッチ数である 1 を取り、コインを 3 枚残します。
- これで、2 番目のプレイヤーが 1 枚のコインを取るか 2 枚のコインを取るかに関係なく、次の動きで最初のプレイヤーがゲームに勝利することになります。
複数の山
フィボナッチ・ニムは、どの局面からでも可能な動きが、これから動くプレイヤーの身元に依存しないという点で、公平なゲームである。したがって、スプレイグ＝グランディの定理は、複数のコインの山があり、各動きで1つの山からのみコインが取り除かれる（同じ山から前回の動きの2倍まで）ゲームの拡張を分析するために使用できる。この拡張では、各山のニム値を計算する必要があり、複数山のゲームの値はこれらのニム値のニム和となる。しかし、これらの値の完全な記述は知られていない。[ 7 ]
研究されている別の複数山のゲームの変種では、前の移動が同じ山への移動であったかどうかに関係なく、各移動での石の数が前の動きの2倍に制限されています。[ 8 ]
参考文献
- ^ a b Vajda, Steven (2007)、「フィボナッチ・ニム」、数学ゲームとその遊び方、ドーバー数学書籍、クーリエ社、pp. 28– 29、ISBN 9780486462776
- ^ a b c d e Whinihan, Michael J. (1963)、「フィボナッチ・ニム」(PDF)、フィボナッチ・クォータリー、1 (4): 9– 13
- ^コインのフィボナッチ数を引くゲームについては、アルフレッド・ブラザー・U.（1963）「フィボナッチ数の探求」（PDF）、フィボナッチ・クォータリー、1（1）：57–63を参照。, 「研究プロジェクト：フィボナッチ・ニム」、p. 63; Pond, Jeremy C.; Howells, Donald F. (1963)、「フィボナッチ・ニムについてさらに詳しく」（PDF）、Fibonacci Quarterly、1 (3): 61– 62
- ^ロナルド・L・グラハム;ドナルド・E・クヌース; Patashnik、Oren (1994)、Concrete Mathematics (第 2 版)、Addison-Wesley、pp. 295–296、ISBN 0-201-55802-5
- ^アレン、コーディ；ポノマレンコ、ヴァディム（2014）「フィボナッチ・ニムと勝利の動きの完全な特徴づけ」、Involve、7（6）：807-822、doi：10.2140/involve.2014.7.807
- ^ 2がこの開始位置からの唯一の勝利手であるという事実と、この例で生じるすべての山のサイズのゼッケンドルフ表現は、 Allen & Ponomarenko (2014)、表1、p. 818に記載されています。
- ^ラーソン、アーバン; ルビンスタイン＝サルゼド、サイモン (2016)、「フィボナッチニムのグランディ値」、国際ゲーム理論ジャーナル、45 (3): 617– 625、arXiv : 1410.0332、doi : 10.1007/s00182-015-0473-y、MR 3538534、S2CID 206890376
- ^ラーソン、アーバン; ルビンスタイン＝サルゼド、サイモン (2018)、「グローバルフィボナッチニム」、国際ゲーム理論ジャーナル、47 (2): 595– 611、doi : 10.1007/s00182-017-0574-x、MR 3842045、S2CID 52073784
