コンウェイの兵隊のソースを表示

'''コンウェイの兵隊'''、または'''チェッカージャンピング問題'''は、ある行より手前にチェッカー駒を並べた状態から、その行からできるだけ奥に駒を届ける1人用の数学ゲーム・パズルである。チェッカージャンピング問題とも呼ばれるが、[[ペグ・ソリテール]]の変種と考えたほうがわかりやすい。無限に広いチェッカーボード上で行い、ある行より下にのみ好きなだけ駒（兵）を置いて良い。ペグ・ソリテールと同様に、駒は縦横に隣接する駒を飛び越え（ジャンプし）、その飛び越された駒を盤上から取り除く（斜めに飛び越えてはいけない）。 この「飛び越えて除去」の繰り返しのみを用い、可能な限り上に駒を届けるゲームである。

[[ファイル:Conway's_soldiers.svg|thumb|500px|それぞれのマスに到達可能なコンウェイの兵隊の配置例。]]

コンウェイは、いかなる戦略を用いても、（有限手数では）駒を5マス以上進められないことを証明した。コンウェイはマスに[[黄金比]]を用いた重み付けを行い、その重み付け和が増加しないことを用いて証明した。この議論は多くの数学書に掲載されている。

サイモン・タタムとガレス・テイラーは、無限の手数を用いれば5マス目に到達できることを示した。この結果はピーター・ブルーとステファン・ハートキの論文にも掲載されている。もし斜めに飛び越えていい場合には8マス目まで到達可能であるが9マス目には到達できない。また、''n''[[次元]]に拡張した場合、3''n''-2マス目まで到達でき、コンウェイの重み付けによって、3''n''-1マス目には到達できないことがわかる。3''n''-2マス目に到達する証明は非常に困難である（エリクソンとリンドストームの論文を参照）。

== 有限の駒では5マス目に到達できない証明 ==

=== 表記及び定義 ===
目標とするマス（目的地）を <math>{x^0 =1}</math>とする。そして、他のマスはそのマスからのマンハッタン距離<math>n</math>を用いて<math>{x^n}</math>とする。すると、駒の初期配置に対してその合計値（例えば、 <math>{x^2 + 2x^3}</math> 等）を対応させることが出来る。これを、盤面の''得点''と呼ぶ。<math>x^{n}</math>マスにいる駒が他の駒を飛び越える操作は、以下の3つの場合に分けられる。
# 前飛び：駒が目的地に向かって飛び越えた場合。得点の変化は<math>{x^{n-2} -x^{n-1} -x^n = x^{n-2}(1 -x -x^2)}</math>となる。
# 横飛び：飛び越えによってその駒が目的地に近づきも遠ざかりもしない場合（役に立たないようにも感じられるが、必要である）。得点の変化は <math>{-x^{n-1}}</math>となる。
# 後ろ飛び：駒が目的地から遠ざかる方向に飛び越えた場合。得点の変化は<math>{x^{n+2} -x^{n+1} -x^{n} = x^{n}(x^{2} -x -1)}</math>となる。

=== <math>x</math>の選択 ===
上記の3つの操作の全てにおいて、得点の変化が正とならない<math>x</math>を選択する。 前飛びの条件より、<math>{x^2 +x -1 = 0}</math>を解くことによって <math>{x =\frac{\sqrt{5} -1}{2}, \frac{-\sqrt{5} -1}{2}}</math>を得る。横飛びの条件より正の値は取れないため、<math>{\frac{\sqrt{5}-1}{2} = \varphi \approx 0.61803\,39887\dots\,}</math>が適している。この値の絶対値は1よりも小さく、この性質は証明に重要である。ここで、<math>{\varphi^2 +\varphi -1 = 0}</math>を並び替えると

<math>{\varphi^2 = 1 - \varphi}</math> （両辺に<math>{\varphi}</math>を乗ずる） 

<math>{\varphi^3 = \varphi - \varphi^2}</math>

<math>{\varphi^4 = \varphi^2 - \varphi^3}</math> 

と出来る（以降同様）。
この右辺を足し合わせると1以外の項は打ち消し合うため、

<math>{\sum_{n=2}^{\infty}\varphi^n = 1}</math>

となる。一方で、左辺は等比級数であるため、

<math> \sum_{k=2}^\infty \varphi^{k} = \frac{1}{1-\varphi} - \varphi - 1= 1</math>

である。

=== 証明 ===
まず、目的地が1マス上にある場合を考える。初期配置の得点を最大化すると、全てのマスに駒がある状態に相当する。

まず、1行目だけを考える。1行目（最前行）の得点は<math>{\varphi +2\varphi^2 +2\varphi^3 + \ldots = \varphi +2(\varphi^2 +\varphi^3 + \varphi^4 + \ldots)}</math>となる。次の行以降では、各マスが1マスだけ距離を増すため、1行離れるたびに得点は<math>\varphi</math>倍になる。

そのため、全てのマスの得点を合計すると、

<math>{{S}_1=(\varphi +2(\varphi^2 +\varphi^3 + \varphi^4 \ldots))(1 +\varphi + \varphi^2 + \varphi^3 + \ldots)}</math>

となる。

ここで、<math>\sum_{n=2}^{\infty}\varphi^n = 1</math>であるため、上記の式は

<math>{{S}_1=(\varphi + 2)(1 + \varphi + 1) = (\varphi + 2)^2 = 4 + 4\varphi + \varphi^2 = 5 + 3\varphi}</math>となる。（最後の変形は <math>{\varphi^2 = 1 - \varphi}</math> を用いている）

したがって、全てのマスに駒がある場合、その得点は<math>{5 + 3\varphi}</math>である。
次に、目的地が2マス上にある場合を考える。この場合、目的地までのマンハッタン距離は、先ほど考えた目的地が1マス上にある場合より1マスずつ増加する。したがって、<math>{\varphi}</math>を全体に乗じ、

<math>{{S}_2=\varphi(5 + 3\varphi) = 5\varphi + 3\varphi^2 = 5\varphi + 3(1 - \varphi) = 3 + 2\varphi }</math>を得る。

同様に

<math>{{S}_3 = 2 + \varphi }</math>

<math>{{S}_4 = 1 + \varphi }</math>

<math>{{S}_5 = 1 }</math>

となる。

したがって、目的地が5マス上にある場合、得点は最大でも1である。駒が有限である場合、合計は1未満となる。どの操作も得点は増加しないため、最終得点も1より小さい。一方で、目的地に移動できる場合には、他の駒が存在しない状態でも得点が <math>{\varphi^0 = 1}</math> である必要がある。したがって、有限の駒では5マス上には到達不可能である。

== 参考文献 ==
* E. Berlekamp, J. Conway and R. Guy, Winning Ways for Your Mathematical Plays, 2nd ed., Vol. 4, Chap. 23: 803—841, A K Peters, Wellesley, MA, 2004.
* R. Honsberger, A problem in checker jumping, in Mathematical Gems II, Chap. 3: 23—28, MAA, 1976.
* H. Eriksson and B. Lindstrom, Twin jumping checkers in Z_d, Europ. J. Combinatorics, 16 (1995), 153–157.
* G. Bell, D. Hirschberg and P. Guerrero, The minimum size required of a solitaire army, [http://www.integers-ejcnt.org/ INTEGERS Electronic Journal of Combinatorial Number Theory], Vol 7, G7, 2007. 

== 外部リンク ==
* [http://www.cut-the-knot.org/proofs/checker.shtml cut-the-knot.org explains the game]
* [http://www.gibell.net/pegsolitaire/army/index.html A page describing several variations of the game, with recent references]
* {{MathWorld|title=Conway's Soldiers|urlname=ConwaysSoldiers}}
<div class="cx-template-editor-source-container" lang="en" dir="ltr" style="display: none;"><div class="cx-template-editor-source"><div class="cx-template-editor-title">MathWorld</div><div class="cx-template-editor-param"><div class="cx-template-editor-param-title"><span id="title" class="cx-template-editor-param-key">title</span></div><div class="cx-template-editor-param-value" data-key="title" id="Reference-Mathworld-Conway.27s_Soldiers-title-" style="position: relative;">Conway's Soldiers</div></div><div class="cx-template-editor-param"><div class="cx-template-editor-param-title"><span id="urlname" class="cx-template-editor-param-key">urlname</span></div><div class="cx-template-editor-param-value" data-key="urlname" id="Reference-Mathworld-Conway.27s_Soldiers-urlname-" style="position: relative;">ConwaysSoldiers</div></div></div></div><div class="cx-template-editor-source-container" lang="en" dir="ltr" style="display: none;"><div class="cx-template-editor-source"><div class="cx-template-editor-title">MathWorld</div><div class="cx-template-editor-param"><div class="cx-template-editor-param-title"><span id="title" class="cx-template-editor-param-key">title</span></div><div class="cx-template-editor-param-value" data-key="title" id="Reference-Mathworld-Conway.27s_Soldiers-title-" style="position: relative;">Conway's Soldiers</div></div><div class="cx-template-editor-param"><div class="cx-template-editor-param-title"><span id="urlname" class="cx-template-editor-param-key">urlname</span></div><div class="cx-template-editor-param-value" data-key="urlname" id="Reference-Mathworld-Conway.27s_Soldiers-urlname-" style="position: relative;">ConwaysSoldiers</div></div></div></div>
* [http://www.cleverlearning.co.uk/blogs/blogConway.php Interactive version of the game]
* [http://plus.maths.org/issue12/xfile/ Plus online magazine describes the game]
* [http://tartarus.org/gareth/maths/stuff/solarmy.pdf Tatham and Taylor's paper]
* [http://mathproblems.info mathproblems.info (search for #15 Checker problem)]
* [http://www.chiark.greenend.org.uk/~sgtatham/solarmy/ A solution to the fifth row using an infinite number of moves]

{{DEFAULTSORT:こんうえいのへいたい}}
[[Category:数学パズル]]