数学オリンピックの問題を解いてみた
はじめに
タイトルの通り、数学オリンピックの問題について書きたいと思います。今回扱う問題はSLPの整数分野の問題で、2016年の春合宿第11問でもあります。すごく面白い問題で、学びもあったので自分用にまとめてみたいと思います。
考察の章は解くときの思考回路を出来るだけ詳細に書き上げてみたつもりですが、蛇足になってしまった部分もあるので読みにくいと感じられた方は解答の章からお読みください。
正の整数$x,y$に対し、$gcd(x,y),lcm(x,y)$でそれぞれ$x$と$y$の最大公約数と最小公倍数を表し、$x~|~y$で$x$が$y$を割り切ることを表すこととします。
問題
$a_0,a_1, \cdots$と$b_0,b_1, \cdots$は正の整数からなる数列であって、$a_0,b_0 \geq 2$および、任意の非負整数nに対して
$$ a_{n+1}=gcd(a_n,b_n)+1,~~ b_{n+1}=lcm(a_n,b_n)-1 $$
を満たすものとする。このとき、ある非負整数$N$と正の整数$t$が存在して、$N$以上の任意の整数$n$に対して $a_{n+t}=a_n$が成り立つことを示せ。
どえ～～、見た目えぐ～～、gcdやlcmに1足したり引いたりってみたことない...それに数列が周期的になってることってどう示すの...けど何かしら綺麗な仕組みが隠されてるんだろうなあ、見た目は怖いけど面白そう！ってな感じで考え始めてみます。
考察
実験がしやすそうなのでやってみます。$(a_0,b_0)=(105,45)$とかにしてみると
$$ (a_n,b_n)=(105,45),(16,314),(3,2511),(4,2510),(3,5019),(4,5018),\cdots $$
こんな感じで確かに繰り返しになりそう。$a_n$は徐々に小さくなる感じで、${b_n}$の方は普通にどんどん大きくなっていくのかな。けどこの場合でも理由はよくわかんない...
$a_{n+1}=gcd(a_n,b_n)+1$って、よく考えてみると$gcd(a_n,b_n) \leq a_n$だから$a_{n+1} \leq a_n+1$なのか。しかも$a_{n+1} > a_n$となるのって$a_n ~|~b_n$のときだからまあまあレアなのね。だったら、
$$ a_1=a_0+1,a_2=a_1+1,a_3=a_2+1,a_4=a_3+1 $$
というようにずっと増加していく場合がどんな場合なのかを考えてみたい。この場合だと、$a_0=a,b_0=b$とかと置くと
$$a~|~b,~a+1~|~b-1,~a+2~|~b-2,~a+3~|~b-3$$
となる。$x~|~y \Longleftrightarrow x~|~x+y$なので、これって
** $$ a~|~a+b,~a+1|~a+b,~a+2~|~a+b,~a+3~|~a+b$$ **
と同値。つまり$a+b$が$a,a+1,a+2,a+3$で割り切れればいいのか。$b$の値で調節できるから、$a_n$をいくらでも連続して増加させることはできるのか...けどいつかは減少するわけか
一度$(a_0,b_0)=(2,58)$($a_0+b_0=60$が$2,3,4,5$で割り切れる)で実験してみると
$$a_n=2,3,4,5,6,7,2,3,4,5,2,3,4,5, \cdots$$
という感じでちゃんとループしそう...なんだこれ
$a_n$が無限に大きくなってしまってはループしなくなって困るし、とりあえず上から抑えられないかなあ。
とりあえず$a_{n+1}< a_n$となる$n$を取ってきて、
$$ (a_n,b_n)=(ag,bg) ~~ (g=gcd(a_n,b_n),a>2)$$
と置いてみると
$$(a_{n+1},b_{n+1})=(g+1,abg-1)$$
このまま$a_{n+m}$まで単調増加したとすると
$$ a_{n+2}=g+2,a_{n+3}=g+3, \cdots ,a_{n+m}=g+m$$
ここで** $g+1,\cdots ,g+m-1$はすべて$(g+1)+(abg-1)=g(ab+1)$を割り切る 。
ここで詰まってだいぶ右往左往して気付く。$ag$は$g(ab+1)$を割り切らないから、$g+1,\cdots g+m-1$の中に$ag$は存在しない！！つまり $g+m \leq ag$ **！！これかなり使えそう！！
数学的に書き直す。$a_{i+1} < a_i$となる$i$を小さい順に$i_1,i_2,\cdots$とする。これは無限数列となる。上の内容からすべての$n$について$a_{i_n} \geq a_{i_{n+1}}$。よって$a_{i_1},a_{i_2},a_{i_3},\cdots$は** 広義単調減少な正整数列となり、十分大きい所で一定！ **(要証明)
さらにこの一定となったところで元の数列は周期的になりそう。
いかがだったでしょうか。これでだいたい流れは掴めたのでちゃんとした解答に移ってみたいと思います。
解答
まず次の補題を用意する。
$a_n< a_{n+1}$ならば$a_{n+1}=a_n+1,a_n ~|~ b_n$
$gcd(a_n,b_n) \leq a_n(\cdots A)$であるから$a_{n+1}=gcd(a_n,b_n)+1\leq a_n+ 1$
$a_n< a_{n+1}$より$a_n+1 \leq a_{n+1}$なので、$a_{n+1}=a_n+1$が成立する。
またこのとき$A$の等号が成立するので$a_n ~|~ b_n$
Step1
$a_i \leq a_{i+1}$となるような非負整数$i$を小さい順に$i_1,i_2, \cdots$とする。このとき数列{$i_n$}は無限数列になることを示す。
有限数列だとすると、ある$N$が存在して
$$ a_N < a_{N+1} < a_{N+2} < \cdots $$
ここで補題１により、すべての$n \leq N$について
$$ a_{n+1}=a_n+1 , a_n ~|~ b_n $$
が成立する。さらにこのとき$lcm(a_n,b_n)=b_n$であるので、$b_{n+1}=b_n-1$が成立する。以上より、任意の非負整数$m$について、
$$ a_{N+m}=a_N+m~, ~b_{N+m}=b_N-m $$
が成立するが、$m=b_N-1$とすると$a_{N+m}$が$b_{N+m}$を割り切らず矛盾。
Step2
Step1で取った数列{${i_n}$}によって正整数からなる無限数列$a_{i_1},a_{i_2},\cdots$を定めると、これは広義単調減少になることを示す。
正整数$n$について$a_{i_n} \geq a_{i_{n+1}}$を示せばよい。以下$i_n=i,
i_{n+1}=i+m$とする。
$m=1$のときは$i_n$の定義から明らか。$m \geq 2$とする。
$i_n$の定義より、
$$a_i \geq a_{i+1}~,~a_{i+1} < a_{i+2} < \cdots < a_{i+m} $$
が成り立つ。$gcd(a_i,b_i)=g$と置き、$a_i=ag,b_i=bg$とすると
$$ a_{i+1}=g+1,b_{i+1}=abg-1 $$
であり、$a_i \leq a_{i+1}$より$a \geq 2$。さらに補題１により、$1 \leq j \leq m-1$について
$$ a_{i+j}= g+j~,~b_{i+j}=abg-j ~,~ a_{i+j}~|~b_{i+j} $$
が成立する。これより、$1 \leq j \leq m-1$について
$$ g+j ~|~a_{i+j}+b_{i+j}=g(ab+1) $$
を得る。
ここで、$a \geq 2$より$a$は$ab+1$を割り切らないので、$ag$は$g(ab+1)$を割り切らない。よって$ag$は$g+1,g+2, \cdots g+m-1$のどれとも等しくないので、$ag \geq g+m$。すなわち、** $a_i \geq a_{i+m} $ **が成立する。以上で示された。
Step3
Step2で取った無限数列{$a_{i_n}$}は十分先で一定となる。つまり正の整数$N$が存在して$n>N$ならば$a_{i_n}=a_{i_N}$が成立する。さらにこの$N$について数列$i_N,i_{N+1},i_{N+2},\cdots$は等差数列となり、その公差を$t$とすると$i_N $以上の任意の整数$n$について$a_{n+t}=a_n$が成立する。
まず一定になることを示す。
広義単調減少な正整数列なので数列が取りうる値は正整数からなる有限集合であり、最小値が存在する。最小値を取る項を一つ$a_{i_N}$とすると、$n \geq N$について$a_{i_N} \leq a_{i_n} \leq a_{i_N}$より$a_{i_n}=a_{i_N}$が成立する。
次に{$a_n$}が$i_N$以上のところで周期的になることを示す。
まず$gcd(a_{i_N},b_{i_N})=g,a_{i_N}=ag,b_{i_N}=bg $とおくと、$1 \leq j \leq i_{N+1}-i_N$について
$a_{i_N+j}=g+j ,b_{i_N+j}=abg-j $である。
$j=i_{N+1}-i_N$とすると$a_{i_{N+1}}=g+i_{N+1}-i_N $であるが、$a_{i_{N+1}}=a_{i_N}=ag$により$i_{N+1}-i_{N}=ag-g $。
さらに$b_{i_{N+1}}=abg-ag+g$なので$gcd(a_{i_{N+1}},b_{i_{N+1}})=g$。
以上を繰り返すことにより、数列$a_n$は$n \geq i_N$のところで
$$ ag,g+1, \cdots,ag-1 $$
を繰り返すことが分かる。
最後に
この問題のポイントは、** 広義単調減少な正整数の無限数列は十分先で一定 という事実だと思います。実際、上の証明では数列がループする本質的な理由は掴めていません。一定となるところを見てみたらたまたま繰り返しが起きていた、という感じです。
しかし、gcdやlcmが混ざったよくわからない数列の挙動を、数列の中の特別な部分に着目するすることで綺麗に解明することが出来るという点で非常に面白い問題だと思います。 問題の設定が厳しく全体的な構造が見えない場合に実験して構造をつかみ、問題で聞かれている事より強い命題を示して解きほぐすこと **は数学オリンピックで有効となることが多々あります。
最後に、今回のポイントとなった性質と似たものを使う問題を二問紹介したいと思います。
$a_1,a_2, \cdots$を正の整数列とする。ある$2$以上の整数$N$が存在し、任意の$n \geq N $に対し
$$ \frac{a_1}{a_2}+ \frac{a_2}{a_3}+ \cdots + \frac{a_{n-1}}{a_n}+ \frac{a_n}{a_1} $$
は整数である。このとき、正の整数$M$が存在し、任意の$ m \geq M $に対し$a_m=a_{m+1}$が成立することを示せ。(IMO 2018-5)
$k,l$を正の奇数とする。数列{$a_n$}を以下のように定める。
$a_1=k,a_2=l$.$a_{n+2}$は$a_{n+1}+a_{n}$の最も大きい奇数の約数と等しい。
このとき、ある正の整数$N$と$C$が存在して、$N$以上の任意の整数$n$に対して$a_n=C$が成り立つことを示せ。また、そのような$C$の値を$k,l$を用いて表せ。(2018年の第４回通信添削問題 5番より)
これにて今回の記事を締めたいと思います。つたない文章でしたが、お読みいただきありがとうございました。感想、指摘、ご意見などありましたら送っていただけるとすごく喜びます。