SRM575
結果:0pt
歯が立たなかった。
TheNumberGameDivOne
漸化式を見つける問題だった。
こういう問題は、自分で例題を作り法則を見つけだすべきだった。
解説では、省略されている証明を簡単にする。
Brusが勝利する条件は、
- nが奇数
- nが2の奇数乗()
である。
nが奇数の場合の証明をする。
まず、証明の見通しを説明し、下の2つの補題を証明する。
- 補題1:nが奇数(素数は除く)の時、次の値は必ずではない形の偶数になる。
- 補題2:nがではない形の偶数の時、次の値は奇数にすることができる。
この勝負が終わるのは、nが素数になる時である。そして、2と0以外の偶数は必ず素数ではない。上の補題より、偶数の次は必ず奇数にできる。奇数の次は必ず偶数になる。偶数で勝負が終わることはないので、負けるのは必ず奇数になる。よって、nが奇数の時はBrusが勝利する。
補題1
nが奇数(素数は除く)の時、次の値は必ずではない形の偶数になることを証明する。
nが奇数であり合成数ならば、素因数は全て奇数になる。偶数と奇数の掛け算は常に偶数になるからである。素因数が全て奇数なので、それの組み合わせの掛け算で表される約数も奇数となる。奇数と奇数の引き算は偶数になるので、次の値は偶数になる。
でない形になることを背理法を用いて証明する。
と仮定する。ここで、tは任意の整数。kは奇数の合成数。cはkの約数とする。cはkの約数なので
となる。ここで、kは奇数なので(k-1)は偶数となる。の素因数は全て偶数である。しかし、右辺には奇数であるcが含まれている。よって、この等式は成り立たない。
補題2
nがではない形の偶数の時、次の値は奇数にすることができることを証明する。偶数がの形をしていないなら、奇数の素因数を必ず含む。偶数である素数は2以外存在しない。なので、2以外の素因数は全て奇数になる。よって偶数がの形をしていないなら、奇数の素因数を必ず含む。
nが2の奇数乗()の場合の証明をする。
nがの場合は、次の値はか偶数になる。次の値を偶数にしてしまうと、必ずまけてしまうのでにするしかない。nが2になる時に勝敗が決まるので、最初のnが奇数の時は必ずBrusが勝利する。