五線の必勝法


きっとどなたも、学生時代に、友達と、紙の上でこのゲームをしたことがあるでしょう。


ルール:

棒が何本か紙に書かれている。最もよく見られるルールは、「1列目に縦棒1本。2列目に2本。・・・5列目に5本。」とピラミッド状に並んだものである。しかし、ここではもっと一般的に考えて、1列目に本、2列目に本、・・・列目に本・・・列目に本あるとする。2人が交互に棒を消していく。消すことができるのは、横に連続している棒のみ。途中ですでに消してある棒を横切ることはできないし、異なる列の棒を同時に消すこともできない。そして、最後の棒を消した人が勝ち。このことは次のように定式化できる。まず、集合とする。各プレイヤーはに対して次のような操作をする。

操作: の元を一つ選び、それをとする。そして、2つの0以上の整数となるように選ぶ。そして、の中からを除き、が0より大きければそれをに付け加える。

この操作を交互に行い、を空集合にしたプレイヤーの勝ちとする。


定理の前にいくつかの関数を定義する。

を2進法で表す。このとき、桁目の数字をで表すことにする。


定理:

五線は、次の場合、後手必勝である。

任意のに対し、(*)が成り立つ。

                         (*)

それ以外の場合、先手必勝である。


証明:

初期状態から、先手が操作を行い、にしたとする。

この操作のあとのに対しては、「任意のに対して(*)が成り立つ」ことはない。なぜなら、もし成り立ったとすると、

任意のに対して、


となる。すると、が成り立つについては、

あるいは  が成り立つ。

よって、となるが、これは、操作の条件と矛盾する。

そのため、操作の後は(*)が成り立たない。ここで、(*)が成り立たない最大のとする。このとき、である。なぜなら、もしとすると、となり、また、に対して、となる。よって、となり、矛盾が生じる。

だから、であり、

ここで後手は、であり、操作前には任意のに対して(*)が成り立っていたことから、操作後のから、であるようなを選ぶことができる。後手は、からをとり、任意のに対して、操作後に(*)が成り立つように、を選ぶことができる。よって、後手は、にする操作を行えば、任意のに対して(*)が成り立つようにできる。

さて、の元の数の総和は、操作をするたびに単調に減っていく。よって、いつかはは空集合になり、ゲームは終了する。

ゲームが終了するとき、それは任意のに対して(*)が成立しているから、最後の操作をすることができるのは後手である。よって、後手必勝。


それ以外の場合、先手必勝であることを次に示す。

(*)が成り立たないのうち最大のものをとする。すると、であるようなの元が少なくとも1つ存在する。それで、を選び、操作後に、任意のに対して(*)が成り立つように、を選ぶことができる。よって、にする操作を行えば、任意のに対して(*)が成り立つようになる。前の場合の結果より、先手必勝となる。

(証明終わり)


一般に行われている五線のゲームでは、最後の棒を消した人が負けとするルールのほうが多いかもしれない。しかし、必勝法は、上に示した証明とほぼ同じで考えることができる。

inserted by FC2 system