整数問題における指数関数の捉え方① (2009年 日本数学オリンピック本選 第一問)


 JMO(日本数学五輪)の本選は例年5問の記述式問題から構成され(予選は12問の短答式)、試験時間は4時間に及びます(予選は3時間)。各問題の難易度はオリンピックの名に恥じぬ高さを誇り、2完も出来れば国際五輪の代表選考に残れるとされています。

 本問も一見すると何の変哲もない整数問題のように見えますが、自力で仮説を立ててそれを証明する必要があるなど決して簡単ではありません。

解答

① 2nの多項式と捉えて割り算を実行する


 問題文を言い換えると上記解答で定義された分数数列f(n)が整数となる条件を考えれば良いのですが、このままでは取り扱いが難しい為に適切な式変形が必要です。そこで8n + nを2nに関する三次式と見做して2n + nを法とした割り算を実行する事で、新たな分数数列g(n)が整数となる条件と考えればよい事が分かります。

② 指数関数の爆発性を利用した必要条件の絞り込み

 
 g(n)の分母と分子を比較すると、分子はnに関する三次多項式である一方で分母は等比数列である2nを含みます。分母も分子もnに対する増加数列ですが、多項式数列と比べて等比数列(公比が1より大きい場合)は非常に速いスピードで増加することが知られています。

 従ってnがある程度大きくなればg(n)の分母は分子より大きくなり、その値は0と1の間に収まることが予想されます(即ちg(n)は整数と成り得ない)。境界線となるnの値は適宜代入計算を行うことにより自力で予想する必要が有り、結局 n が10以上の時分母が分子より大きくなることが推測されます(こういった仮説を自力で立てる必要が有る点が、数オリならではです)

 あとはこの仮説を自分で証明する必要がありますが、数学的帰納法を利用するのが良いでしょう。n = k + 1における証明については、対応する3次関数の増減表を利用する解法でも示すことが可能です。

③ 仕上げの代入計算

 ②で示した命題によりnが10以上の時、g(n)が整数と成り得ないことが分かります(ほぼ自明ですが、g(n) > 0についても一応証明すべきかもしれません)。よって残る候補は1から9までの自然数値という事になりますが、ここまで来ればあとは虱潰しに調べた方が楽でしょう。

 ここまで来ての計算ミスは余りに勿体ない為、多少時間をかけてでも丁寧に代入計算を行うべきです。

コメント

 一見すると唐突な式変形や補題の設定に見えますが、根底にあるのは底が1より大きな指数関数が、多項式に比べて非常に速いスピードで発散するという有名事実です。この考え方は本問に限らず、大学入試における整数問題を解く上でも有用である事が多く、頭に入れておくべきでしょう。

 本問は数オリ本選の問題としては恐らく簡単な部類と言えるでしょうが、それでも学ぶべき点は多く良問であると言えます。

投稿者: matsubushi

趣味で数学など

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。