Evolton
方針
と が互いに素であることから、 の割り切れ条件で が一意に定まる。(2) は を仮定して次の が に入ることを帰納法で示す。(3) は を使って の交代を出す。
解答
(1)
のとき、 であり、 は のいずれかである。よってをみたす が一意に定まる。 からとなるので、以後これを繰り返す。したがってである。
(2)
は で割り切れないから、 と は互いに素である。したがって が で割り切れるような は一意に定まる。
と仮定する。このとき よりである。さらに であるから、 は整数でをみたす。 であるから、数学的帰納法によりすべての でである。
(3)
のとき である。 を で割った余りで見るとである。(2)より は のいずれかなので、 は に等しい。 からである。
したがって、 が奇数のときであり、 が偶数のときである。よってである。
別解
解法2
方針
各 に対し、合同式 の唯一の代表 を選ぶ「状態遷移」として数列を見る。(1)は4状態の表、(3)は2状態の直接計算で周期を確定する。
解答
(1)
のときである。 だから後の (2) と同じ評価から であり、各状態の遷移はとなる。 からこの表をたどれば(2)
なので である。したがって、各整数 に対してを満たす はただ1つ存在する。
いま とする。するとしかも だから初項 から帰納的にがすべての で成り立つ。
(3)
とする。 のときだから、一意性により一方、 のときだから初項が なので、この2状態が交互に現れる。よってなおなので、得られた は指定された範囲にも入っている。
総評
難度6、計算量6。想定時間は20分程度。割り切れ条件から の一意性を押さえ、 が常に から の範囲に入ることを帰納法で示すのが山場である。(3) では から が交代することに気づけば短くまとまる。別解では状態ごとの遷移を直接検算し、最後に得られた が必ず を満たすところまで確認した。