180px|thumb|ワイソフのゲームをチェス盤で表した図。クイーンの位置が青丸だと、後手が最善手を行えば必ず勝つ。 ワイソフのゲーム()は2人用のゲームで、2つの山からコイン(または石など)を好きな数だけ交互に取り合っていき、最後に取った者を勝者とする。ただし、1回での取り出し方は、片方の山からまたは、両方の山から同数ずつとする。

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

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

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

必勝形の原理 thumb|upright=1.6|ワイソフのゲームの必勝形。一番左下の四角は位置 (1, 1) で、赤い四角は後手必勝形である。 後手必勝形のリストは、以下のようにして帰納的に見出せる。

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

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「逆型」「双対ゲーム」などと呼ばれている。

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

脚注

参考文献

関連項目 不偏ゲーム ニム

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

外部リンク