[規則性]A〜Eの5つの箱に、碁石がそれぞれ1〜5個のせてあります。2人でこの箱からかわりばんこに碁石を取っていって、最後に碁石を全部取り尽くした方が勝ち、というゲームをします。・一度に同じ箱から複数の碁石をとっても良いが、別の箱から取ることはできないというルールがあります。先手側の立場にたっと時、最初にどのように取れば勝ちにつながるでしょうか?次の中から正しい方法を3つ選んでください。2手目以降もお互いが最善の手をつくすものとします。(E−5)(注)(C−2)とは、Cの箱から碁石を2個取ることを表すことにします。2.解答例1(清川育男さん、LIONさん、C-Dさん、okaokaさん、有無相生さん、他多数)まず、箱が2つの場合を考えてみましょう。・後手番では、必ず(N、N)型になる。碁石の数は次第に減っていくので、最後は後手番で(0、0)となり、先手勝ちとなる。先手は、(N、N)となるようにできれば、先手必勝型である。箱が3個の時、先手は(1、2、3)または(1、4、5)にできれば必勝型である。・後手(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)と、後手がどのような手をとっても、先手は(N、N)型にできるので、先手必勝。・後手(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、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)と、後手がどのような手をとっても、先手は(N、N)型または(1、2、3)の必勝型にできるので、先手必勝。・箱が5個のときに(N、N、1、2、3)または、(N、N、1、4、5)にできれば、先手必勝型の組み合わせなので、やはり先手必勝型。本問の場合、(A−1)→(2、3、4、5)(C−1)→(1、2、2、4、5)(E−1)→(1、2、3、4、4)の3つのケースが先手必勝になります。このうち、(C−1)→(1、2、2、4、5)は、(2、2)と(1、4、5)の組み合わせ、(E−1)→(1、2、3、4、4)は、(4、4)と(1、2、3)の組み合わせ、になるので、先手必勝。・後手(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)となり、後手がどのような手を取っても、先手は必勝型に持ち込める。・先手(B−1)→(1、1、3、4、5)の場合は、後手(1、1、1、4、5)・先手(B−2)→(1、0、3、4、5)の場合は、後手(1、0、0、4、5)・先手(C−2)→(1、2、1、4、5)の場合は、後手(1、1、1、4、5)・先手(C−3)→(1、2、0、4、5)の場合は、後手(1、0、0、4、5)・先手(D−1)→(1、2、3、3、5)の場合は、後手(1、2、3、3、3)・先手(D−2)→(1、2、3、2、5)の場合は、後手(1、2、3、2、2)・先手(D−3)→(1、2、3、1、5)の場合は、後手(1、2、3、1、1)・先手(D−4)→(1、2、3、0、5)の場合は、後手(1、2、3、0、0)・先手(E−2)→(1、2、3、4、3)の場合は、後手(1、2、3、3、3)・先手(E−3)→(1、2、3、4、2)の場合は、後手(1、2、3、2、2)・先手(E−4)→(1、2、3、4、1)の場合は、後手(1、2、3、1、1)・先手(E−5)→(1、2、3、4、0)の場合は、後手(1、2、3、0、0)とすれば、後手が必勝型に持ち込むことができますので、解は上記3ケースしかありません。答:(A−1)、(C−1)、(E−1)以上3.解答例2(中村明海さん、高橋道広さん、他)この問題は、有名な3山くずしと呼ばれるゲームで、2進数表示で考えると簡単に先手必勝型が分かります。(1)4=100+)5=1011=0011になります。先手は、ここから、ニム和が0になるような手を作ることが出来れば、必勝型になります。ちなみに、解答例1で出てきた必勝型(N、N)、(1、2、3)、(1、4、5)は、いずれもニム和は0です。(1)の計算でニム和が0になるようにするには、1の位が1のものを0にすればいいので、1から5では奇数の1、3、5のいずれかになります。(A−1)、(C−1)、(E−1)の3ケースが先手必勝型です。(E−1)1=0012=0103=0114=100+)4=1000=000なお、(A−1)〜(E−5)についてニム和を計算すると下記のようになります。(E−5)1=0012=0103=0114=100+)0=0004=100従って、(A−1)、(C−1)、(E−1)以外ではニム和が0にならないことがわかります。箱A、B、C、D、Eにある碁石の個数をa、b、c、d、eとします。先手番で、s=a+b+c+d+e(ニム和:以下同様)が0でないとします。本問では、s=1です。ニム和は、2進数表示で各桁の1の個数が奇数のとき1、偶数の時0でもあるので、ニム和が0でないということは、sの各桁のうち1のものが必ずあります。(本文では最下位)このうち、一番位が高い桁(下から数えて第n位とします)について考えると、ニム和が1なので、同じ桁に1となるものが、a、b、c、d、eの中に少なくとも1つはあります。(全て0ならニム和も0)例えば、aがそうだとします。(本文では、a=1、c=3、e=5)a’=a+sとすると、s’=a’+b+c+d+e=(a+s)+b+c+d+e=(a+b+c+d+e)+s=s+s=0になります。・第n位は、aもsも1なので、a’=a+sでは0従って、a’=a+s<aとなります。(本問では、1+s=0、3+s=2、5+s=4)すなわち、a→a’個に減らせば、s’=0となり、ニム和を0にすることができます。今度は、後手番でニム和が0とします。後手が、a、b、c、d、eのいずれかの碁石を減らしたとき(例えばb→b’個)、b’の各桁のうち、1個はbと値が異なるものがあります。すると、その桁ではb→b’に伴って0→1か1→0になっています。a、b’、c、d、eについていえば、前者では1の個数は+1、後者では−1になるのでいずれのときも、偶数→奇数に変わります。従って、s’=a+b’+c+d+eは0ではありません。よって、その次の先手番では再びニム和を0になるよう碁石を減らすことができます。以上を繰り返していけば、碁石の数は次第に減っていき、後手番で全て0の場合に必ずなってしまうので、必ず先手勝ちとすることができます。