石取りゲーム必勝法 -PART3- 三山崩しにチャレンジ

石取りゲームは、最初に用意した石を決められたルールにしたがって取っていき、 勝ち負けを決めるゲームです。最初に用意する石の数や石の取り方を変えることで、いろいろな遊び方を楽しむことができます。今回は三山崩しというゲームにチャレンジしてみましょう。
　三山崩しは昔からある有名なゲームです。石の山を3つ用意します。石は1つの山からしか取れません。取ることのできる石の数は1個以上無制限です。このゲームも、石を最後に取った方を勝ちとする「最後が勝ちゲーム」と最後に取った方を負けとする「最後が負けゲーム」の2種類考えることができます。ここでは「最後が勝ちゲーム」の必勝法を考えてみましょう。

　三山崩しの必勝手は不思議なことに2進数を使います。2進数についは興味のある方は『2進数は神の数？』の記事を読んでみてください。
　さて、3つの山の石の個数を x, y, z とします。これを3つの組 ( x, y, z ) で表すことにします。たとえば x＝15, y＝20, z＝30 としましょう。これを2進数に変換します。

表1 のように、与えられた数を2で割っていきます。次に、奇数なら1を、偶数なら0を記入します。得られた0と1の列を下から上へ読むと2進数になります。得られた2進数を表 2のように配置します。一番右端の桁を第0桁、次を第1桁と、右から左に桁を数えます。

表が完成したら各桁の1の数を数えます。このとき次が成立します。

『各桁の和がすべて偶数なら先手は必敗、そうでなければ必勝である』

表2の場合、第2桁の合計は3で奇数、第0桁の合計は1で奇数、その他の桁の和はすべて偶数です。したがって ( 15, 20, 30 )の山でゲームを始めた場合は先手必勝です。

 

( x, y, z ) が必勝手なら、うまく石をとると必敗手にして後手に回せることを示しましょう。もう一度( 15, 20, 30 )の場合を見てみましょう。

和が奇数である、もっとも左側の桁を考えます。表2では、第2桁です。この場合は、x, y, z の第2桁すべてが　1 ですからどれを選んでもかまいません。和が 1 の場合は、その桁が1 のものを選びます。ここでは x を選ぶことにします。x の第2桁を0とします。x のこれより右の桁は y と z により一意的に定まります。第1桁の1はそのままとし、第0桁の 1 は 0 に変更します。この作業は x の山から 5個取り去ったことを意味します。2進数で表すと、1111 から 1010 となります。ここでそれぞれの桁の1を合計してみましょう。全ての桁の合計が偶数になっているので、必敗の形になっています。

　次に必敗の形で順番が回ってきた場合、つまりそれぞれの桁の和が全て偶数の状態から石を取るとどうなるかを見てみましょう。たとえば x の山から石を取るとします。すると、x の2進数表示の桁の中に「1から0に変わる」あるいは「0から1に変わる」桁があるはずです。このような桁がなければ、x は何も変わらないからです。そのように変わった桁では、1の個数の和は奇数となります。これは必勝手です。つまり必敗手の形で自分の番になった場合は、どのように石をとっても必勝手の形を相手に回すことになるのです。

2進数は三山崩しのために考え出された記法ではありません。2進数がゲームの戦略に役に立つとは、不思議な気がしませんか？　何も関係がなさそうに見えても、このように役に立つ概念が数学にはたくさんあるのです。私たちは普段の生活で2進数を意識して使うことはあまりありません。しかし「10進数さえ知っていれば他は知らなくてもよい」と決めてしまうことなく、様々な数学の概念に触れることで、少し違った角度から物事を捉えられるのではないかと思います。

▼ 関連記事

▼Twitter、Webマガジンサイトも更新中。よろしくお願いいたします。
Twitter: @mathematicasite
Web:http://mathematica.site/