06. ペグソリティア -解けないパズルを解く方法-

ペグソリティアというパズルを御存知だろうか. 図1のような穴の開いた盤にペグを刺して遊ぶパズルである. 図1中の黒丸(白丸)は, ペグが刺さっている(いない)ことを表している. 通常用いられる図1のような盤は English board と呼ばれる.

図1: English board の初期配置例.

図1: English board の初期配置例.
図中の ● (○) はペグの刺さっている穴(いない穴) を表す.

図2: ジャンプの例.

図2: ジャンプの例.

図2(a)のように連続する3つの穴の1つ目と2つ目にペグが有り, 3つ目の穴にペグが無いとき, 図2(b)のように飛び越えて中央のペグを除き, 図2(c)のように1つのペグを残すことができる. この操作をジャンプと呼ぶ. ジャンプを実行できる3つの穴の並びは, 縦の上から下, 縦の下から上, 横の右から左, 横の左から右の4通りがある. ペグソリティアは, 与えられた初期配置から, ジャンプを繰り返し行って, (与えられた) 最終配置に到達する手順を探すパズルである.

あるペグ配置に対し, ペグが刺さっていない所にペグを刺し, ペグが刺さっている所にはペグを刺さない配置を, 補配置と呼ぶ. 例えば図1の補配置は, 中央の5箇所のみにペグが刺さっている配置となる. では次のような命題を考えよう.

図1を初期配置として, ジャンプを繰り返し行って,図1の補配置に到達する手順は存在しない.

Berlekamp, Conway and Guy(1) は, 次のような巧妙な方法でこの問題が解けないことを示している. まず最初に, ゲーム盤の各マス(穴)に図3のような数字を割り当てる. 任意のペグ配置p に対し, ぺグが刺さっているマス目の図3での値を合計したものを pag(p ) と書く. 例えば図1の配置をps と書くとpag(ps) = 4 である. また図1の補配置をpf と書くと

図3: パゴダ関数の例

図3: パゴダ関数の例

 

pag(pf) = 6 となる. 実は図3の値は非常に巧妙に割り当てられており, どの連続する3つのマス目についても, 対応する数字を(a, b, c ) と書くと, a + b ≥ c が成り立っている. 連続する3つのマス目の方向は4つあることに注意されたい(ゆえにa ≤ b + c も同時に成り立っている). これより, ある配置p1 から1回のジャンプ操作で配置p2 が得られたとき, ペグの取り除かれた2箇所の値の和より, ペグの刺し込まれた場所の値の方が同じか小さい. したがって必ずpag(p1) ≥ pag(p2) が成り立つ. すなわち, ジャンプ操作によって, 配置に対する値pag(・)は単調非増加となっている(2). ゆえに, ある配置p1 から(何回かの) ジャンプ操作で配置p3 が得られたとき, 必ずpag(p1) ≥ pag(p3) が成り立つ. ところが上記の問題では, 初期配置ps と最終配置pf は4 = pag(ps) < pag(pf) = 6 を満たしており, このことから初期配置からジャンプ操作で最終配置に到ることは不可能であることが分る.

Berlekamp, Conway and Guy は図3の値を, 各マス目に実数を対応させる関数と見なし, パゴダ関数と呼んでいる(3).ペグソリティアを解く『手順が存在しない』事を示すには, この「パゴダ関数」のような巧妙なカラクリを考案する必要がある.

黄金比が現れる美しいパゴダ関数を使う例として, peg solitaire army (Conway's soldiers)と呼ばれるパズルが解けないという有名な証明がある. 興味のある方は, Berlekamp, Conwayand Guy の本を参照されたい(4).

 

(1)E. R. Berlekamp, J. H. Conway, and R. K. Guy,
"Winning Ways for Mathematical Plays (2nd Edition, vol. 4)," AK Peters, 2004.

(2)配置に対するポテンシャルの類と考えることができる.

(3)名前の由来はBerlekamp, Conway and Guy の本を参照のこと.

(4)日本語訳が近年出版本としては, 例えば以下でも読むことができる.
A. Beutelspacher and B. Petri, 柳井浩(翻訳), 『黄金分割―自然と数理と芸術と』, 共立出版, 2005.