数学オリンピック予選の第11問の解答をまとめてみる

きつねねねさんの漫画で取り上げられていた数学オリンピック予選の第11問の解答を自分なりにまとめてみる。

問題文

AさんとBさんが黒板を使ってゲームを行う。はじめ、黒板には2以上50以下の整数が1つずつ書かれており、2以上50以下の整数からなる空でない集合Sが定まっている。まず、最初のターンでAさんはSの要素をすべて黒板から消す。その後、2人はBさんから始めて交互に黒板から1つ以上の整数を選んで消すことを繰り返す。ただし、直前の相手のターンで消されたどの整数とも互いに素であるような整数は消すことができない。自分のターンが始まった時消せる整数が無ければゲームを終了し、その人の負け、もう一方の人の勝ちとする。
Bさんの行動に関わらず、Aさんが必ず勝つことができるようなSはいくつあるか。

とても面白いのでぜひ！！
漫画のリンク

解答

まず、Iを2以上50以下の整数の集合とする。SがIの空でない部分集合であるとき、Sが極大であるとは、Sの数の素因数の積で書けるすべてのIの数がSに含まれていることとする。これはSが、Sの数を分解して得られるすべての素数に対して、Iの数でその積であるものを集めたものになっているということ。

次のことを証明する。
１．先手が初手で極大な集合を取った場合、先手は必ず勝つことができる。
２．先手が初手で極大でない集合を取った場合、後手は必ず勝つことができる。

１の証明：まず、これまでに両者がとった数の全体をTとおく。Tは先手が初手で数を取った後、極大な集合である。次のことを示せば十分である：
「先手が数を取った後、Tが極大な集合ならば、後手がどのように数をとっても、先手はうまく数を取って再びTを極大にすることができる」
これを示すため、ある段階で先手が数を取った後Tが極大になっていると仮定する（最初かもしれないしそうでないかもしれない）。後手は、先手が取ったいずれかの数と互いに素でない数しか取れないので、それはTに含まれる何らかの素数で割り切れる。しかしTの素数でしか割り切れないならば、Tに含まれるはずであるから、Tの外から数を取る場合、それは必ずTに含まれない何らかの素数で割り切れる。その素数は、Iが連続しているので、必ずIに含まれる。また、Tのすべての数と互いに素であるため、後手がこれを取ることはできない。

後手が取った数の集合をUとする。先手は、Uに含まれる数を素因数分解して得られる素数に対し、それらとTの素数の積でできるIの数で、Tに含まれないものをすべて追加する。その中には先ほど述べた、Uのいずれかの数を割り切りTに含まれない素数が必ず含まれるので、先手は少なくとも1つ数を取ることができる。こうしてできる集合T'は、その中の数に含まれる素数のみからなる積をすべて含むので、極大になっている。こうして再びTを極大にすることができた。

以上より、帰納法で、先手は確実に勝てることが示された。

２の証明：先手が初手で極大でない集合を取ったとする。後手は、先手が取ってできた集合Tに対し、その数を素因数分解して得られるすべての素数について、その積であるようなAの数で、Tに入ってないものをすべて過不足なく追加する。追加できるのはTが極大でないからである。また、そのような数はすべてTの何らかの数の何らかの素因数を含んでいるので、確実に取ることができる。こうしてTが極大になるので、以降は先ほどの議論と同じようにして、後手は確実に勝つことができる。

Iの極大な集合は、それに含まれる素数のリストにより決定される。なので、Iに含まれる素数の集合について、その空でない部分集合と1対1に対応する。素数は全部で15個であるから、極大な集合の総数は(2^15)-1通りとなる。ゆえに、先手が勝てる数の選び方の総数は、(2^15)-1通り。

たとえば先手が{3,9,27,5,25,15,45}を取った場合、後手が{6,21}を取ったとすると、先手はTを極大にするために、2,3,5,7のみからなる積でこれまでに出てきてないものをすべて追加すればよい。それが3,5のみからなることはあり得ないし、そうでないなら確実に2か7で割り切れるので、6,21のいずれかと互いに素でないわけである。

これで合ってるんかな...