コンウェイの兵隊

コンウェイの兵隊、またはチェッカージャンピング問題は、ある行より手前にチェッカー駒を並べた状態から、その行からできるだけ奥に駒を届ける1人用の数学ゲーム・パズルである。チェッカージャンピング問題とも呼ばれるが、ペグ・ソリテールの変種と考えたほうがわかりやすい。無限に広いチェッカーボード上で行い、ある行より下にのみ好きなだけ駒（兵）を置いて良い。ペグ・ソリテールと同様に、駒は縦横に隣接する駒を飛び越え（ジャンプし）、その飛び越された駒を盤上から取り除く（斜めに飛び越えてはいけない）。 この「飛び越えて除去」の繰り返しのみを用い、可能な限り上に駒を届けるゲームである。 コンウェイは、いかなる戦略を用いても、（有限手数では）駒を5マス以上進められないことを証明した。コンウェイはマスに黄金比を用いた重み付けを行い、その重み付け和が増加しないことを用いて証明した。この議論は多くの数学書に掲載されている。 サイモン・タタムとガレス・テイラーは、無限の手数を用いれば5マス目に到達できることを示した。この結果はピーター・ブルーとステファン・ハートキの論文にも掲載されている。もし斜めに飛び越えていい場合には8マス目まで到達可能であるが9マス目には到達できない。また、n次元に拡張した場合、3n-2マス目まで到達でき、コンウェイの重み付けによって、3n-1マス目には到達できないことがわかる。3n-2マス目に到達する証明は非常に困難である（エリクソンとリンドストームの論文を参照）。