ひたすら受験問題を解説していくブログ
東京大学2011年前期数学第2問
todai_2011_math_q2.png

解説


数論分野で出てくる連分数展開と呼ばれる非常に精度の高い近似法を背景とした問題です。(3)で”有理数⇒あるnで0”というのを証明しますが,その逆,”あるnで0⇒有理数”であることも真だったりします。本問で出てくる数列は連分数展開の分数に随時展開されていく部分の数列です。その辺は参考で軽く触れます。
問題自体はスタンダードな良問であり,ぜひ解けるようになって欲しい問題です。

(1)
よくわからないですが,こういうのはとりあえず入れてみる精神が重要です。1<√2<2なので,
todai_2011_math_a2_1.png
todai_2011_math_a2_2.png
となります。a2=a1であり,a3以降も直前の1項のみに依存して作られ方は同じなので,すべて√2-1になります(解答では帰納法でしっかり書かないとダメなんですかね?)。

(2)
a1=<a>=aより,0≦a<1です。与えられている条件も入れると,1/3≦a<1です。また,a≠0より,a2=aになるように考えてみると,
todai_2011_math_a2_3.png
<>の記号が気持ち悪いので,1/aの整数部分をmとすると,
todai_2011_math_a2_4.png
となります。また,1/3≦a<1⇔1<1/a≦3⇒1≦m≦3であり,m=1,2,3を代入すると,
todai_2011_math_a2_5.png
ですが,1/3≦a<1のフィルターにかけると以下の2つのみ残ります(そもそもm=3はa=1/3のみなので,a2の段階で0になるので除けます)
todai_2011_math_a2_6.png
nまでこれらのaになるならば,n+1の場合もこれらのaになるので,すべてのnについてaになります。

(3)
a1の段階が一緒になるので,0≦p≦q-1とpをqで割った余りで考えても違いはありません。

p=0の場合,直ちにa1=0であり,以降のすべてのnで0となります。

p≠0の場合,a2はqをpで割ったあまりをq2と置くことによって,次のように表せます。
todai_2011_math_a2_7.png
同様にq0=q,q1=pであったと考えてみれば,一般的にqn+1をqn-1をqnで割った余りと定義してやれば,n以下のkでのqkすべてが0ではない限り,
todai_2011_math_a2_8.png
となります。
さて,ここで,qqまでのすべてのqnにおいて,qk≠0が成立していると仮定すると,この数列qnは定義上0ではないあまりなので,自然数かつq=q0>q1>q2・・・>qq≧1です。しかし,ひとつ次の項に移るたびに最低でも1は減っていくので,qq≦q-q=0であり,矛盾してしまいます。
よって,qqまでのqnにおいて,qk=0なるものが存在することになり,そのn=k以降はすべてan=0になるため,k≦qより,n≧qなるnでan=0になります。

【別解答】数学的帰納法により解法
a1の段階が一緒になるので,0≦p≦q-1とpをqで割った余りで考えても違いはありません。qに関して帰納法でいくことを考えます(自分にはnで考えてもいまいちピンと来ず,pはそもそも一番関係が薄そうなので考えていません)。

(i)q=1の時
pは整数なので,aも整数であり,a1も整数の小数部分,つまり0になります。よって,n=q=1以降のanも0になり,成立しています。

(ii)
q≦kで成立していると仮定します。q=k+1の場合,p=0なら言うまでもなくan=0なので,p≠0とすれば,1≦p≦q-1=kです。このとき,
todai_2011_math_a2_9.png
であり,q=pの場合と同一となり,1≦p≦kより,n≧k+1≧p+1でan=0になります(一個ずれているので+1です)。
よって,仮定の下でq=k+1でも成立します。

(i)(ii)より,すべての自然数qにおいて成立します。

【参考】連分数展開
連分数展開は最良近似分数(分母がその分母以下の分数で最も近似精度のいい分数。有名どころだとπ=22/7あたりでしょうか)を考えた結果出てくるものです(逆だったらすみません)。

最良性の証明も含め厳密なものは数論の本などに任せるとして,ここでは近似アルゴリズムを簡単に述べて,本問がどう絡んでくるのかを説明したいと思います。
近似したい数をαとしたとき,αを傾きとして原点を通る直線Lとします,Lの上下にU-2,U-1をとった場合(U-2=(1,0),U-1=(0,1)とします),
todai_2011_math_a2_10.png
という形でU0がL上もしくはU-2と同じ側になるような最大の整数aが定められます。これをa0のように定義します。また,以下の図から考察できるように,直線Lへの距離(dとします)でその近さを考えてやれば,U0はU-1より近くなります(図ではa0=2で,d0=d-2-2d-1<d-1です)。
todai_2011_math_a2_21.png
同様に,UnがL上もしくはUn-2と同じ側になるような(L上になったらその時点で終わりです)最大の整数anをとって(一応n≧1でan≧1です。n=0の場合のみd-2<d-1の可能性があるので,0になり得ます)
todai_2011_math_a2_11.png
というように定義すれば,段々と
todai_2011_math_a2_12.png
と近づいていきます。これの何がαの近似なのかといえば,各Uへの傾きがLに近づいていくことにもなり,Unの座標を(qn,pn)とでもして,証明は他任せにしておきますが(qn+1≧an+1qnであること,および,UnとUn+1を並べて作った行列の行列式が±1になることから証明できます),
todai_2011_math_a2_13.png
という精度で近似できていることになります。

さて,ここからが本問との関連ですが,さっきのdの漸化式を変形していくと,
todai_2011_math_a2_14.png
となり,bn=dn-1/dn-2とおいてやれば
todai_2011_math_a2_15.png
のようになり,この数列bnが本問でいう数列anということになります。

次に,これがどう連分数による近似になっていくかですが,b0を求めてみると,下図より,
todai_2011_math_a2_22.png
todai_2011_math_a2_16.png
であり,順次代入していけば,連分数を得られます。
todai_2011_math_a2_17.png
例えば(2)の√2-1の場合を代入していけば,a0=0,n≧1でan=2であり,
todai_2011_math_a2_18.png
(√5-1)/2は,
todai_2011_math_a2_19.png
となります。ちなみに,有理数での近似の話に戻ると,
todai_2011_math_a2_20.png
だったりします。

東京大学2011年前期数学に戻る
スポンサーサイト

テーマ:大学受験 - ジャンル:学校・教育

コメント
コメント
コメントの投稿
URL:
本文:
パスワード:
非公開コメント: 管理者にだけ表示を許可する
 
トラックバック
トラックバック URL
http://jukenkaisetsu.blog.fc2.com/tb.php/383-8c5b487f
この記事にトラックバックする(FC2ブログユーザー)
トラックバック