きままにものづくり

日々の気付いたことなんかを書いてます。

SRM575

結果:0pt
歯が立たなかった。

TheNumberGameDivOne

漸化式を見つける問題だった。
こういう問題は、自分で例題を作り法則を見つけだすべきだった。

解説では、省略されている証明を簡単にする。
Brusが勝利する条件は、

  • nが奇数
  • nが2の奇数乗(2^{2k+1})

である。

nが奇数の場合の証明をする。
まず、証明の見通しを説明し、下の2つの補題を証明する。

  • 補題1:nが奇数(素数は除く)の時、次の値は必ず2^tではない形の偶数になる。
  • 補題2:nが2^tではない形の偶数の時、次の値は奇数にすることができる。

この勝負が終わるのは、nが素数になる時である。そして、2と0以外の偶数は必ず素数ではない。上の補題より、偶数の次は必ず奇数にできる。奇数の次は必ず偶数になる。偶数で勝負が終わることはないので、負けるのは必ず奇数になる。よって、nが奇数の時はBrusが勝利する。

補題1

nが奇数(素数は除く)の時、次の値は必ず2^tではない形の偶数になることを証明する。
nが奇数であり合成数ならば、素因数は全て奇数になる。偶数と奇数の掛け算は常に偶数になるからである。素因数が全て奇数なので、それの組み合わせの掛け算で表される約数も奇数となる。奇数と奇数の引き算は偶数になるので、次の値は偶数になる。
2^tでない形になることを背理法を用いて証明する。
2^t = k-c
と仮定する。ここで、tは任意の整数。kは奇数の合成数。cはkの約数とする。cはkの約数なので
2^t = c*(k-1)
となる。ここで、kは奇数なので(k-1)は偶数となる。2^tの素因数は全て偶数である。しかし、右辺には奇数であるcが含まれている。よって、この等式は成り立たない。

補題2

nが2^tではない形の偶数の時、次の値は奇数にすることができることを証明する。偶数が2^tの形をしていないなら、奇数の素因数を必ず含む。偶数である素数は2以外存在しない。なので、2以外の素因数は全て奇数になる。よって偶数が2^tの形をしていないなら、奇数の素因数を必ず含む。

nが2の奇数乗(2^{2k+1})の場合の証明をする。
nが2^{t}の場合は、次の値は2^{t-1}か偶数になる。次の値を偶数にしてしまうと、必ずまけてしまうので2^{t-1}にするしかない。nが2になる時に勝敗が決まるので、最初のnが奇数の時は必ずBrusが勝利する。