30パリティ 偶奇性

さて、久々の数学の話です。

そもそも私が偉そうに話せる数学の話題があんまりないってのがあるんですよねｗ

なぜブログで取り上げようと思ったやらｗｗ



というわけで、パリティ、偶奇性のお話です。

まずはこちらのゲームです。
http://www.gamedesign.jp/flash/police/police_jp.html

このゲームで一通り遊んでみてください。

警官が泥棒を捕まえたら勝ちなのですが
勝つ方法がわかりますか？








このゲーム、勝つには警官は一番下の曲がっている道を通らないといけないんです。

図を使って説明しましょう。

ボードはこんな感じでしたね？（並び方は変えました。）

この、マス目（円形ですが）を色分けしてみましょう。すると…

背景の色が変わったのはエンコードが原因のようです詳しくは不明

実は、こうして色分けした場合、

右下を除いて、どこにいても、次に移動できるますは違う色になってるんです。

先ほどのゲームでの初期位置は、警官と泥棒は同じ色にあたるますに立っています。

その状態から警官から動き出すので、泥棒のいる色のマスにはふつうはどうやってもたどり着けません。

しかし、右下の通路だけは、唯一黄色から黄色への移動ができるのです。

これにより、泥棒のいるますに追いつけるようになるのです。

このとき、左上のマスからそれぞれのマスへ移動するのにかかる最短手数を書き出すと、

さらに色が変わる……どういうことなの……

このように、赤色のマスは偶数、黄色のマスは奇数となっています。

ここから、このような性質を偶奇性と呼ばれます。

すなわち、偶数の次は奇数、奇数の次は偶数、というわけです。

この偶奇性のかかわる問題は、ほかにもスライドパズルにもあります。

おそらく箱入り娘と一二を争うほど有名なスライドパズル、１５パズルの問題で、

サム・ロイド氏が高額の賞金を懸け出題した問題として、以下のようなものがあります。

部分的に線が細いのもエンコ（ｒｙ

これは、答えが出せない問題なんです。

証明までは忘れましたが、これを完成形にするために

直接はがして入れ替えた場合の入れ替える回数が

奇数回の場合、完成させることができないんです。

これもまた偶奇性の問題になります。

この問題が発表されて以降は、この偶奇性の問題も考えたスライドパズルが多く登場したんだそうですが、その辺まではよく知りません。

そのうち、偶奇性とかちょっと研究してスライドパズル得意になれたらなぁ…なんて考えてる私でした。

長くなっちゃってすんません。

明日からは塩さんプログラム進めようかなぁなんて。