◆ 8. tm-kimura さん

いま，アキさんと田中さんでゲームを始めました。 ここに，12 本，1 本，23 本，11 本の 4 つのマッチ棒の山があります。ルールは，好きな山から 1 本以上のマッチ棒を交互に取っていき，最後にマッチ棒を取った方が勝ちです。 先手番となったアキさんは 6 分ほど考えたあと，「私の勝ちですね！」といいながら手を動かしました。さて，アキさんはどの山から何本のマッチ棒を取り去ったのでしょうか。 ただし，一度に一つの山からすべてのマッチ棒を取り去ることはできますが，二山にまたがってはいけません。また，取り去る山はその都度好きな山を選べます。何人の方がアキさんより早いか楽しみにしています。 (12月1日23時11分開始)

▼ 解説 (A)　4 つの山がくずれ，2 つの山になったときは，2 つの山の数を同じにして手をわたす。相手が何本かくずしたら，同じ数を取り去り，再び 2 つの山を同じ数にする。そして，最終的には (2，2) にして手をわたせばよい。(1，2) で返されたときは (1，1) にしてわたす。(0，2) で返されたときは 2 本とも取り去れば勝ちとなる。 (B)　3 つの山になったときは，(1，2，3) にしてわたせばよい。 (0，2，3) で返されたときは (0，2，2) にしてわたす。 (1，1，3) 〃 (1，1，0) 〃 (1，0，3) 〃 (1，0，1) 〃 (1，2，2) 〃 (0，2，2) 〃 (1，2，1) 〃 (1，0，1) 〃 (1，2，0) 〃 (1，1，0) 〃 また，(1，4，5) にしてわたしてもよい。 (0，4，5) で返されたときは (0，4，4) にしてわたす。 (1，3，5) 〃 (1，3，2) 〃 (1，2，5) 〃 (1，2，3) 〃 (1，1，5) 〃 (1，1，0) 〃 (1，0，5) 〃 (1，0，1) 〃 (1，4，4) 〃 (0，4，4) 〃 (1，4，3) 〃 (1，2，3) 〃 (1，4，2) 〃 (1，3，2) 〃 (1，4，1) 〃 (1，0，1) 〃 (1，4，0) 〃 (1，1，0) 〃 このように追いつめていくと，(2，4，6) や (3，5，6) の勝ち筋が導き出される。 (C)　4 つの山のときは，(1，1，2，2)，(1，2，5，6)，(2，3，4，5) などが勝ち筋である。 (1，1，2，2) にしてわたしたときを考える。 (0，1，2，2) で返されたときは (0，0，2，2) にしてわたす。 (1，0，2，2) 〃 (0，0，2，2) 〃 (1，1，1，2) 〃 (1，1，1，1) 〃 (1，1，0，2) 〃 (1，1，0，0) 〃 このことから，(X，X，Y，Y) の形が勝ち筋であることが分かる。 (2，3，4，5) にしてわたしたときを考える。 (1，3，4，5) で返されたときは (1，0，4，5) にしてわたす。 (0，3，4，5) 〃 (0，1，4，5) 〃 (2，2，4，5) 〃 (2，2，4，4) 〃 (2，1，4，5) 〃 (0，1，4，5) 〃 (2，0，4，5) 〃 (1，0，4，5) 〃 (2，3，3，5) 〃 (2，3，3，2) 〃 (2，3，2，5) 〃 (2，3，2，3) 〃 (2，3，1，5) 〃 (2，3，1，0) 〃 (2，3，0，5) 〃 (2，3，0，1) 〃 (2，3，4，4) 〃 (2，2，4，4) 〃 (2，3，4，3) 〃 (2，3，2，3) 〃 (2，3，4，2) 〃 (2，3，3，2) 〃 (2，3，4，1) 〃 (2，3，0，1) 〃 (2，3，4，0) 〃 (2，3，1，0) 〃 このように，相手が返す手を場合分けし追いつめていくと，大変な作業ではあるが，(1，6，11，12) も勝ち筋の一つであることが見出せる。 一般に，次の解法が知られている。 (A) 〜 (C) で見てきた勝ち筋を以下のように二進法で表し，それぞれのけたごとに合計すると，どのけたも偶数になっていることが分かる。 2 10 2 10 計 20 　 1 01 2 10 3 11 計 22 　 1 001 4 100 5 101 計 202 　 1 01 1 01 2 10 2 10 計 22 　 2 010 3 011 4 100 5 101 計 222 このように，どのけたの合計も偶数にして相手にわたすと，少なくとも一つのけたは奇数になって返される。そこで，再び適当な山をくずし，すべてのけたを偶数にしてわたせばよい。 この問題における勝ちパターンの例を以下に示す。 ⇒は相手にわたすことを，→は自分に返ってくることを意味する。 1 00001 11 01011 12 01100 23 10111 計 12223 ⇒ 1 0001 11 1011 12 1100 6 0110 計 2222 → 1 0001 11 1011 8 1000 6 0110 計 2122 ⇒ 1 0001 11 1011 8 1000 2 0010 計 2022 → 1 0001 5 0101 8 1000 2 0010 計 1112 ⇒ 1 001 5 101 6 110 2 010 計 222 → 1 001 5 101 4 100 2 010 計 212 ⇒ 1 001 5 101 4 100 0 000 計 202 →　… したがって，答えは「23 本の山から 17 本のマッチを取り去った」となる。