タイトルの通り、数学オリンピックの問題について書きたいと思います。今回扱う問題はSLPの整数分野の問題で、2016年の春合宿第11問でもあります。すごく面白い問題で、学びもあったので自分用にまとめてみたいと思います。
考察の章は解くときの思考回路を出来るだけ詳細に書き上げてみたつもりですが、蛇足になってしまった部分もあるので読みにくいと感じられた方は解答の章からお読みください。
正の整数
どえ~~、見た目えぐ~~、gcdやlcmに1足したり引いたりってみたことない...それに数列が周期的になってることってどう示すの...けど何かしら綺麗な仕組みが隠されてるんだろうなあ、見た目は怖いけど面白そう!ってな感じで考え始めてみます。
実験がしやすそうなのでやってみます。
こんな感じで確かに繰り返しになりそう。
というようにずっと増加していく場合がどんな場合なのかを考えてみたい。この場合だと、
となる。
**
と同値。つまり
一度
という感じでちゃんとループしそう...なんだこれ
とりあえず
と置いてみると
このまま
ここで**
ここで詰まってだいぶ右往左往して気付く。
数学的に書き直す。
さらにこの一定となったところで元の数列は周期的になりそう。
いかがだったでしょうか。これでだいたい流れは掴めたのでちゃんとした解答に移ってみたいと思います。
まず次の補題を用意する。
またこのとき
有限数列だとすると、ある
ここで補題1により、すべての
が成立する。さらにこのとき
が成立するが、
Step1で取った数列{
正整数
が成り立つ。
であり、
が成立する。これより、
を得る。
ここで、
Step2で取った無限数列{
まず一定になることを示す。
広義単調減少な正整数列なので数列が取りうる値は正整数からなる有限集合であり、最小値が存在する。最小値を取る項を一つ
次に{
まず
さらに
以上を繰り返すことにより、数列
を繰り返すことが分かる。
この問題のポイントは、** 広義単調減少な正整数の無限数列は十分先で一定 という事実だと思います。実際、上の証明では数列がループする本質的な理由は掴めていません。一定となるところを見てみたらたまたま繰り返しが起きていた、という感じです。
しかし、gcdやlcmが混ざったよくわからない数列の挙動を、数列の中の特別な部分に着目するすることで綺麗に解明することが出来るという点で非常に面白い問題だと思います。 問題の設定が厳しく全体的な構造が見えない場合に実験して構造をつかみ、問題で聞かれている事より強い命題を示して解きほぐすこと **は数学オリンピックで有効となることが多々あります。
最後に、今回のポイントとなった性質と似たものを使う問題を二問紹介したいと思います。
これにて今回の記事を締めたいと思います。つたない文章でしたが、お読みいただきありがとうございました。感想、指摘、ご意見などありましたら送っていただけるとすごく喜びます。