五線の必勝法

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

ルール：

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

操作 $F$ ：　 $M$ の元を一つ選び、それを $b$ とする。そして、2つの0以上の整数 $c,d$ を $c+d<b$ となるように選ぶ。そして、 $M$ の中から $b$ を除き、 $c,d$ が0より大きければそれを $M$ に付け加える。

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

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

$a$ を2進法で表す。このとき、 $a$ の $k$ 桁目の数字を $keta_{k}(a)$ で表すことにする。

定理：

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

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

$\displaystyle \sum_{a\in M}keta_{k}(a)\equiv 0 (mod 2)$ 　　　　　　　　　　　　　　　　　　　　　　　　　(*)

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

証明：

初期状態から、先手が操作 $F$ を行い、 $a\in M$ を $b,c$ にしたとする。

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

任意の $k$ に対して、

$keta_{k}(a)\equiv keta_{k}(b)+keta_{k}(c) (mod 2)$

となる。すると、 $keta_{k}(a)=keta_{k}(b)+keta_{k}(c)=1$ が成り立つ $k$ については、

$keta_{k}(b)=1$ あるいは　 $keta_{k}(c)=1$ が成り立つ。

よって、 $a\leqq b+c$ となるが、これは、操作の条件 $a>b+c$ と矛盾する。

そのため、操作 $F$ の後は(*)が成り立たない。ここで、(*)が成り立たない最大の $k$ を $m$ とする。このとき、 $keta_{m}(a)=1$ である。なぜなら、もし $keta_{m}(a)=0$ とすると、 $keta_{m}(b)+keta_{m}(c)=1$ となり、また、 $n(>m)$ に対して、 $keta_{n}(a)\leqq keta_{n}(b)+keta_{n}(c)$ となる。よって、 $a\leqq b+c$ となり、矛盾が生じる。

だから、 $keta_{m}(a)=1$ であり、 $keta_{m}(b)=keta_{m}(c)=0$ 。

ここで後手は、 $keta_{m}(a)=1$ であり、操作 $F$ 前には任意の $k$ に対して(*)が成り立っていたことから、操作 $F$ 後の $M$ から、 $keta_{m}(d)=1$ であるような $d$ を選ぶことができる。後手は、 $M$ から $d$ をとり、任意の $k(\leqq m)$ に対して、操作後に(*)が成り立つように、 $e(<d)$ を選ぶことができる。よって、後手は、 $d$ を $e,0$ にする操作を行えば、任意の $k$ に対して(*)が成り立つようにできる。

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

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

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

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

(証明終わり)

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