皆さんこんにちは。東大セミナーの北川です。
今年も国公立大学二次試験前期日程が終了し、新たな年度がスタートしました。昨年度の東大セミナーグループとしての合格実績は、先月12日にご紹介済み[1]です。是非ご覧ください。
それはそれとして、受験数学好きにとっては今年も様々な面白い問題の公開に沸き立っているところです。私の中では東大文科第2問の、典型問題っぽく見えるけど典型問題的な処理をすると欲しい答えにならない洒落た問題も好きなのですが、それ以上に京大理系第4問[2]が面白かったので、こちらを紹介いたします。
[1] 2024年度各大学合格実績と所感について – 石川県金沢市・野々市市・白山市の学習塾 – 東大セミナー (tohsemi.com)
[2] 「先月は第6問を解説するといってたじゃないか」と思われたそこのあなた。確かに最初は大問6を解説しようと思っていたのですが、思った以上に煩雑かつ面白くない記事になりそうだったのでやめておくことにしました。ご承知おきください。
目次
今回紹介する問題は以下の通りです。
与えられた自然数\(a_0\)に対して、自然数からなる数列\(a_0,a_1,a_2,…\)を次のように定める。
\(
a_{n+1}=
\begin{cases}
\frac{a_n}{2}(a_n が偶数のとき) \\
\frac{3a_n+1}{2}(a_n が奇数のとき)
\end{cases}
\)
次の問いに答えよ。
(1)\(a_0,a_1,a_2,a_3\)がすべて奇数であるような最小の自然数\(a_0\)を求めよ。
(2)\(a_0,a_1…a_10\)がすべて奇数であるような最小の自然数\(a_0\)を求めよ。
問題の意味そのものは、高校1年生で理解できるような簡単な内容になっています。以下で説明していきましょう。
最初に、ある自然数(ここでは正の整数を指します)を1つ決めてメモします。そして、その数が偶数か奇数かによって、次の操作のうちどちらか１つを実行します。
・その数が偶数なら、その数を半分にした数を新しくメモする。
・その数が奇数なら、その数に3をかけて、1を足してから、半分にした数を新しくメモする[3]。
さて、操作の結果として、あなたは何か新しい数を1つメモすることになりますね。そうしたら、その新しくメモした数に対して、また同じようにどちらかの操作を行います。すると、また新たな数を１つ得ることになり……と、この操作を延々と繰り返すことができるはずです。
さて、こうして得られた数は、実はすべて自然数になることが分かります。偶数の場合は偶数を２で割っているので、結果が自然数になるのは当然です。奇数の場合も、奇数に３をかけて１を足すと偶数になります[4]から、これを２で割れば自然数になるのは当然です。
ここまで分かれば、(1)と(2)で聞かれている内容は簡単です。
(1)は、「最初の数から３回操作を行ってみたら、（最初の数も含めて）メモした数は全部奇数になったよ。このとき、最初の数として指定した数はどんな数になりますか？ あり得る中で一番小さい数を答えてください」という意味です。
(2)は、「最初の数から10回操作を行ってみたら、（最初の数も含めて）メモした数は全部奇数になったよ。このとき、最初の数として指定した数はどんな数になりますか？ あり得る中で一番小さい数を答えてください」という意味です。
どうでしょう。これまで紹介してきた問題の中でも、意味が非常に分かりやすい問題だと思いませんか？
[3] 例えば5を選んだなら、5×3+1=16で、これを半分にして8を得ます。
[4] 毎度のことにはなりますが、なんで？ と思ったら自分で実験してみると分かりやすいです。
では、実際にこの問題を解いてみましょう。
「えー、またどうせ難しい数学的な手法を使うんでしょう」と思ったそこのあなた。よく考えてみてください。
今回は「条件を満たすような、一番小さな自然数」を求めればいいのです。ならば1から順に試してみればよいのではないでしょうか？ いつか上手くいく数が現れれば、確実にそれと分かります。しかもこの方法なら、例えば「30以下の数はダメだったけど、31で初めて上手くいった」という状況ができれば、「31が条件を満たす最小の数だ！」と断言してよくなりますよね。
おまけに、最初に選ぶ数も奇数である必要があるわけですから、2,4,6…といった偶数は検証する必要がないのです。奇数だけ検証すれば十分です。
というわけで物は試し、やってみましょう。実験の結果をどんどん記載していくので、読み方を説明します。
・奇数に対し、「3をかけて1を足した後に２で割る」という操作を施した結果を以下にメモしていきます。例えば、A→Bと書いてある場合、「Aという数に操作を施したら、結果はBという数になりました」と読み取ってください。
・A→B→Cと記載されている場合は、「Aに操作を施したらBになって、Bに操作を施したらCになりました」という意味だと思ってください。より複数の矢印が連なっている場合も同様です。
・また、結果の最後に「(n回)」と書いてある場合、「n回操作したら偶数になってしまった」ことを表すものとします。
先のnが3以下だと、書かれた４つの数のどれかに偶数が混じることになってしまう[5]ので、nが初めて４以上になるような奇数を探すのが目標です。
じゃ、いきますよ！
～実験の記録～
1→2 (1回)
3→5→8 (2回)
5→8 (1回)
7→11→17→26 (3回)
9→14 (1回)
11→17→26 (2回)
13→20 (1回)
15→23→35→53→80 (4回)
やった！ というわけで、(1)の答えは15です。
「えっ、こんな簡単に答えが出ちゃっていいの？」と思ったそこのあなた。ここまで正しい理屈だけをこねて話をしてきたので、これでよいのです。
京大理系の問題とはいえ、なんともあっさり解けてしまいましたね。
[5] この先にある実験結果の、7についての項目を見ると分かりやすいでしょう。この場合、3回目の操作の結果として「26」が現れているので「3回の操作の結果がすべて奇数」にはなっていないことに注意が必要です。
では、この調子で(2)も解いてしまいましょう。今度は「10回操作を施して全部奇数」になるような最小の数を求めるのでした。先の実験結果の書き方に従えば、nが初めて11以上になるような数を探せばいいことになります。
それでは実験を続けてみましょう。
～実験の記録(続き)～
…
17→26 (1回)
19→29→44 (2回)
21→32 (1回)
23→35→53→80 (3回)
25→38 (1回)
27→41→62 (2回)
29→44 (1回)
31→47→71→107→161→242 (5回)
…
い～や見つからんやないかい！！！！！！
(1)の実験も併せてかなりの回数3をかけて1で割っていますが、11回どころか10回すら見えないですね。こりゃあマズいです。もちろんこのまま、ボン・ジョヴィの”It’s my life”を流しながらなかやまきんに君に手計算させてもいい[6]のですが、場合によっては試験時間が終わってしまう可能性も考えられます。
ここからは、頭を使っていい感じに楽をする必要がありそうです。よって、少しだけ難しい話がスタートします。高校2年生までで習う知識があればついてこられるはずですが、数式の意味が分からない場合は、その部分だけを読み飛ばし、まずは結果と理屈だけを追ってみてください。
また、この解答は「最短ルート」ではありません。なるべく自然な発想で問題を捉えて、より一般的な主張を証明することで問題を解くような感じになります。こちら、ご了承下さい。
ではまず、先ほどの実験結果を別の視点から見てみましょう。
パッと目に付くのは、2回に1回は「1回の操作で偶数になる数」が出てくるという点でしょう。偶然にしてはちょっと出来すぎているようにも思えます。一体、どうしてこのような結果が得られるのでしょうか？
1回の操作で偶数になる数を羅列してみましょう。
$$1,5,9,13,17,21,…$$
この数たちの並びを見てみると、すぐにあることに気が付きます。隣り合う数同士の差が4になっていますね。つまり、この数たちは「初項が1で公差が4の等差数列」をなすのですが、この数列の 番目に登場する数は\(4n-3\)と表すことができます[7]。
\(4n-3=4(n-1)+1\)と見なすことにすれば、これらの数はすべて、4で割って1余る数になると言えます。
以上の結果より、「4で割って1余る数に対して操作をすると、1回の操作で偶数になる」ような気がしてきます。これの証明は容易く、以下の通り行うことができます。
[証明]
\(n\)を自然数とする。自然数\(4n-3\)に1回の操作を施すと、以下のような結果になる。
$$\frac{3(4n-3)+1}{2}=\frac{12n-8}{2}=6n-4=2(3n-2)$$
\(3n-2\)は任意の\(n\)について自然数であるから、\(2(3n-2)\)は任意の\(n\)について偶数である。
かくして、「4で割って1余る自然数は、1回の操作で偶数になる」と示せました。しかしこれだけでは考察材料が不足しています。
これを足掛かりに、例えば「2回の操作で初めて偶数になる数」の特徴を探ってみることにしましょう。
まずは同じように、そのような数を並べてみましょう。
$$3,11,19,27…$$
今度は、3を初項とする公差8の等差数列になっています。そして、さっきの証明とほとんど同様にして、「8で割って3余る自然数は、2回の操作で初めて偶数になる」と示すことができます。
同様にして、今度は「3回の操作で初めて偶数になる数」を考えてみましょう。
$$7,23,39,…$$
今度も同様に予想して考えると、「16で割って7余る自然数は、3回の操作で初めて偶数になる」と示すことができます。
さて、そろそろ勘のいい方は規則性に気が付いてきたのではないでしょうか。
ここまでに得られた主張はすべて、「\(a\)で割って\(b\)余る自然数は、\(c\)回の操作で初めて偶数になる」というものでした。
\(a\)に入るのは、\(4=2^2,8=2^3,16=2^4\)など、すべて「2の累乗」になっています。
\(b\)に入る数はやや難しいですが、\(1=2^1-1,3=2^2-1,7=2^3-1\)であることが分かると、「2の累乗-1」の形であることも予想がつくでしょう。さらには、対応するaの値とも何か関係がありそうな感じがしますね。
\(c\)に入る数は、単純に\(a\)を2の累乗に直した時の指数から1を引いた数であると当たりがつきます（例えば、「4で割って1余る数」の場合だと、\(a\)は\(4=2^2\)なので指数は2だが、この時の\(c\)の値は\(2-1=1\)である）。
以上を踏まえると、こんな予想が立ちます。
[予想]
\(2^m\)で割って\(2^{m-1}-1\)余る自然数は、\(m-1\)回の操作で初めて偶数になる(ただし\(m\)は自然数とする)
（\(m=1\)の場合は、2で割って余りが出ないなら、操作するまでもなく偶数であるという意味だと解釈する。この主張内容は正しい）
仮にこの予想が正しいとすると、\(m=12\)を代入した時には
「4096で割って2047余る自然数は、11回の操作で初めて偶数になる」
という主張になるわけです。11回目の操作で初めて偶数になるなら、10回目の操作までは奇数ということなので、(2)の条件に適います。すると、答えとして考えられる数は2047ということになりますね。
結構大きい数になりました。実験だけで解こうとしていたらどうなっていたことか……。
何はともあれ、これでようやく解答の方針が立ちました。後は上記の予想が正しいことと、上記の予想を考えればそれで充分なことを示していくことにします。
[6] 何のこと？ と思った方は調べてみてください。一種のパロディネタです。
[7] 理屈の説明は省きます。「ホンマか？」と思う方は実験して確かめてみてください。
解答にあたって、まず確かめておきたいのは「上の主張は”ちゃんと”数を分類できているのか？」というところです。
例えば4で割って1余る奇数が、同時に8で割って3余ってしまう、というように、この分類に”ダブり”が発生することはないのでしょうか？
或いは、ある奇数が4で割っても1余らないし、8で割っても3余らないし、16で割っても7余らないし……というように、分類に”漏れ”があることはないのでしょうか？
もしそんなことが発生すれば、先の予想はそもそもナンセンスだということになってしまいます。確かめてみましょう。
“ダブり”については、以下のようにして起こり得ないことを証明できます。
[証明]
\(m,n\)をともに自然数とし、\(m>n\)とする。ある奇数\(a\)が、\(2^m\)で割って\(2^{m-1}-1\)余り、かつ\(2^n\)で割って\(2^{n-1}-1\)余るとする。
この時、適当な自然数\(k\)が存在し、
\(a=2^m k+(2^{m-1}-1)=2^n (2^{m-n} k+2^{m-n-1}+1)+(2^n-1)\)
と書くことができる。\(m,n\)の大小関係から、\(2^{m-n} k+2^{m-n-1}+1\)は整数であり、また、\(2^n>2^n-1\)であるから、\(a\)を\(2^n\)で割った余りは\(2^n-1\)である。
一方で、仮定より\(a\)は\(2^n\)で割って\(2^{n-1}-1\)余る数なので、\(2^{n-1}-1=2^n-1\)が成り立つことになるが、これは不合理である。
従って、どのような奇数についても、\(2^m\)で割って\(2^{m-1}-1\)余り、かつ\(2^n\)で割って\(2^{n-1}-1\)余るということはありえない。
また、”漏れ”がないことも、以下の通り証明することができます。
[証明]
すべての偶数は、適当な自然数mと適当な非負整数[7]\(k\)が存在して、\(2^m (2k+1)\)と表すことができる[8]。つまり、すべての奇数は\(2^m (2k+1)-1\)という形で表すことができる。
すると、\(2^m (2k+1)-1=2^{m+1} k+2^m-1\)である。\(k\)は整数であるから、この奇数を\(2^{m+1}\)で割った余りは\(2^m-1\)である。よって、どのような奇数であっても、適当なmが存在し、\(2^{m+1}\)で割った余りは\(2^m-1\)になる。
したがって、予想の中で用いている分け方は”ダブりなく”かつ”漏れなく”分類できていることが分かりますので、予想がナンセンスではないことが保証されたということになります。
では、いよいよ予想そのものの証明に移りましょう。さっき具体的な数で示したことを応用してみるのがポイントです。
[証明]
先の”漏れなく”の証明で述べた通り、すべての奇数は適当な自然数\(m\)と適当な非負整数\(k\)が存在して、\(2^m (2k+1)-1\)と表すことができる。
予想の内容について、\(m\)に対する数学的帰納法で証明する。
\(m=1\)のとき、\(2^m (2k+1)-1\)に対して1回操作を施した結果が以下の通りである。
\(\frac{3\{2^m (2k+1)-1\}+1}{2}\)
\(=\frac{2^{m+1}・3k+2^m・3k-2}{2}\)
\(=2^m・3k+2^{m-1}・3k-1\)
\(=2^{m-1} {2(3k+1)+1}-1\)
ここで、\(3k+1\)は整数である。新たに\(3k+1=k_1\)と定義すると、1回操作を施した後の数\(s_1\)は、\(s_1=2^{m-1} (2k_1+1)-1\)と書くことができる。
ここで、\(m-1=0\)なので、\(2^{m-1} (2k_1+1)-1=2k_1\)となり、\(s_1\)は偶数。
つづいて、ある\(m\)についてこの予想が正しいと仮定して、\(m+1\)のときを考える。
\(n_0=2^{m+1} (2k+1)-1\)に対して、1回だけ操作を施す。
すると、先のとおり操作を施した後の数\(n_1\)は、先の\(k_1\)を用いて、\(n_1=2^m (2k_1+1)-1\)という形で表すことができる。帰納法の仮定より、\(n_1\)は\(m\)回の操作で初めて偶数になるから、\(n_0\)は\(m+1\)回の操作で初めて偶数になると言える。
従って、題意は示される。
以上より、予想が正しかったことが示せました。
後はこの予想を の場合に適用すれば、「4096で割って2047余る自然数は、11回の操作で初めて偶数になる」という主張を得られます。
4096で割って2047余る自然数のうち最小のものは、当然2047です。
したがって、(2)の答えは2047、ということになります。実験はしませんが、電卓でポチポチやるだけでこれが本当に11回目の操作で初めて偶数になるか確かめられるので、気になる方はやってみてください（最小かどうかは手作業で突き止めるのは厳しいでしょう……）。
さて、以上で問題の解説は終了になります。
この問題は、実験をすることによって閃きやすくなり、かつその誘導も丁寧という良問だと個人的には認識しています。今回はその発想の過程までひとつひとつ書いたので、やや冗長な仕上がりになってしまいましたが、本番ではもう少し簡潔に記述するとよいと思います。具体的にはすべての整数が非負整数\(m,k\)を用いて\(2^m (2k+1)\)と書けることを示し、最後の証明を回せば十分でしょう。
[7] 非負整数とは、負ではない整数のことです。正の整数だけでなく、0も含む表現です。
[8] 厳密にやる場合はこれも証明したいですが、省きます。数学的帰納法を上手く使えば証明できますので、興味がある方は試行錯誤してみてください。
最後に、この問題の背景についても少しお話しましょう。
今回の問題、実は問題文自体に冗長な部分があることにお気づきでしょうか？
与えられた自然数\(a_0\)に対して、自然数からなる数列\(a_0,a_1,a_2,…\)を次のように定める。
\(
a_{n+1}=
\begin{cases}
\color{red}{\frac{a_n}{2}(a_n が偶数のとき)} \\
\frac{3a_n+1}{2}(a_n が奇数のとき)
\end{cases}
\)
次の問いに答えよ。
(1)\(a_0,a_1,a_2,a_3\)がすべて奇数であるような最小の自然数\(a_0\)を求めよ。
(2)\(a_0,a_1…a_10\)がすべて奇数であるような最小の自然数\(a_0\)を求めよ。
赤字でハイライトしたこの部分、よく考えると不要ですよね。
なぜなら、(1)にせよ(2)にせよ、規定回数になる前に1度でも偶数になったら、そこで考える必要はなくなり\ます。つまり、問題を解くだけなら「\(a_n\)が奇数のときだけ操作のルールを用意し、\(a_n\)が偶数になったらストップする」でよかったはずです。
なぜ、このように「無意味なルール」を付け足したのか？ その鍵は、数学の世界に存在する、とある未解決問題が握っています。その問題の名は「コラッツ予想[10]」と言います。
どうでしょう？ 結構言っていること自体はシンプルですよね。例えば、最初の自然数として4を選ぶと、4→2→1と、すぐに1になります。もう1つ例として、7を選ぶと、7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1と、長いですが確かに有限回の操作で1になりました。
問題の意味も、計算も、かなり単純です。小学生にもわかるような内容です。
にもかかわらず、1963年に広く知られるようになってからおよそ70年が経った今でも、この主張を完璧に論証した人物は1人もいないのです。アメリカの数学者、ジェフリー・ラガリアス氏は、2010年の著書でこの問題に対し以下のように述べています[11]。
要するに、コラッツ予想は小学生でも中身が分かるのに、最先端にいる人が「今の数学ではちょっと無理」と言ってしまうほどの超難問、というわけなんです。意外ですね！
さて、話を今回の問題に戻しましょう。先に挙げたコラッツ予想の中の操作、今回の問題のそれとよく似ている……というか、本質的には同じです[13]。
つまり、この問題においては無意味な偶数のときの操作まで加えて出題したのは、これがコラッツ予想を下敷きにした問題だよ！ とこっそり主張する、京大の遊び心みたいなものだと言えるでしょう。
ですが、それだけではありません。京大の問題が持つ意味を考えてみるともっと面白いことが分かります。
先ほどの問題で証明された事実を確認してみましょう。
[事実]
\(2^m\)で割って\(2^{m-1}-1\)余る自然数は、\(m-1\)回の操作で初めて偶数になる(ただし\(m\)は自然数とする)
この操作については
・操作前の数が偶数なら、次に操作によって得られる数は小さくなる。
・操作前の数が奇数なら、次に操作によって得られる数は大きくなる。
という特徴があります（前者はほぼ自明ですし、後者も任意の奇数 に\(k\)に対して、\(\frac{3k+1}{2}\) の方が大きいと言われればこれもほぼ当たり前です）。
ということは、それなりに大きい を取って初期値を決めることで、操作のたびに数はどんどん大きくなっていくはずです。でも、コラッツ予想の主張は「最終的に1になる」というものでした。
一見相反するように見える2つの主張ですが、もしコラッツ予想が正しいのなら、「操作の結果、一旦非常に大きくなる数があったとしても、その後のどこかでどんどん小さくなっていって最終的に1に辿り着く」というわけです。
「スタート地点から見て充分大きくなる数がある」のに、「最終的に全部1になる」としたら、ますます直観に反するような気がしてきます。もしかしたらホントに無限に大きくなるサイクルがあるのかも……？
京大が入試問題としてこのような「コラッツ予想の不思議な点」を持ち出してきたわけは、京大も単に遊び心だけで未解決問題を引用したのではなく、問題そのものの奥深さも味わって欲しいというメッセージを込めたかったからではないか。と、そんな気がします。
さて、ここまでを通してコラッツ予想そのものをもっと知りたい！ と思った方もいらっしゃるでしょう。
しかし残念なことにコラッツ予想については、未解決問題であるだけでなく、そのアプローチすら未だ難しいところが多いようで、日本における解説はほぼ存在しないのが現状です。
そんな中で、昨年に技術評論社より出版された『素数って偏ってるの？ ～ABC予想，コラッツ予想，深リーマン予想～』（小山信也）の第2章には、コラッツ予想の研究においてまさに今なされていることが書かれており、私たちのような素人でもその魅力に触れることができます（現状最先端の結果とされるUCLAのテレンス・タオ教授によるアプローチも噛み砕いて説明されています！）。この予想について現在でも簡単に手に入る一般の和書というのは数少ないもので、是非一度手に取ってみて頂きたいです。
また、朝倉書店より出版されている『数論<未解決問題>の事典』という書籍には、コラッツ予想証明に対する歴史的経緯が（少しばかりではありますが）載っています。原著者のリチャード・ガイ氏はカルガリー大学の数学教授だった方で、未解決問題に対する並々ならぬ関心があったようです。コラッツ予想もさることながら、その他の未解決問題に対しても興味を持つ一助になるかもしれません。
今回の解説はここまで。お読みいただき、ありがとうございました。
来月もまたよろしくお願いします。
[10] コラッツ予想には\(3n+1\)問題、角谷の問題、シラキュースの問題……など様々な別名はありますが、恐らくはこの名前が最も浸透しているのではないでしょうか。
[11] “The 3x+1 Problem: An Overview”,https://arxiv.org/abs/2111.02635(2024/4/16最終確認)
[12] 注と訳はこの記事の筆者によるものです。
[13] 奇数の時の操作が若干違いますが、よく考えると奇数の操作を施した段階で偶数が得られるので、次は偶数の操作をするのが確定になります。なので本質的には今回の問題と一緒と捉えられるのです。
東大セミナーを知る
コース紹介
会社案内
Copyright ©金沢市・野々市市・白山市の学習塾 - 東大セミナー All Rights Reserved.