ワイソフのゲーム

ワイソフのゲーム（）は2人用のゲームで、2つの山からコイン（または石など）を好きな数だけ交互に取り合っていき、最後に取った者を勝者とする。ただし、1回での取り出し方は、片方の山からまたは、両方の山から同数ずつとする。

このゲームは、チェスにおけるクイーンによっても同等な説明ができる。碁盤上にあるクイーンを、各プレイヤーが碁盤上の南、西、南西のどれかの向きに好きな歩数だけ移動させていったとき、クイーンを左下隅に移動させた者を勝者とする、というものである。クイーンがあるマスの座標、座標は2山にあるコインの数に対応する。

マーティン・ガードナーは1977年3月に、科学雑誌『サイエンティフィック・アメリカン』での「数学ゲーム コラム」の中で、このゲームは中国で捡石子（jiǎn shízǐ（チャヌシッチ）、石取りの意）の名前でプレイされていたと主張している。

オランダの数学者であるウィレム・アブラハム・ワイソフが1907年にこのゲームの数学的分析を発表した。最善手を行うならば、どちらが勝つかは最初の個数の組で決まる（後述）。歴史的には、ニムに次いで2番目に（必勝法が数学的に）解決したゲームであるRichard J. Nowakowski (Dalhousie University)  2009年1月24日。p.4。

 必勝形の原理 
後手必勝形のリストは、以下のようにして帰納的に見出せる。

後手必勝形、後手必敗形を表記の簡略化のためそれぞれ〇, ×で表す。

2山のコインの数を  とする。各点は〇, ×のどちらかである。

(0, 0) は〇である。

 が〇であるとは、任意の自然数  に対して  が×であることである。 が×であるとは、ある自然数  を取ると  のどれかは〇であることである。

故に、(0, 0) は〇より、 または  または  は×である。

残りは  で、この中で  がいずれも最小である (1, 2) は〇である。

(1, 2) は〇より、残りの内  または  は×である。

残りは加えて  で、この中で  がいずれも最小である (3, 5) は〇である。

(3, 5) は〇より、残りの内  または  は×である。

残りは加えて  で、この中で  がいずれも最小である (4, 7) は〇である。

これを繰り返すと、〇である  は次の表のようになる：
+ワイソフのゲームの後手必勝形 01234567891011121314151617181920…01346891112141617192122242527293032…02571013151820232628313436394144474952…
（ の列はを参照）
（ の列はを参照）
（ を1列にしたものはを参照）

 必勝形の床関数表示 
ワイソフのゲームの後手必勝形は次のように表される：
 （ は 0 以上の整数、 は黄金比）
ここで ⌊ ⌋ は床関数を表す。

これは、レイリーの定理と


より従う。

 必勝形のゼッケンドルフ表現 
ワイソフのゲームの (0, 0) 以外の後手必勝形は、次のようにゼッケンドルフ表現することができる。 は 番目のフィボナッチ数とする。

〇である  は、 のゼッケンドルフ表現を
（ はどの2つも連続しない正整数）
とすると、

となる。

 逆型ルール 
ワイソフのゲームを含む組合せゲームにおいて、最後に石を取った者を勝ちとするルールは正規形、最後に石を取った者を負けとする方のルールは「逆形」（クラスメソッド株式会社）2018.03.23「逆型」「双対ゲーム」などと呼ばれている。

逆形のワイソフのゲームの後手必勝形  は次の通りである：


 脚注 

 参考文献 



 関連項目 
 不偏ゲーム
 ニム

 レイリーの定理
 ビーティ数列
 フィボナッチ数
 ゼッケンドルフの定理

 外部リンク 


Category:組合せゲーム理論
Category:数学ゲーム
Category:ゲーム
Category:数学に関する記事
Category:数学のエポニム