ワイソフのゲーム

ワイソフのゲームをチェス盤で表した図。クイーンの位置が青丸だと、後手が最善手を行えば必ず勝つ。

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

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

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

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

必勝形の原理

ワイソフのゲームの必勝形。一番左下の四角は位置 (1, 1) で、赤い四角は後手必勝形である。

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

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

2山のコインの数を テンプレート:Math2 とする。各点は〇, ×のどちらかである。

(0, 0) は〇である。

テンプレート:Math2 が〇であるとは、任意の自然数 テンプレート:Mvar に対して テンプレート:Math2 が×であることである。テンプレート:Math2 が×であるとは、ある自然数 テンプレート:Mvar を取ると テンプレート:Math2 のどれかは〇であることである。

故に、(0, 0) は〇より、テンプレート:Math2 または テンプレート:Math2 または テンプレート:Math2 は×である。

残りは テンプレート:Math2 で、この中で テンプレート:Math2 がいずれも最小である (1, 2) は〇である。

(1, 2) は〇より、残りの内 テンプレート:Math2 または テンプレート:Math2 は×である。

残りは加えて テンプレート:Math2 で、この中で テンプレート:Math2 がいずれも最小である (3, 5) は〇である。

(3, 5) は〇より、残りの内 テンプレート:Math2 または テンプレート:Math2 は×である。

残りは加えて テンプレート:Math2 で、この中で テンプレート:Math2 がいずれも最小である (4, 7) は〇である。

これを繰り返すと、〇である テンプレート:Math2 は次の表のようになる：

ワイソフのゲームの後手必勝形 テンプレート:Math2

テンプレート:Mvar	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	…
テンプレート:Mvar	0	1	3	4	6	8	9	11	12	14	16	17	19	21	22	24	25	27	29	30	32	…
テンプレート:Mvar	0	2	5	7	10	13	15	18	20	23	26	28	31	34	36	39	41	44	47	49	52	…

（テンプレート:Mvar の列はテンプレート:OEISを参照）

（テンプレート:Mvar の列はテンプレート:OEISを参照）

（テンプレート:Math2 を1列にしたものはテンプレート:OEISを参照）

必勝形の床関数表示

ワイソフのゲームの後手必勝形は次のように表される：

• $(\lfloor n\phi \rfloor ,\lfloor n{\phi }^2\rfloor )$（テンプレート:Mvar は 0 以上の整数、テンプレート:Mvar は黄金比）

ここで ⌊ ⌋ は床関数を表す。

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

• テンプレート:Math2
• $\frac{1}{\phi }+\frac{1}{{\phi }^2}=1$

より従う。

必勝形のゼッケンドルフ表現

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

〇である テンプレート:Math2 は、テンプレート:Math2 のゼッケンドルフ表現を

$y-x=:F_{n_1-1}+F_{n_2-1}+\cdots +F_{n_k-1}$（テンプレート:Math2 はどの2つも連続しない正整数）

とすると、

$x=F_{n_1}+F_{n_2}+\cdots +F_{n_k}$

$y=F_{n_1+1}+F_{n_2+1}+\cdots +F_{n_k+1}$

となる。

逆型ルール

ワイソフのゲームを含む組合せゲームにおいて、最後に石を取った者を勝ちとするルールは正規形、最後に石を取った者を負けとする方のルールは「逆形」「逆型」「双対ゲーム」などと呼ばれている。

逆形のワイソフのゲームの後手必勝形 テンプレート:Math2 は次の通りである：

• $(0,1),(2,2),(\lfloor n\phi \rfloor ,\lfloor n{\phi }^2\rfloor )(n\ge 2)$

参考文献

• テンプレート:Cite web
• テンプレート:Cite web

関連項目

• 不偏ゲーム
  • ニム
  • テンプレート:仮リンク
• レイリーの定理
• ビーティ数列
• フィボナッチ数
• ゼッケンドルフの定理

外部リンク

• テンプレート:MathWorld