コンウェイの兵士たち

コンウェイの兵士、またはチェッカージャンピング問題は、1961 年に数学者ジョン ホートン コンウェイによって考案され、分析された1 人用の数学ゲームまたはパズルです。ペグ ソリティアのバリエーションで、無限のチェッカーボード上で行われます。ボードは、無限に伸びる水平線によって分割されています。線の上には空のセルがあり、線の下には任意の数のゲーム ピース、つまり「兵士」があります。ペグ ソリティアと同様に、移動は、1 人の兵士が隣接する兵士を飛び越えて空のセルに垂直または水平 (斜めではない) に移動し、飛び越えた兵士を取り除くことで構成されます。パズルの目的は、兵士を水平線よりできるだけ上に配置することです。

コンウェイは、どのような戦略を採用しても、兵士が水平線から4列以上前進できるような動きの順序は限られていないことを証明した。彼の議論では、慎重に選ばれたセルの重み付け（黄金比を含む）が使用され、総重量は減少するか一定のままになるかのどちらかであることを証明した。この議論は、多くの一般的な数学書で再現されている。^[1]

サイモン・タサムとギャレス・テイラーは、無限の一連の動きによって5行目に到達できることを示した。 ^{[2] [3]}対角ジャンプが許可されている場合、8行目に到達できますが、9行目に到達することはできません。^{[1]ゲームの}n次元バージョンでは、到達できる最高の行は です。コンウェイの重み付けの議論は、その行に到達できないことを示しています。[ 4 ^]${\displaystyle 3n-2}$${\displaystyle 3n-1}$

を定義します。(言い換えると、ここでは は黄金比の逆数を表します。) に注目してください。 ${\displaystyle \varphi ={\frac {{\sqrt {5}}-1}{2}}\approx 0.61803\,39887\ldots }$${\displaystyle \varphi}$${\displaystyle \varphi ^{2}=1-\varphi }$

ターゲット スクエアに値 のラベルを付け、他のすべてのスクエアに値 のラベルを付けます。ここで、 はターゲット スクエアまでのマンハッタン距離です。次に、兵士のスクエアの値を合計することで、兵士の配置の「スコア」を計算できます。たとえば、次のジャンプでターゲット スクエアに到達するように配置された兵士が 2 人だけの場合、スコアは になります。 ${\displaystyle \varphi^{0}=1}$${\displaystyle \varphi^{n}}$${\displaystyle n}$${\displaystyle \varphi^{1}+\varphi^{2}}$

兵士が他の兵士を飛び越える場合、考慮すべき 3 つのケースがあります。

1. 兵士が目標のマスに向かってジャンプする場合、ある兵士のマス目の値を、兵士がジャンプしたマス目の値をとします。この場合、ジャンプ後のスコアの合計変化は です。${\displaystyle \varphi^{n}}$${\displaystyle n}$${\displaystyle \varphi^{n-1}}$${\displaystyle \varphi ^{n-2}-\varphi ^{n-1}-\varphi ^{n}=\varphi ^{n-2}(1-\varphi -\varphi ^{2})= 0}$
2. 兵士がジャンプ後に目標マスから同じ距離に留まる場合: この場合、スコアの変化は です。${\displaystyle \varphi ^{n}-\varphi ^{n-1}-\varphi ^{n}=-\varphi ^{n-1}}$
3. 兵士が目標マスから飛び去った場合:ここでのスコアの変化は です。${\displaystyle \varphi ^{n+2}-\varphi ^{n+1}-\varphi ^{n}=\varphi ^{n}(\varphi ^{2}-\varphi -1)=-2 \varphi ^{n+1}}$

したがって、ジャンプによって構成の合計スコアが増加することはありません。

ここで、1 本の無限の水平線だけが兵士で完全に満たされている開始構成を考えてみましょう。

この水平な兵士の列が目標マスの真下にある場合、その配置のスコアは です。目標マスの2マス下の列のスコアは です。3マス下の列のスコアは、などとなります。 ${\displaystyle \varphi +2\varphi ^{2}+2\varphi ^{3}+\ldots }$${\displaystyle \varphi ^{2}+2\varphi ^{3}+2\varphi ^{4}+\ldots =\varphi (\varphi +2\varphi ^{2}+2\varphi ^{3}+\ldots )}$${\displaystyle \varphi ^{2}(\varphi +2\varphi ^{2}+2\varphi ^{3}+\ldots )}$

兵士が赤線の下の半分の平面全体を埋め尽くす完全な開始配置を考えてみましょう。この配置のスコアは、個々のラインのスコアの合計です。したがって、ターゲットのマス目が赤線の真上にある場合、スコアは

${\displaystyle S_{1}=(\varphi +2(\varphi ^{2}+\varphi ^{3}+\varphi ^{4}\ldots ))(1+\varphi +\varphi ^{2}+\varphi ^{3}+\ldots )}$。

ここで、 のもう一つの興味深い性質、つまり に注目してください。この恒等式を適用すると、 ${\displaystyle \varphi }$${\displaystyle \sum _{n=2}^{\infty }\varphi ^{n}=1}$

${\displaystyle S_{1}=(\varphi +2)(1+\varphi +1)=(\varphi +2)^{2}=5+3\varphi \approx 6.85410\ldots }$。

目標マスが赤い線より2列目上にある場合、すべての兵士は目標マスから1マス離れているため、スコアは

${\displaystyle S_{2}=\varphi S_{1}=3+2\varphi }$。

同様に:

${\displaystyle S_{3}=\varphi S_{2}=2+\varphi }$、

${\displaystyle S_{4}=\varphi S_{3}=1+\varphi }$、

${\displaystyle S_{5}=\varphi S_{4}=1}$。

兵士が有限回数の移動の後に目標マスに到達すると、終了構成のスコアは となり、 は目標マスにいる兵士の貢献度を表し、 は平面上の他の場所に残っている無限の数の兵士の (小さいが正の) 貢献度を表します。 ${\displaystyle E=\varphi ^{0}+\epsilon }$${\displaystyle \varphi ^{0}}$${\displaystyle \epsilon }$

したがって、目標のマス目が兵士の無限半平面の上の 5 行目にある場合、開始構成のスコアは であり、終了構成のスコアは であり、どのようなジャンプでもスコアが増加することはないため、 となることが示されました。これは矛盾です。つまり、有限回のジャンプの後、どの兵士も 5 行目のマス目に到達することは不可能です。 ${\displaystyle S_{5}=1}$${\displaystyle E=1+\epsilon }$${\displaystyle S_{5}\geq E}$

• E. Berlekamp、J. Conway、R. Guy、「数学的プレイで勝つ方法」、第 2 版、第 4 巻、第 23 章: 803—841、AK Peters、マサチューセッツ州ウェルズリー、2004 年。
• R. Honsberger、「チェッカージャンピングの問題」、Mathematical Gems II、第3章: 23-28、MAA、1976年。

• cut-the-knot.org でゲームの説明
• ゲームのいくつかのバリエーションを最近の参考文献とともに説明するページ
• ワイスタイン、エリック W.「コンウェイの兵士」。MathWorld。
• ゲームのインタラクティブバージョン（1）
• ゲームのインタラクティブバージョン（2）
• さらにオンラインマガジンがゲームについて解説