イギリス盤ペグソリティアを数学的に解析 : ３色パリティとパゴダ関数（１）　

ペグソリティア（パズル）を数学的アプローチで解こうとする試みは、
'The ins and outs of peg solitare'
という洋書によって、ほぼ完ぺきな理論が示されています。

そして、ラジくまるはその洋書をせっかく輸入購入したのに、文章の意味を理解できなかった・・・・と白状しました。
というお話を、以前の記事に書いております。

このたび、Pressman社の'Think & Jump'の記事を書くにあたり、再び「ペグ・ソリティア・パズル」をネット調査やりなおしてみました。
そうしたらJaap's Puzzle Page というサイトを発見したのです。
その中に'The ins and outs of peg solitare'の理論を、豊富な図解をつけて解説しているページがありました。

Analysis of Peg Solitaire

なんということでしょう・・・・・・・。
Jaapさんが描いた数多くの図解のおかげで、ラジくまるはついに'The ins and outs of peg solitare'のキモにたどりつくことができました。

・・・・あいかわらず、数学理論のほうは、もやっとしていて理解できてないんですが。

Jaapさんありがとうございました。この場を借りてお礼申し上げます。

ラジくまるがペグ・パズル解析の数学的アプローチをどこまで理解したのか、今回は、そんなあたりを記事化してご紹介したいと思います。
「数学が本当に得意な人」が「サルでもわかる数学の本」みたいな数学解説本を書く時、あるいはそういう趣旨の教育番組を作るときに、ぜひ、この記事を参考にしていただきたいとの願いを込めています。ご活用いただければ幸いです。

数学があまり得意じゃない人（ラジくまる）は、どんなところで数学理論につまづいちゃうのか。というところをわかっていただきたい！という切実な願いが、この記事には詰まっております。

＊＊＊

では、理解できた内容についてお話します。

ペグ・パズルの数学的な解析アプローチは２段階ステップで行われます。
１段目が「３色パリティ」で、２段目が「パゴダ関数」です。

まず本日は「３色パリティ」について解説します。

解析の第一段階：「３色パリティ」
イギリス盤ペグソリティアは、全部で33マスのジャンプ・パズルです。
まずはともかく、「直線状にならんだ3マス」が必ず色が異なるという条件で３つの色に塗分けます。
塗分けした結果、赤青黄すべてが11個ずつになりました。

ここで、任意の赤マスからペグ１個を除去してみます。
するとこのパズルの初期条件でのペグ個数は以下の通りになります。
赤10個
黄11個
青11個
（それぞれの色のマスに、何個のペグがあるか？）

この状態を（赤黄青）＝（偶数、奇数、奇数）のパリティ状態と呼ぶことにします。

ソリティア盤のことは、いったんちょっと横に置いて、まずはとりあえずペグジャンプという行動を深掘りしてみましょう。
下の図のようにジャンプすると「赤１黄１青０」から「赤０黄０青１」に変化します。

逆方向のジャンプも全く同様です。「赤０黄１青１」から「赤１黄０青０」に変化します。
図でわかる通り「１つジャンプ」が実行されるたびに「３色パリティ」の奇数と偶数とが全部反転（Flip-Flop）するのです。パズル盤面上のどこかでジャンプが１回実行されると、必ず（赤黄青）の３色全部がパリティ反転するわけです。

ジャンプ前→ジャンプ後
（偶偶偶）→（奇奇奇）
（奇偶偶）→（偶奇奇）
（奇奇偶）→（偶偶奇）
（奇奇奇）→（偶偶偶）
（偶奇偶）→（奇偶奇）
（奇偶奇）→（偶奇偶）

ここまでわかったところで、再び33マスのイギリス・ソリティア盤に戻りましょう。
初期状態で32本のペグがあり、ジャンプ１回で１本減少するのですから、最後の１本になるまでの間に31回のジャンプを実行したはずです。

（偶奇奇）→31回ジャンプ→（奇偶偶）
　全32本　　　　　　　　　　全1本　

イギリスソリティア盤の初期状態は（赤黄青）＝（偶奇奇）です。
この状態から31回ジャンプしたら、その時のパリティは、（赤黄青）＝（奇偶偶）になります。そして31回のジャンプが実行できたならば、盤面に残っているペグ本数は１本になっているはずです。

初期状態
赤　偶数　（１０本）
黄　奇数　（１１本）
青　奇数　（１１本）

最後に１本が残った状態
＊初期状態から３１回のジャンプに成功した場合
赤　奇数　（１本）
黄　偶数　（０本）　
青　偶数　（０本）
ここに書いたように、最初に赤（中心のマス）のペグを除去してからパズルを開始すると、最後の１本は赤のマスに残るということが、３色パリティによって「予言」できてしまうのです。

注意：ここで紹介したパリティによる判定結果では「ものすごく成功する確率が高い」というとがわかっただけなんだそうです。うまくいかないペグの初期状態もありえるとのこと。

ところで、さっきは説明しませんでしたが、もしペグパズルの初期状態が
（偶偶偶）とか（奇奇奇）だった場合には「最後に１本のペグが残る」という状況は不可能です。初期状態がそういうペグパズルは絶対に解けません。
その理由は、最後の１本になった瞬間に３色パリティの値が（奇奇奇）になることはありえないからです。
どうなるのかと言えば、３本が飛び飛びに残って終了するか、あるいは運が良ければ「同じ色のマスに２本残る」か、どちらかにしかできないと予想されます。

来週は「パゴダ関数」のお話をします。