ウィトフのゲーム

ワイトフのゲームは、2 つのカウンターの山を使ってプレイする 2人用の数学的な減算ゲームです。プレイヤーは交代で、一方または両方のカウンターの山からカウンターを取り除きます。両方のカウンターの山からカウンターを取り除くときは、各山から取り除くカウンターの数が等しくなければなりません。1 人のプレイヤーが最後のカウンターを取り除くとゲームが終了し、そのプレイヤーが勝ちます。

このゲームを同じように説明すると、チェスのクイーン1 個が大きなマス目のどこかに配置され、各プレイヤーはクイーンをマス目の左下隅、つまり南、西、南西の任意の方向に動かすことができます。クイーンを隅に動かしたプレイヤーが勝者となります。クイーンの 2 つの直交座標は、山から駒を取り除くというゲームの定式化における 2 つの山のサイズに対応します。

マーティン・ガードナーは、1977年3月のサイエンティフィック・アメリカン誌の「数学ゲーム」コラムで、このゲームは中国では捡石子jiǎn shízǐ（「石拾い」）という名前でプレイされていたと主張している。^[1]オランダの数学者WAウィトフは、 1907年にこのゲームの数学的分析を発表した。^[2]

ゲーム内のどのポジションも、整数のペア( n、m ) ( n  ≤  m )で記述できます。これは、ポジションの両方の山のサイズまたはクイーンの座標を表します。ゲームの戦略は、コールド ポジションとホット ポジションを中心に展開します。コールド ポジションでは、順番が来たプレイヤーがベスト プレイで負けますが、ホット ポジションでは、順番が来たプレイヤーがベスト プレイで勝ちます。ホットポジションからの最適な戦略は、到達可能な任意のコールド ポジションに移動するということです。

ポジションをホットとコールドに分類することは、次の 3 つのルールを使用して 再帰的に実行できます。

1. (0,0)はコールドポジションです。
2. コールド ポジションに 1 回の移動で到達できるポジションは、すべてホット ポジションです。
3. すべての動きがホットポジションにつながる場合、ポジションはコールドです。

たとえば、規則 2 により、形式 (0, m ) および ( m , m ) ( m  > 0) のすべての位置はホットです。ただし、位置 (1,2) はコールドです。これは、そこから到達できる位置 (0,1)、(0,2)、(1,0)、(1,1) だけがホットであるためです。n と m の値が最小のコールド位置 ( n , m ) は、(0, 0)、(1, 2)、(3, 5) 、 (4, 7)、(6, 10)、(8, 13) です。( OEISのシーケンス A066096 および A090909 ) ( OEIS : A072061も参照)

このゲームのミゼールゲームでは、(0, 1)と(2, 2)はコールドポジションであり、m、  n >2のポジション( n、m )が コールドなのは、通常のゲームで( n、m )がコールドな場合のみです。

ワイトフは、コールドポジションが黄金比によって決まる規則的なパターンに従うことを発見した。具体的には、kが任意の自然数であり、

${\displaystyle n_{k}=\lfloor k\phi \rfloor =\lfloor m_{k}\phi \rfloor -m_{k}\,}$

${\displaystyle m_{k}=\lfloor k\phi ^{2}\rfloor =\lceil n_{k}\phi \rceil =n_{k}+k\,}$

ここで、 φ は黄金比で、床関数を使用している場合、 ( n _k、m _k ) はk^番目のコールドポジションです。これらの 2 つの数列は、それぞれOEIS : A000201および OEIS : A001950として、オンライン整数シーケンス百科事典に記録されています。

2つのシーケンスn _kとm _kは、方程式に関連付けられた ビーティシーケンスです。

${\displaystyle {\frac {1}{\phi }}+{\frac {1}{\phi ^{2}}}=1\,.}$

ビーティシーケンスのペアの場合に一般的に当てはまるように、これら 2 つのシーケンスは補完的です。つまり、各正の整数はどちらのシーケンスにも 1 回だけ出現します。

• ニム
• グランディのゲーム
• 平方を引く
• ウィトフ配列

• Weisstein、Eric W.「Wythoff のゲーム」。MathWorld。
• グライム、ジェイムス。「Wythoff's Game (Get Home)」（ビデオ）。YouTube 。ブレイディ・ハラン。2021年12月15日時点のオリジナルよりアーカイブ。 2017年8月21日閲覧。