■コマネチ大学数学科71講:サム・ロイド

 「誰にも縛られたくないと♪逃げ込んだこの夜に♪自由になれた気がした♪15のパズル~♪」。盗んだバイクで走り出すのも、15パズルを解くのも、自由だぁ~「たけしのコマネチ大学数学科第71講」。

問題:次の「15パズル」3問のうち、完成させることのできない問題はどれか?

(※註:Flashのチュートリアル(サンプル)にあった「15Puzzle」を使用した)


 「サム・ロイド」は、アメリカのパズル作家。「15パズル」自体は、彼の考案ではないらしいが、「15パズル」をもとにした問題に1000ドルの懸賞金をかけて発表したところ、バカ売れしたらしい。19世紀(1878年)の話だから、1000ドルといっても、大金だったはず。でも、このパズルは解法がなく、懸賞金を手に入れた者はいなかった……というオチがつく。

20071214_00
 で、問題1と問題3は、実際に「15パズル」を遊んでみれば、すぐに完成させることができる。しかし、問題2は、どうがんばっても、完成させることはできない。答えが「2」であることは明白なのだが、その理由、法則を見つけることがポイントになる。問題2の最終形は、[14]と[15]が入れ替わった例題(図)のようになる。

 コマ大数学研究会は、今回、ロケではなく、スタジオで一緒に「15パズル」に取り組む。ダンカンは、解法がないパターンとして紹介された、上の図を見て、右下の「空マス」に接しているのが[12]と[14]、両方とも偶数であることに注目した。そこで、それぞれの問題の[空マス]に接する数字を確かめてみると、以下のようになった。

20071214_01

 答えは「2」で、理由は「偶数」どうしの組み合わせがあるから。「お母さん、偶数でなんとかしてよ」ということで、「マザー・グース―の定理」。

20071214_02
 マス北野は、絶対に解けない(例題)のパターンを知っていた。それに賞金が懸っていたことも。きっとなにかの本で読んだのだろうが、詳細なところまでは思い出せない。しかし、自分自身より数が小さい置き換えが奇数の場合は、解けない……というところまで肉迫した。

20071214_03
 東大生チームは、15個の数字のうち、初期状態から離れた場所にある数字を除くと、残り14個で、7つのペアになる、縦、横の組み合わせを考える。問題1と問題3は、7つのペアが完成するが、問題2だけは、その組み合わせができない。問題を解くカギは「ペアリング」にあるという主張。

 おまたせ。中村亨センセの「美しき数学の時間」だ。「15パズル」は、ひとつの[空マス]を利用して数字を置き換える手順を繰り返し行う。最後に[15][14]のようなパターンになると解けないことは述べた。では、最初にこの「15パズル」は解けるのか、解けないのかを判断する方法とは……。

20071214_04

 まず、[空マス]のある行を左に詰める。そうすると、右端の列に[空]がひとつ出来る。その列の数字を上に移動させ、[空]を右下に作る。そこで、左上から順に、それぞれの数字に対して、自分より小さい数字を数えて、足していく。

 たとえば、問題1の場合は、[空]が右下にあるので、ピースを移動させる必要はなく、左上の数字「4」に対して、それより小さい数の個数をカウントする。[3][2][1]があるので、3個。次に[3]に注目し、同様に数えると[2]と[1]で2個。[2]は、[1]のみの1個だ。以降は、自分より小さい数は出現しない(昇順の並びになっている)ので「0」。この個数を足し合わせると「3+2+1=6」。合計数が偶数の場合は、初期状態に戻すことができる。逆に問題2の場合は、「1+4+1+1+1+4+1+1+1=15」となり、奇数。奇数の場合はパズルを完成させることができない。

 初期状態の、あるいは完成した「15パズル」は、1~15の数字が昇順に並んでいるので、自分より小さい数は出現せず「0」になる。解法がない例題の場合は、[15][14]という並びがひとつだけあるので「1」だ。

 「15パズル」は数字を置き換える操作を繰り返し行うと述べた。つまり「置換」である。中村亨センセは計算で求めたが、これを視覚的に検証してみよう。

 まず、紙と鉛筆を用意し、問題1の場合、上のほうに「4、3、2、1」と書き、下のほうに、正しい順番「1、2、3、4」と書く。それぞれの数字を線で結ぶ。「5」以降は、昇順に並んでいるので省略。

20071214_05

 線の交点を数えると「6個」ある。6回の置換を行っているわけだ。ちょっと前のエントリ「数学基礎:あみだくじ」で、線の交点は「あみだくじ」の横棒にあたること書いた。あみだくじの横棒も6本になり、それぞれが正しい場所に置換されるのだ。念のため、問題2の場合も、同様に線で結んでみよう。

20071214_06

 見ての通り、線の交点は15個。奇数なので、この「15パズル」は完成させることができないことがわかる。

 ところで、今回の問題は、私自身が今年(2007年)の正月にぶちあたった問題でもあった。詳しくは「謹賀新年」の「不可能な『ガスンコ』変換」を参照してほしい。当時は、この問題を解決する、こんなスマートな方法があるなんて考えが及ばなかった;;でも、正月に生じた問題が、2007年も、あとわずかの日数を残すのみだが、とりあえず、年内に解決をみたことは喜ばしい^^;

 でも、冒頭のFlashは、「おまけ」としてピースをランダムにシャッフルする機能を追加したが、完成できるかどうかのチェックはしていない><;

 でも、でも……。すでに、あなたは、それが完成できるか、どうかを最初の状態で判断することができるはず、オッパッピー!(オーシャン・パシフィック・ピース!:太平洋に平和を!)。でも、でも、でも……それを言うなら「It’s peace in the Pacific Ocean.」なんだけど、そんなのカンケーねぇ。


“■コマネチ大学数学科71講:サム・ロイド” への2件の返信

  1. コマネチ大学 #70

    コマネチ大学 #70
    たけしのコマネチ大学数学科#70 2007/12/13 深夜OA
     
     
    今回のテーマは、
    「サム・ロイド」
     
     
    【定番本】
    コマ大数学科
    特別集中講座
    ビートたけし
    ¥1,000
    【New】
    逆転発想力パズル
    脳が目覚める
    竹内薫 中村亨
    ¥1,2…

  2. 福岡でのコマ大放送1回目はこの問題でした。今回の問題は判定方法も知っていましたのですぐに解けました。
     私は(スライド式以外の方法も含めて)2つのコマを入れ替えて完成する入れ替えの回数を数えました。この回数の偶奇でも同じ判定ができます。
     

コメントは受け付けていません。