「数学オリンピックチャンピオンの美しい解き方」に出てくる、その他のさまざまな例の練習問題その3

「数学オリンピックチャンピオンの美しい解き方」に出てくる、その他のさまざまな例の練習問題その3

解答

$d=2$の時は、nを2進数で表して、m個取り去った時に2の累乗+1になる数にすると、相手は抵抗する。残りが1個になるように2の累乗個取り去ると負けるので、1個以外の2の累乗個を取り去る。0x02 $111\dots 001\dots 01$となる。
ここで2個を取り去ると
0x02 $110111\dots 111\dots 01$
となる。
このように、1の桁が0になるように$2^n$個を取り去るか、0の桁が減るように取り去るかである。
どうやっても2の累乗になってしまう取り去り方は、1,2,3,4を残す場合自明である。必ず負ける。
5の場合、1,2,3,4どれも負ける。
6,7なら5にできるので勝ち。
9も5にできるので勝ち。
10は2,6,8,9にしかできない。負け。
11なら10にして勝ち。
12なら10にして勝ち。
13は5にして勝ち。
14は10にして勝ち。
15は7にして勝ち。
17は15にして勝ち。
18は10にして勝ち。
19は15にして勝ち。
20は18にして勝ち。
21は20,19,17,13,5になる。5にして勝ち。
22は18にして勝ち。
23は負け。
24は、23にして勝ち。
取り去った時に相手が勝つ数にしかならないなら負ける。

では、負ける数にしかならないように取り去るにはどうすればいいか？
取り去り方は$2^n$が一番大きな桁の数にはn個ある。
$2^{n-1}$を取り去るとどうなるか？　桁が減る。
複数の桁が$2^n+1$や$2^n+2^m$の場合、必勝法はなさそうだ。いや、そうか。
1個の桁が$2^n+1$の場合、$2^n-1$個取り去って、相手がk個取り去ってきたらこちらもk個取り去る。そして相手が1個取り去ったらこちらも1個取り去り、$2^m-1$を作る。
この時に2進法で1になった桁が奇数個で、相手が0の桁を取り去り、また2進法で1になった桁が奇数個、ということが最後まで繰り返される、という条件を$n$が満たす場合だけ、先手が勝つ。満たさない場合後手が勝つ。
一般の場合は、大体は$d$進法で全ての桁の合計が奇数で、全ての取り去り方で、同じように全ての桁の合計が奇数という条件を満たす場合だけ、先手が勝つ。満たさない場合後手が勝つ。
厳密に考えよう。
$d$が奇数の場合、初めに$d$進法で桁の合計が奇数なら常に奇数を維持した場合のみ先手の勝ち、つまり常に先手の勝ち。偶数なら後手の勝ち。
桁の合計を奇数にするゲームなので、0の桁を攻めて偶数を奇数に変えても、相手が一度も奇数にできない時以外は1の桁を0にしても、相手は奇数を維持する為に0以外の桁を淡々と減らしてきて、負ける。（なお、0の桁を攻めても勝てる。）
$d$が偶数の場合はどうか。
$d=4$の場合、
101は31から30,23……
0の桁を攻めれば、1が3に変わる。
しかし、この1手パスは、3に変わる桁が偶数個の場合、初めの1回を含めて合計2p回可能である。ただし、そのすぐ下の桁のパスは奇数回可能だ。合計の可能なパスの回数は、$4^n$の桁を攻めた場合$n-2$回だ。そしてその内の奇数回可能なパスは$n$が偶数の場合、m個のパスできる桁があり、
その内の$\frac{m-1}{2}+1$個は
次に偶数回可能なパスを作る。
そして$\frac{m-1}{2}$個は奇数回パスが可能である。この奇数回可能なパスが常に奇数個ある為の条件は、何度$1$を引いて$2$で割っても、必ず奇数になることだ。
$2^n-1$はこの条件を満たす。
つまり、そのような数は$2^n$である。ルール上、この数は必ず勝つ。
3に変わる桁の数が奇数m個なら$\frac{m-1}{2}$個の有効なパスが可能である。その全てが奇数回の有効なパスを生まなければならない。
お互いにパスをし合うと奇数回パスする場合だけ先手が勝てるからだ。この場合、一番上の桁は$2^{2m}$。
3に変わる桁の数が偶数2m個なら
その後有効なパスができる桁の数はm個。mが偶数で、しかもそのパスで偶数個の有効なパスが常に生成されるなら先手は負け。つまり$2^m+1$桁なら負け。しかし、奇数個の有効なパスが生成される場合、生成したパスでパスが成立し、2の倍数個の有効なパスしか生成されない。つまり、しっかりとしたパスになる。
つまり、その後の全ての有効なパスで、有効なパスが奇数個しか生成されないなら、先手の勝ちとなる。
従って、$n\geqq 4$ の偶数の場合、初めに2の累乗である時と、$n$の$d$進法表記で桁の数が$2^m+1$の自然数で、無効なパスの桁が任意、$2^k+1(k< m)$の桁が任意で、しかも他の桁が先手に有利なように有効なパスを生成する場合だけ先手が勝つ。それ以外は先手が負ける。
Q. E. D.
■
奇数と偶数を間違えてたと思ったら、正しかった。
この問題は難しい。

訂正及びお断り

dが4以上の偶数の時、任意の0の桁を攻めることができ、条件が非常に複雑である。よってこの解説は誤りを含んでおり、一般には殆どの場合先手、後手共に必勝法はないと思われる。
ただし、dが奇数の時は明らかで、どの0以外の桁を攻めても桁の総和が奇数と偶数を行ったり来たりするし、0の桁を攻めても……あれ？
ああ、そうそう。1やそれ以外のdより小さい桁が1減り、有限個の偶数の桁ができるので、やはり奇数と偶数を行ったり来たりする。
従って、先手と後手は数の大きさ次第で初めからどちらが勝つか決まっており、必勝法も何も、途中でその運命を変えることはできない。
奇数の場合を完全に解明しただけでも十分だし、4以上の偶数の場合に一般には必勝法がないということが分かってよかった。