入試問題ではないけど良問な、海外数学コンテストの問題

皆さんこんにちは。東大セミナーの北川です。

国公立大学の入学試験も終わり、いよいよ待ち望んだ春の到来が近づく今日この頃。受験生の皆さんは、この1年（どころか3年間！）、本当によく努力してくれたことと思います。その努力に敬意を表し、新たな門出を祝福致します。

そして、学習塾・予備校としては、この時期は巡りくる”スタートの時期”でもあります。この時期に難関大学の入試を取り上げあれやこれやと評するのも、次にスタートする誰かのためになればと思ってのことです。

今月拾ってきた問題も、そんな誰かが受験勉強のスタートを切ろうと思った時に道しるべとなるような、受験数学のエッセンスが詰め込まれた良い問題です。

新高3になる方は、是非腕試しと思って解いてみてください！

目次

1.今月の問題

2.解法の糸口～mod3～

3.最後の考察を前に 

4.解決篇：絞り込み～mod5～

5.おわりに

1.今月の問題

今月取り上げる問題はこちらになります。

いきなり英語が出てきて面食らわれた方もいらっしゃるでしょう。

大丈夫です、すぐに日本語へ直します。

若干意訳チックですが、問題の内容としては変わりないでしょう。

問題の意味そのものは、比較的簡単に理解できます。文章中で定義されている「funnyな数」という概念が重要になってきますので、これについて確認してみることにしましょう。

この文章中での「funnyな数」は

・正の整数である

・その数が持つすべての正の約数について、2を足したら素数になる
という2条件を満たすものすべてです（以下、約数と言えば正の約数のことを表すとします）。

具体例を挙げます。

例えば、5はfunnyな数になりそうです。5の約数は1と5の2つだけですが、これらに2を足した\(1+2=3\)と、\(5+2=7\)は、両方とも素数になっていますね。

そのほかにも、例えば9もfunnyな数です。9の約数は、1と3と9の3つだけです。

これらは\(1+2=3\)、\(3+2=5\)、\(9+2=11\)、とすべて2を足せば素数になります[2]。

一方で、例えば4はfunnyな数ではありません。4は2を約数に持ちますが、\(2+2=4\)はどう見ても素数じゃありません。

他にも、例えば25はfunnyな数ではありません。25は25自身を約数に持ちますが、\(25+2=27\)は素数ではない(3で割り切れる)ですからね。

どうでしょう、ちょっと輪郭が見えてきましたか？

以下は解説パートです。これからこの問題を自力で解きたい、という方は一度立ち止まって考えてみてください。

[1] https://artofproblemsolving.com/

2.解法の糸口～mod3～

それでは、ここからが本番です（以下説明のため、funnyな数ではない正の整数を「funnyでない数」と呼称することにします）。

また、解説中では幾つかの基本的な事実を解説無しに用います。具体的には

・正の整数\(n\)について、その正の約数の個数は、\(n\)を素因数分解した時の各指数に1を加えて積をとった値に等しいこと

などが挙げられます。

さて。スタート地点はいくつも考えられますが、「funnyな数が満たすべき条件を考える」というのが自然な方向でしょう。また、それに付随して「funnyでない数が満たす条件を考える」というのも良いと思います。

今回は後者から攻めてみましょう。先ほど具体例を挙げた、funnyでない数を考察します。

例えば、4はfunnyでない数でした。ちょっと考えてみると、偶数は必ず2を約数として持ち、\(2+2=4\)は素数ではありませんから、偶数は必ずfunnyでない数になります。

対偶を取れば、「ある正の整数がfunnyな数ならば、その整数は奇数である」ということになりますね。

25もfunnyでない数でした。25の約数は1,5,25しかなく、\(25+2=27\)は素数でないという流れでした。これはちょっとピンと来にくい例です。

他の、偶数ではないfunnyでない数を考えましょう。例として、35もfunnyでない数です。35は7を約数として持ちますが、\(7+2=9\)は素数ではないですね。

さて、以上のほかにも無数にfunnyでない数は存在します。実際に、その他の数でも実験をしてみてください。すると、幾つかのfunnyでない数に共通する特徴が見つかります。

例えば、実は偶数ではないfunnyでない数は、「2を足すと3の倍数になるような約数」を持つようなものが結構多いのです。25も35もそうでした。他の例も挙げてみましょう。

・65は13を約数に持ちますが、\(13+2=15\)は3の倍数になります（勿論funnyでない数です、以下同様）。

・85は85自身を約数に持ちますが、\(85+2=87\)は3の倍数になります。

どうでしょう？ なんだか偶然とは思えないですね（まあ偶然のこともあるのですが）。

となれば、次に気になるのは「どうして2を足すと3で割り切れる約数を持つ数が多数存在するのか」という点になります。このままでは考えにくいので、もう少し問題を言い換えてみましょう。

「2を足すと3で割り切れる数」というのは、つまり「3で割ると1余る数」ということです。要は、「3で割ると1余るような約数を持つ正の整数とはどんな数なのだろう？」という問いに帰結できるわけです。

「3で割った余り」を考える問題、受験生の皆さんなら一度は目にしたことがあるのではないでしょうか。ここまで来てしまえばしめたものです。

例えば先ほどの35の例だと、7を素因数として持った時点でもうfunnyでない数になるのは確定だったわけです。65も同じです。13を素因数として持った時点でfunnyでない数になります。

これで謎の半分は解けました。つまり、3で割って1余るような素因数を持った数は、funnyでない数になるのです。対偶を取れば、「ある正の整数がfunnyな数であるなら、その数を素因数分解したとき、3で割って1余るような素因数は現れない」ということです。

でも、じゃあ85はどうでしょうか。\(85=5×17\)ですが、5も17も3で割ったら2余る素数です。25も、 ですから同じ状況です。必ずしも、3で割って1余る素因数を含んでいないからといって、funnyな数だとは限らないのです。

ですが、この謎も比較的簡単に解けてしまいます。ポイントは、3で割ったら2余る整数同士を掛け算すると、3で割ったら1余る整数になる、という事実です。

証明は以下の通り、簡単な式変形で済みます。

この事実から「もしある正の整数を素因数分解したとき、3で割って2余る素因数が（重複含め）2つ以上現れるのならば、その数はfunnyでない数になる」ということが言えます[2]。

対偶を取れば「もしある正の整数がfunnyな数なら、その整数を素因数分解したとき、3で割って2余る素因数は高々1つしか現れない[3]」ということになります。

これはfunnyな数にまつわる、大きな制限です！

ここまでの洞察をまとめましょう。つまり、ある正の整数がfunnyな数ならば、その数は……

・奇数である

・3で割って1余る素因数をもたない

・3で割って2余る素因数は高々1つしか持たない

ような数であるということです。ここからは、この手がかりを基に絞り込みを行います。

[1] 実は行間がありますが、結論としては正しいです。

[2] funnyな数の条件には、2を足す前の数が素数であることは含まれていません。あくまで、足した後が素数であればそれで良いのです。

[2] 「高々n個」は、「多くともn個以下」と読み替えてもらっても構いません。つまり、今回であればそのような素因数は0個か1個しか持たない、という意味です。

3.最後の考察を前に

さて、細かい考察を始める前に1つ。実はここまで意図的に避けてきた話題があります。

お気づきの方も多いでしょうが、それは「ある正の整数が3を素因数として持っていた場合、その数がfunnyな数かどうか」という話です。

3で割って1余る、2余る素因数については、前項で考えた通りです。では、唯一3で割り切れる素数——つまり3自身については？

その問いに答えるのは容易です。まず、\(3^1=3\)、\(3^2=9\)、\(3^3=27\)、\(3^4=81\)、\(3^5=243\)です。そして、\(3+2=5\)、\(9+2=11\)、\(27+2=29\)、\(81+2=83\)までは素数ですが、\(243+2=245\)は素数ではありません。このことから、素因数分解したときに3が5回以上現れるような数はfunnyでない数であると分かります。

例によって対偶を取れば、「ある正の整数がfunnyな数であれば、その整数を素因数分解したときに、素因数3は高々4個しか現れない」ということになります。これで、先ほどのfunnyな数が持つ特徴リストに、1つ項目を増やすことができます。

・奇数である

・素因数3は高々4つしか持たない

・3で割って1余る素因数を持たない

・3で割って2余る素因数は高々1つしか持たない

4.解決篇：絞り込み～mod5～

さて、ここから問題文の条件——「正の約数の個数が最大であるようなfunnyな数」に合いそうな数を探していきましょう。

ここでは、最後の条件「3で割って2余る素因数は高々1つ」という部分で場合分けをするのが楽でしょう。つまり、そのような素因数を持つか、持たないかだけを考えればいいのです。

このうち、3で割って2余る素因数を持たない場合は簡単です。この場合は3しか素因数を持たないはずですから、\(3^4=81\)が、funnyな数であって約数の個数が最大になるということが、先ほどの考察より明らかです。この場合、約数の個数は5つです(1、3、9、27、81の5つ)。

では、3で割って2余る素因数を持つ場合はどうでしょうか。その素因数をpと書くことにしましょう。その他の素因数は3しかありえないことから、条件を満たす数は\(3^m×p\)(mは4以下の正の整数)と表せるはずです。
mの値が大きければ大きいほど約数の個数は多くなります。ひとまず\(m=4\)と固定して、\(3^4×p\)という数がfunnyな数になるかどうか考えてみましょう。

少し実験してみましょう。pは3で割って2余るような素数でしたね。

・\(p=5\)だとすると、\(3^4×5=405\)です。このとき、405は405自身の約数ですが、\(405+2=407\)は（11で割れるので）素数ではありません。

・\(p=11\)だとすると、\(3^4×11=891\)です。このとき、33は891の約数ですが、\(33+2=35\)は（5で割れるので）素数ではありません。

・\(p=17\)だとすると、\(3^4×17=1377\)です。このとき、153は1377の約数ですが、\(153+2=155\)は（5で割れるので）素数ではありません。

・\(p=23\)だとすると、\(3^4×23=1863\)です。このとき、23は1863の約数ですが、\(23+2=25\)は（5で割れるので）素数ではありません。

全然……見つかりませんね……。

小さい順から\(p\)の候補となる数を探してきたのですが、一向にfunnyな数になりそうな感じがしません。

ひょっとすると、そんな\(p\)は存在しないのかもしれないですね。

こう疑うのも自然なことで、実際、\(p=5\)を例外として、それ以外の場合はすべて「2を足すと5で割れるような約数」が存在していることが分かります。これはさっきの3で割るときと同じような規則性が背景にあるのではないか、と。

これを確かめてみましょう。

\(3^4×p\)は、必ず\(p\)、\(3p\)、\(9p\)、\(27p\)、\(81p\)の5つを約数として持ちます。そして、\(p\)を5で割った時の余りは、必ず0か1か2か３か4になります。試しに余りが1になるときを考えてみましょう。このとき、適当な自然数kが存在して、\(p=5k+1\)と書けるはずです。

すると、\(3p+2=3(5k+1)+2=15k+3+2=15k+5=5(3k+1)\)ですから、3pに2を足した数は5の倍数になります。\(p\)の条件からして、これは素数ではないでしょう。

余りが他の数だったときも同様に考えると、先に挙げた5つの約数の中に、必ず2を足すと5の倍数になるものが存在します。\(p=5\)のとき以外は、これはすべて素数にはなりえないはずです。つまり、\(p\)が5でない素数の時、\(3^4×p\)はfunnyでない数になってしまうのです。

そして、\(p=5\)のときも個別に検証した通り、\(405+2=407\)が素数ではないので、funnyでない数になります。

したがって、\(3^4×p\)という形の数はすべて、funnyでない数になるのです。

すると、\(3^m×p\)における \(m\)の値は4ではありえないことになります。

惜しいですが、1つ減らして\(m=3\)でやってみましょう。

\(3^3×p\)について、\(p\)、\(3p\)、\(9p\)、\(27p\)は必ずその約数となります。ということは、先ほどと同様に考えることで、\(p\)が5でない素数の場合はfunnyでない数になることが明らかです。

\(p=5\)のときはどうでしょう？

\(3^3×5=135\)の約数は、1、3、5、9、15、27、45、135の8つになります。そして、\(1+2=3\)、\(3+2=5\)、\(5+2=7\)、\(9+2=11\)、\(15+2=17\)、\(27+2=29\)、\(45+2=47\)、\(135+2=137\)はすべて素数です。

つまり、\(p=5\)のとき、135はfunnyな数になります。そして、約数の個数は8つです。先に調べた81のときの、５つよりも多いですね。

\(3^m×p\)の\(m=3\)のときは以上ですべて考察完了になります。

あとは\(m=2,1\)のときを調べてもいいですが、既にこの時点で約数の個数が8つを下回ることは明らかなので、これで終了とします。

以上より、funnyな数の中で約数の個数が最大になるのは、135のみであると結論づけられます。

5.おわりに

この問題の解説は以上になります。

この問題の良いところというのは、実験→考察→証明という、受験数学において難問を解く際のプロセスが自然に導けるような作りになっていることです。

適当に実験を重ねれば、3で割った余りに着目することに気付くのは難しくないでしょう。また、その後5で割った余りに着目するのも、実験でそこに目が向くよう仕向けられていたからです。

受験で実際に出題されるとしたら誘導はつくかもしれませんが、手探りで絡まった問題をほどく体験も楽しいもので、こうして問題をこねくり回す中でたくさん得られるものがあるのだろうとも思います。

そんなわけで、この受験の”スタートの時期”だからこそ、色んな難問に頭をひねってみるのもいいのではないでしょうか。

今月もここまでお付き合いくださり、ありがとうございました。来月もお楽しみに