2017 JMO 問2 - だま氏の解いた問題たち

Peingでリクエストがあったので書きます.

問題

f:id:yootaamath:20191012164809p:plain
第27回(2017年)JMO本選の問題

感想

昔解いたことがあるので解きなおしたんですけど, やはり自分の苦手なタイプですね…
JMO1~2番の中ではやや難くらいな気がします.
実験してみるとなんとなく成り立ちそうだなってのがわかるんですけど, それをどう証明すればいいのか…という感じの問題です.

解説

解いていくときの気持ち

問題文を見ます. 数列を定めていく問題らしいです.
まずは実験です. 適当に\(a_1,\dots,a_N\)を定めて数列を計算していきます. \(2^n\)で割った余りを考えるので2進数で数字を書いていったほうが見やすそう.
やってみると, ある\(n\)が存在し, 任意の\(i(1\leq i\leq n-1)\)において\(a_i< 2^n\)となると終わりだなってことがわかります. そういう項って\(n\)が大きくなっても余りは変わらないし. そうじゃない数列の要素がどうなっていくのかが問題の肝だなって気持ちです. それをどう扱おう…そういう項の集合を\(B_n\)とおいてみます.
やってみるとどうしても\(B_n\)の要素を\(2^n\)で割った余りがどんどん大きくなっていきます. でもちょっとやりにくいので数列全体で\(2^n\)で割った余りの最小値を考えてみます.
これが広義単調増加なのはすぐわかった. というわけで発散しないとすると有界ですね. この考え方はありがちです.
有界だと何がまずいんだろう…ちょっと悩みます. 考えてみると, 新しく出てくる項って絶対余りがそれより大きくなるので, \(B_n\)に入ってくれるものがなくなってくるんだなあってなります. そういうことを定式化してみます.
なんやかんやで解けた気がする…？解答を書くとき\(C_n\)を定めてみると書きやすいなあってなったのでそうしました.

解答

\(a\%b\)で\(a\)を\(b\)で割った余りを表すものとする.
任意の整数\(A\)において\(A\%2^{n+1}-A\%2^n\)は0または\(2^n\)であるためこれは常に0以上, すなわち\(A\%2^{n+1}\geq A\%2^n\)であり, また\( (2A)\%2^{n+1}=2(A\%2^n)\)となることに注意する.

\(n\geq N+1\)に対し\(c_n\)を\(\min(a_1\%2^n,a_2\%2^n,\dots,a_{n-1}\%2^n)\)と定める. このとき仮定より\(c_{N+1}\neq 0\)であり, \(n\geq N+1\)のとき\(a_n\)の定め方より\[a_n\%2^{n+1}=2((a_n/2)\%2^n)=2c_n\quad \cdots (1)\]である.

すると, 任意の正の整数\(A,n\)において\(A\%2^{n+1}\geq A\%2^n\)であり, また(1)より\(a_n\%2^{n+1}\geq c_n\)であるため, \(c_{n+1}\geq c_n\), つまり数列\(\{c_n\}\)は広義単調増加となる. 特に, 任意の\(n\)において\(c_n>0\).

また任意の\(n\geq N+1\)に対し\(c_n\leq a_1\%2^n \leq a_1\)よりこの数列は有界. よってある整数\(M_1\)が存在し, 任意の\(n\geq M_1\)に対し\(c_n\)は定数である. この値を\(c\)とする. \(c\)は数列\(\{a_n\}\)のある項を\(2^{M_1}\)で割った余りとなるため\(2^{M_1}>c\). また\(c>0\)である.

\(n\geq N+1\)に対し, 集合\(B_n\)を\(B_n=\{a_i|1\leq i\leq n-1, a_i\geq 2^n\}\)と定める. ある\(n\)が存在し\(B_n=\emptyset\)となるとき, \(a_{n+1},a_{n+2},\dots\)はすべて\(2\min(a_1,\dots,a_n)\)となるため題意が成り立つ.

\(n\geq M_1\)に対し\(C_n=\{b|b\in B_n, b\%2^n=c\}\)と定める. このとき, 任意の\(M_1\)以上の整数\(n\)において, \(d\in C_{n+1}\)のとき, (1)より\(a_n\% 2^{n+1}=2c>c\)であるため\(d\neq a_n\). \(2^{M_1}>c\), \(d\%2^{n+1}=c\)より\(d\%2^n=c\)である. よって\(d\in C_n\). したがって\(C_{M_1}\supset C_{M_1+1}\supset \cdots\)となる.

するとある整数\(M_2\geq M_1\), 集合\(C_{\infty}\)が存在して\(n\geq M_2\)のとき\(C_n=C_{\infty}\)となる.
これが空集合でないと仮定し, 任意の\(A\in C_{\infty}\)をとるとき, \(2^k>A\)なる整数\(k\)をとると, \(A\notin B_k\). よって\(A\notin C_k\)となり\(A\in C_\infty\), \(C_\infty \subset C_k\)に矛盾. よって\(C_{\infty}=\emptyset\)である.

すると\(n\geq M_2\)のとき, \(\min(a_1\%2^n,a_2\%2^n,\dots,a_{n-1}\%2^n)=c\)であり, \(a_1,a_2,\dots,a_{n-1}\)の中で\(2^n\)で割った余りが\(c\)となるものはすべて\(2^n\)未満であるため, \(a_n\)の定め方より\(a_n<2^{n+1}\)となる. よって\(a_n\notin B_{n+1},B_{n+2},\dots\)である.

すると, \(\max(a_1,a_2,\dots,a_{M_2-1})< 2^k\)となる\(k\)をとるとき, \(B_k=\emptyset\)となる. よって示された.