シンプルな問題ほど手ごわい……？ 素数と不等式のダブルアタック！ ～2024年大...
皆さんこんにちは。東進衛星予備校 金沢南校の北川と申します。
夏風邪を引いたことにより完全に様々なことへのモチベーションが消えかけていますが、日課のプログラミング過去問演習だけは何とか続けております。生徒の皆さんが雨にも風にも夏の暑さにも負けず頑張ってくれているので、私だけがへこたれるわけにもいかんわけです。
最近はブログ記事のためもあるのですが、旧帝大の過去問を遡って見ることが増えました。その中で、阪大の問題は順当に難しく、かつ難しすぎないという点において題材にしやすいなあと感じてきました。
今日はそんな中でも、問題の意味を理解するだけなら簡単で、丁寧な論証をしようと思うと難しい問題を1つ見つけてきましたので、これの解説をします。
目次
1.2024年阪大文系第3問
今回扱う問題はこちら！
素数を小さい順に並べて得られる数列を
$$ p_1, p_2, …, p_n, … $$
とする.
(1)\(p_{15}\)の値を求めよ.
(2)\(n \geq 12\)のとき,不等式\( p_{n} > 3n \)が成り立つことを示せ.
問題の意味自体は非常に簡単ですね。一応言っておくと、(1)は「小さいほうから15番目の素数は何？」という意味です。15番目ですから数えればすぐにわかります。
???「落ち着くんだ……『素数』を数えて落ち着くんだ……」
$$ 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,… $$
ということで、(1)の答えは「47」ですね。天下の阪大がこれで何点かくれるっていうのが信じられないですね。
さて、この問題の本丸は(2)です。 \(n\)が12以上の時、小さいほうから\(n\)番目の素数が3\(n\)より大きいことを示すことになります。
いくつか実験してみましょう。小さいほうから12番目の素数\(p_{12}\)は37です。一方で\(3 \times 12 = 36\)ですから、\(p_{12} > 3 \times 12\)は確かに成り立っているようです。
他にも、例えば\(p_{13} = 41\)で\(3 \times 13 = 39\)ですから、\(p_{13} > 3 \times 13\)も成り立っています。\(p_{14}\)や\(p_{15}\)も同じことになっています。これがこの先もずっと同じような関係が成立するよ、ということを証明すればよいわけです。
じゃあやっていきましょう。
2.「何となくそれはそう」を言語化する
さて、(2)の問題の意味を理解したところで改めて考えてみると、ある程度数学的な訓練を受けた人であれば「なんかそんな気するわ」となるはずです。
まず、素数は探索範囲が広くなればなるほどまばらに分布しているはずです。つまり、充分大きな素数は1つ前の素数と比べてかなり遠くにあることが増えるはずなのです。
だから、\(p_{n}\)の値は\(n\)が大きくなるにつれて爆裂に大きくなりうるのですが、\(3n\)の値はどんなに\(n\)が大きくても3ずつしか増えないわけで、普通に考えれば\(3n\)の方が圧倒的に小さくなるはずなのです。すると、直観的には一度\( p_{n} > 3n \)となれば、そうそうそれがひっくり返るような感じはしないなあと思えないでしょうか。
「素数がまばらに分布している」というのをもう少し言い換えてみましょう。
今回であれば、例えば素数が出てくる頻度を定量的に測る指標を探すことにします。
例えば事実として「正の整数\(p\)が2,3以外の素数であるならば、ある非負整数\(k\)が存在して\(p = 6k + 1\)または\(p = 6k + 5\)と表せる」ということが広く知られています（対偶を取って考えてみればこれは明らかです）。
これを使って考えてみましょう。素数\(p\)について\(p = 6k + 1\)と書けたとすると、その次の素数は最も近くても、\(6k + 5\)以上になります。その次の素数となると、一番近くても\(6(k+1)+1\)以上になります。
これは\(p = 6k + 5\)と書けるときでも同じようなことが起きます。
となると、ある素数の「次の次の素数」は、6以上離れていることが分かります。
この事実を使うと、この問題を以下のように解くことができます。
[解答]
\(n \geq 12\)のとき,不等式\(p_n > 3n \)が成り立つことを、\(n\)について場合分けして示す。
・\(n\)が6以上の正の整数\(m\)を用いて、\(n=2m\)と書けるとき、\(m\)についての数学的帰納法を使って\(p_{2m} > 3(2m) \)を示す。
まず\(m = 6\)のとき、\(p_{12} = 37 > 36 = 3 \times 12 \)より主張は正しい。
ある6以上の整数\(k\)について、\(p_{2k} > 3(2k) \)であると仮定する。
このとき、\(p_{2(k+1)} = p_{2k+2} \geq p_{2k} + 6 \)であることが、解答の前の考察より明らかであるから、仮定より
$$ p_{2k} + 6 > 3(2k) + 6 = 3(2(k+1))$$
が分かる。したがってこの場合は正しいことが示された。
・\(n\)が6以上の正の整数\(m\)を用いて、\(n = 2m + 1\)と書けるときについても、ほとんど同様にして\(m\)についての数学的帰納法が適用できる[1]。
以上より、題意は示された。
有名事実を使うことで、こうも容易く証明ができてしまうのは面白いですね！
また、東進などのサイトの模範解答では不等号を使った非常に頭の良い方法で解いています。そちらの方も参照して、より解き方の幅を広げるのが良いでしょう。
3.おわりに
今回の記事は短いですがここまで。
簡単な問題ですが、簡単がゆえにしっかりした論理で解答を書かないといけないのが大変な問題でした。
こういう問題を落とさないように、新指導要領になっても気を抜かずいきましょう。
[1] 本番の解答では省略しない方が良いと思います。
