10

数学オリンピックの問題を解いてみた

764
0

はじめに

タイトルの通り、数学オリンピックの問題について書きたいと思います。今回扱う問題はSLPの整数分野の問題で、2016年の春合宿第11問でもあります。すごく面白い問題で、学びもあったので自分用にまとめてみたいと思います。

考察の章は解くときの思考回路を出来るだけ詳細に書き上げてみたつもりですが、蛇足になってしまった部分もあるので読みにくいと感じられた方は解答の章からお読みください。

正の整数x,yに対し、gcd(x,y),lcm(x,y)でそれぞれxyの最大公約数と最小公倍数を表し、x | yxyを割り切ることを表すこととします。

問題


a0,a1,b0,b1,は正の整数からなる数列であって、a0,b02および、任意の非負整数nに対して
an+1=gcd(an,bn)+1,  bn+1=lcm(an,bn)1
を満たすものとする。このとき、ある非負整数Nと正の整数tが存在して、N以上の任意の整数nに対して an+t=anが成り立つことを示せ。

どえ~~、見た目えぐ~~、gcdやlcmに1足したり引いたりってみたことない...それに数列が周期的になってることってどう示すの...けど何かしら綺麗な仕組みが隠されてるんだろうなあ、見た目は怖いけど面白そう!ってな感じで考え始めてみます。

考察

実験がしやすそうなのでやってみます。(a0,b0)=(105,45)とかにしてみると
(an,bn)=(105,45),(16,314),(3,2511),(4,2510),(3,5019),(4,5018),
こんな感じで確かに繰り返しになりそう。anは徐々に小さくなる感じで、bnの方は普通にどんどん大きくなっていくのかな。けどこの場合でも理由はよくわかんない...
an+1=gcd(an,bn)+1って、よく考えてみるとgcd(an,bn)anだからan+1an+1なのか。しかもan+1>anとなるのってan | bnのときだからまあまあレアなのね。だったら、
a1=a0+1,a2=a1+1,a3=a2+1,a4=a3+1
というようにずっと増加していく場合がどんな場合なのかを考えてみたい。この場合だと、a0=a,b0=bとかと置くと
a | b, a+1 | b1, a+2 | b2, a+3 | b3
となる。x | yx | x+yなので、これって
** a | a+b, a+1| a+b, a+2 | a+b, a+3 | a+b **
と同値。つまりa+ba,a+1,a+2,a+3で割り切れればいいのか。bの値で調節できるから、anをいくらでも連続して増加させることはできるのか...けどいつかは減少するわけか
一度(a0,b0)=(2,58)(a0+b0=602,3,4,5で割り切れる)で実験してみると
an=2,3,4,5,6,7,2,3,4,5,2,3,4,5,
という感じでちゃんとループしそう...なんだこれ

anが無限に大きくなってしまってはループしなくなって困るし、とりあえず上から抑えられないかなあ。
とりあえずan+1<anとなるnを取ってきて、
(an,bn)=(ag,bg)  (g=gcd(an,bn),a>2)
と置いてみると
(an+1,bn+1)=(g+1,abg1)
このままan+mまで単調増加したとすると
an+2=g+2,an+3=g+3,,an+m=g+m
ここで** g+1,,g+m1はすべて(g+1)+(abg1)=g(ab+1)を割り切る
ここで詰まってだいぶ右往左往して気付く。agg(ab+1)を割り切らないから、g+1,g+m1の中にagは存在しない!!つまり
g+mag **!!これかなり使えそう!!

数学的に書き直す。ai+1<aiとなるiを小さい順にi1,i2,とする。これは無限数列となる。上の内容からすべてのnについてainain+1。よってai1,ai2,ai3,は** 広義単調減少な正整数列となり、十分大きい所で一定! **(要証明)
さらにこの一定となったところで元の数列は周期的になりそう。

いかがだったでしょうか。これでだいたい流れは掴めたのでちゃんとした解答に移ってみたいと思います。

解答

まず次の補題を用意する。

 an<an+1ならばan+1=an+1,an | bn

gcd(an,bn)an(A)であるからan+1=gcd(an,bn)+1an+1
an<an+1よりan+1an+1なので、an+1=an+1が成立する。
またこのときAの等号が成立するのでan | bn

Step1

aiai+1となるような非負整数iを小さい順にi1,i2,とする。このとき数列{in}は無限数列になることを示す。

有限数列だとすると、あるNが存在して
aN<aN+1<aN+2<
ここで補題1により、すべてのnNについて
an+1=an+1,an | bn
が成立する。さらにこのときlcm(an,bn)=bnであるので、bn+1=bn1が成立する。以上より、任意の非負整数mについて、
aN+m=aN+m , bN+m=bNm
が成立するが、m=bN1とするとaN+mbN+mを割り切らず矛盾。

Step2

Step1で取った数列{in}によって正整数からなる無限数列ai1,ai2,を定めると、これは広義単調減少になることを示す。

正整数nについてainain+1を示せばよい。以下in=i,in+1=i+mとする。
m=1のときはinの定義から明らか。m2とする。
inの定義より、
aiai+1 , ai+1<ai+2<<ai+m
が成り立つ。gcd(ai,bi)=gと置き、ai=ag,bi=bgとすると
ai+1=g+1,bi+1=abg1
であり、aiai+1よりa2。さらに補題1により、1jm1について
ai+j=g+j , bi+j=abgj , ai+j | bi+j
が成立する。これより、1jm1について 
g+j | ai+j+bi+j=g(ab+1)
を得る。
ここで、a2よりaab+1を割り切らないので、agg(ab+1)を割り切らない。よってagg+1,g+2,g+m1のどれとも等しくないので、agg+m。すなわち、** aiai+m **が成立する。以上で示された。

Step3

Step2で取った無限数列{ain}は十分先で一定となる。つまり正の整数Nが存在してn>Nならばain=aiNが成立する。さらにこのNについて数列iN,iN+1,iN+2,は等差数列となり、その公差をtとするとiN以上の任意の整数nについてan+t=anが成立する。

まず一定になることを示す。
広義単調減少な正整数列なので数列が取りうる値は正整数からなる有限集合であり、最小値が存在する。最小値を取る項を一つaiNとすると、nNについてaiNainaiNよりain=aiNが成立する。
次に{an}がiN以上のところで周期的になることを示す。
まずgcd(aiN,biN)=g,aiN=ag,biN=bgとおくと、1jiN+1iNについて
aiN+j=g+j,biN+j=abgjである。
j=iN+1iNとするとaiN+1=g+iN+1iNであるが、aiN+1=aiN=agによりiN+1iN=agg
さらにbiN+1=abgag+gなのでgcd(aiN+1,biN+1)=g
以上を繰り返すことにより、数列anniNのところで
ag,g+1,,ag1
を繰り返すことが分かる。

最後に

この問題のポイントは、** 広義単調減少な正整数の無限数列は十分先で一定 という事実だと思います。実際、上の証明では数列がループする本質的な理由は掴めていません。一定となるところを見てみたらたまたま繰り返しが起きていた、という感じです。
しかし、gcdやlcmが混ざったよくわからない数列の挙動を、数列の中の特別な部分に着目するすることで綺麗に解明することが出来るという点で非常に面白い問題だと思います。
問題の設定が厳しく全体的な構造が見えない場合に実験して構造をつかみ、問題で聞かれている事より強い命題を示して解きほぐすこと **は数学オリンピックで有効となることが多々あります。

最後に、今回のポイントとなった性質と似たものを使う問題を二問紹介したいと思います。


a1,a2,を正の整数列とする。ある2以上の整数Nが存在し、任意のnNに対し
a1a2+a2a3++an1an+ana1 
は整数である。このとき、正の整数Mが存在し、任意のmMに対しam=am+1が成立することを示せ。(IMO 2018-5)

k,lを正の奇数とする。数列{an}を以下のように定める。
a1=k,a2=l.an+2an+1+anの最も大きい奇数の約数と等しい。
このとき、ある正の整数NCが存在して、N以上の任意の整数nに対してan=Cが成り立つことを示せ。また、そのようなCの値をk,lを用いて表せ。(2018年の第4回通信添削問題 5番より)

これにて今回の記事を締めたいと思います。つたない文章でしたが、お読みいただきありがとうございました。感想、指摘、ご意見などありましたら送っていただけるとすごく喜びます。

投稿日:20201112
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

Iso
Iso
21
1897
主に数学オリンピックの勉強をしています。数学オリンピックでは整数分野が好きです。よろしくお願いします

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中