ニム | 元祖ワシ的日記

ニム

2007年10月16日(火)

ネタがないので敬愛するマーチンガードナー先生の数学ゲームに載ってたやつを紹介。

ニムというのゲームの一種で、いろいろな亜種がありますが、だいたいこんなもんです。
通常二人で行います。

１）チップをいくつかの山にして積んでおく
２）その山から「あるやり方」でチップを取っていく
３）最後のチップを取ったら勝ち（あるいは負け）

「あるやり方」というのがいろいろあるのですが、「１つ山を選んでそこから好きな数だけいくらでもとれる」というのが一番オーソドックスです。

チップを用意できなくても、たとえば財布の中から小銭をばらまいて、同じコインを同時に何枚とってもいい。最後の1枚をとったら勝ち。見たいな感じにすればよいでしょう。

実は、このゲームには必勝法があります。

このルールを知ってれば、相手が間違った手を打てば、必ず勝てます。（必勝法を知らないとまず間違った手をうつ）

その計算方法は美しいんだけれども、ぱっと見た感じ、わかりにくいので、相手はムキになってきますよ。是非試してみてください。

まずは簡単な例から

山が１つしかなければ、先手が絶対勝ちます。（全部とっちゃえばいい）

山が２つの場合は１つのときほど簡単じゃないけど、ちょっと考えると、常に両方の山の高さが同じになるように高い方からチップを取ればよいことがわかります。そうすれば、相手はいつかは手詰まりになり、最後のチップをいつかは取ることができます。

故に面白いのは3つ以上ということになります。

簡単な例を。

もし山を１，２，４ならば４の山から１つとって、１，２，３にすれば必ず勝ちます。

１）相手が1の山をとってしまえば、3の山から1つとり、２，２として勝ち確定
２）相手が2の山から１つとれば、3の山を全部取って、１，１として勝ち確定
３）相手が2の山を全部とってしまえば、3の山から2つとって、１，１として勝ち確定

相手が3の山からとった場合も同様に考えれば、必ず必勝形に持ち込めます。

こんな感じで、この形に持ち込めば勝てるという形は遊んでいくうちに自然とわかってくるとおもいます。

ただ、これが完全な必勝法となると難しい。これを自力で思いつく人はあまりいないんじゃないかな～。おそらくかなり数学の才能がある人かと。

で、結論から言うと、以下のようになります。

各山の数の排他的論理輪が0になるように山を崩していけばよい。そうすれば相手は手詰まりになり、勝てる。

面白いことに二進数と排他的論理和が中心的な役割を果たします。こんなところで排他的論理和が出てくるとは実に興味深い。

この意味がわからない人は以下のように考えてください。

各山の数を１，２，４，８，１６、・・の組み合わせの和であらわし、１，２，４，８，１６、・・の数を数え、偶数になるように山を崩す。

これで勝てます。

ポイントとして、１，２，４，８，１６、・・の各数を2つ以上使わないこと。すなわち0個か1個。

たとえば
７＝１＋２＋４
９＝１＋８
１００＝６４＋３２＋４

必ずこのようにあらわせます。

実際のゲームにおける例を示しましょう。今、山が３つで　１、４、７とします。この場合１４１＋２＋４ですから、１，４の個数は偶数で２の個数が奇数です。故に3つ目の山から2個とり、１，４，５とすれば全ての数が偶数になります。この後、１）相手が１の山を取ってしまえば、５の山から１つとり、４，４として勝利が確定。２）相手が4の山から1つまたは１つとれば、１，２，３に持ち込めるから勝ち確定。３）相手が4の山から３つまたは全部とれば１，１に持ち込めるから勝ち確定。相手が５の山から取った場合も同様に必勝形に持ち込むことができます。なぜこのやり方で勝てるのか証明しようと以前おもったけど、一箇所どうしてもうまく証明できませんでした。そこがなんだったかもよく覚えてませんが、とりあえずこれで勝てます。お試しアレ。

コメント一覧

・・・何となく解ったような解らないような・・・。しかーし！１つだけ完璧に解ったことがあります。それは・・・・この手の勝負でいっせいさんに挑んではいけない、ということです（笑

オセロの「打ち止めの定理」と本質的に同じだね。