第7回:必勝法

 「たけしのコマネチ大学数学科」の第7回目。今回の問題は、ゲーム「三山くずし」の必勝法を考えなさいというもの。

 問題:「3個、5個、7個の石がある。交互に石を取っていき、最後の石を取ったほうが勝ち。石はいくつ取ってかまわないが、違う山(色)の石を同時に取ることはできない。このゲームの必勝法を考えなさい」

Ex_071_1  例によって「エクセル」で表を作ってみる。A列は「=DEC2BIN(C2)」として、C列に入力された石の数を参照して、二進数に変換している。B列の石の山は「=REPT("●",C2)」で、石の数ぶんの「●」を表示している。

 ここまで作成すると、やはり、対戦してみたくなる。しかし「エクセル」でインタラクティブなものを作ろうとすると、どうしても「VBA」を使わざるをえない。「VBA」とは「Visual Basic for Applications」の略で、マイクロソフトの「Office」製品で処理を自動実行させるためのプログラム言語だ。今回の問題は「VBA」の入門として、ちょうどいいかもしれない。

 さっそく「表示」メニューの「ツールバー」から「コントロールツールボックス」をクリックし、ボタンをひとつ作成。このボタンが押されたときの処理を「VBA」で記述する。第6回の二進数の説明のとき「エクセル」では、論理演算子はビット演算ができないと書いたが、「VBA」を使えば、話は別だ。「Xor」(排他的論理和)も使うことができる。

Ex_072  (※クリックで拡大)

 これで、石の数を減らし「決定」ボタンを押すと、「エクセル」の番になり、石を取る。何も考えていない「エクセル」に必勝法を教えるということは、同時に自分自身がこの問題の「必勝法」に対する理解を深め、より短い記述で整理することにつながる。その結果、先手必勝だが、途中で一度でもミスをすると負けてしまうことになる(^^;。必勝法は、番組を見た方なら、すでにご存知のはず。

六芒星のパズル

 このブログにトラックバックを送ってくれた「Atelier-T.T ゲームプログラミング工房」で「六芒星(ろくぼうせい)」のパズルをプログラミングで解くというおもしろい試みをしている。

Tr_011  パズルのルールを確認しておくと、図の○の部分に1~12までの数字を入れ、各列の合計がすべて同じになるようにする(数字は重複使用してはならない)。

 私は「C++」を持っていないし、使ったこともないので、公開しているプログラムを試してみることはできないのだが、「エクセル」で挑戦してみようという気になった。

 もしも、この問題を「コマ大数学研究会」のように体を張り、ひとつひとつ数字を入れて確かめる方法をとったならば、どれくらいの組み合わせが考えられるのだろうか。

Tr_012  一度使った数字は使えないので「=12×11×10……×1」とエクセルで計算すると「479001600」通りとなった。これは「12の階乗」だ。掛け算をいくつも並べるのは面倒なので、「エクセル」にも関数が用意されていて「=FACT(12)」とすれば、答えが出る。

 4億7900万通りをすべて調べるわけにもいかない。「エクセル」でこの問題を解くのは無理っぽい。そこで、いくつかの仮説を立てる。まず、1列の4つの数字を足した合計がいくつになるか。1~12までを全部足すと「78」、これを12で割ると、ひとつの○に入る数字の平均は「6.5」、それが4つで「26」だ。

Tr_012b 仮説1:列の合計は「26」
仮説1が正しければ、1列には偶数2個、奇数2個が入る(もしくは、偶数4個、奇数4個の組み合わせも考えられる)。
辺の頂点、交差するところで数字は2回使われるので、ひとつの列を考えると、前半部分だけを決定すれば、後半部分は他の列によって自動的に決まる。

Tr_013  こうして「六芒星パズル」を解くための(あくまで補助するだけの(^^;」表を作成した。数字はとりあえず便宜的に入れたもの。列(3)と列(4)は、入力する必要はなく、他の列をセル参照している。そして、答えのチェックの意味で列の合計を表示している。これだけでも、図を紙に描いて、数字を書いては消すよりは、ずっとラクちんだ。

Tr_014 Tr_015  まず、A列の「1」と「2」を残して考えてみる。すると、仮説では、列の合計が「26」になるはずなので、残りの後半は、「11」と「12」だ。ここでF列を考えると、すでに「2」があるので、次に大きい「9」と「10」を使う。すると、B列(1)は「5」となる。

Tr_016  同様に列Eは、すでに後半部分に「10」と「1」が入っているので、「7」と「8」を入れると、うまく「26」になる。試行錯誤を繰り返し、完成したのが、この表。なんとかすべての数字を入れることができた。

Tr_017  前出の「Atelier-T.T ゲームプログラミング工房」によると、解は「960」通り。このうち、回転、鏡像による重複は、6×2で12通り。すべての解に対して12通りの重複があるので、この「六芒星パズル」には、80通りの解があることになる(らしい……99.9%の仮説)。