Youtubeを散歩してたら……
なんとなくオシャレ、かつあんまし時間のかからなそうな整数論の問題をYoutubeで見かけた*1。
【話題の一行問題】東大数学2015第5問【2015Cmが偶数】 - YouTube
というわけで、久々に更新。
サクサクのおやつみたいに手軽に楽しめる問題なので、遊びたい人は自分でチャレンジしてみてください。ちょっとした気分転換になると思うよ!
2015東大理系 第5問
問題は次の通り、
『を
以下の正の整数とする。
が偶数となる最小の
を求めよ。』
これを気楽に解いてみた*2。
2進法を使って解いてみたのが、結構気に入ったので公開してみる。そう、2進法でガンガンいってるので、受験生は真似しない方がいいかも*3……
要は、どこかの数学好きが、少しでも楽しくなればOKというスタンスなのだ。
今回のあらすじ
ステップ1:の場合に
を調べてみた。これは寄り道。
ステップ2:進法を使う解き方の始まり~。そして、怪し過ぎる数を見つける!
ステップ3:が奇数であり続ける、そのギリギリまで一掃する!
ステップ4:がついに偶数に!ついでに一般化も?
ステップ1(寄り道):
のとき、
は
で最大何回割れるか?
最初にやった実験を紹介してみる。けど、この方針は途中で面倒になって放棄したので、興味ない人や解法だけ知りたい人はステップ2から読んだ方が良いです。
整数問題が苦手な人が、この問題を考える練習くらいにはなってるかも?*4
が偶数かどうかを考えたいから、分子分母がで何回割り切れるかを調べるのが基本方針になる。
そこで、分母に現れるが
でぴったり
回割り切れる
と表せる場合から考えてみる。
このとき、は
で最大何回まで割り切れるか?(素因数
の個数)
これを知りたくなって、冪のリズムに合わせて、
とかテンポ良く書いてみた。
それで、この式をちょっと観察すると、
「に含まれる偶数は、
に現れる数1つ1つに
をかけたものに一致する」
と気づく。逆に言うと、
「に含まれる偶数を全て取り出し、それぞれ
で割ってから、もう一度かけ直すと、
にピッタリ一致する*5。」
この観察結果から、に含まれる素因数
の個数を
とおいて考えてみる。まず、
は
で
回だけ割れるから
だ。一般の
のときは、上に書いた観察から、
と書けることが明らかなので、少し式変形して、
つまり、は
で、最大
回割れる。
よって、
『定理1: は
で、最大
回割れる。』
と分かる。これを使うと、から
までの数を1つずつかけた数は、
で
回割れるとかすぐにわかる*6。
ステップ2: 2015を
の冪を使って表してみたくなる。そして、2進法へ……
分母に現れるが
の冪の場合は、ステップ1で調べた。
次は分子だが、は偶数じゃない。けど、
の冪を使う方針を押し通したい。そんな理由で、
進法を使ってみることにした。
すると、驚愕の事実が分かった!
『驚愕の事実1: は2進法で
と表せる』
これは、
と表せるということなので、あからさまにが怪しい*7。
推理小説にしたら、「犯人臭」出し過ぎもいいところじゃないか~
これで、が犯人(正解)だったら、推理小説としては残念なレベル……
初見で感じた「オシャレ感」も3割りくらい引っ込めたい気持ちに*8……
一応結末は、この記事の最後ということで……
さて、計算結果1を改めて見つめて、桁の小さい方から大きい方へと指でなぞってやる。すると、ちょうど真ん中にあるが「壁になってる感」がある。
そこで少し観察をして、進法の定義に立ち返りつつ進むことにした。
突然だが、ここで以下の数々を見比べていただきたい。
と
と
と
さて、右と左の数の関係は何か?
答えは、「右に書いてある数は、左に書いてある数において、中央にあるより右側の数字だけを取り出したもの」でした。言ってみると、右の数は「
の壁のこちら側」の世界である。
なぜ、「の壁のあちら側*9」を捨てたのか?
答えは、割りとシンプルで、で割れる回数が等しいからだ。つまり、
「とし、
が
でないとする。
このとき、
という2進数を考えると、
を
で割れる最大回数は、
に一致する。」
このことがすぐわからない時は、進数の場合を考えるといいかも。
例えば、進数で
と数を考えると、
なので、と
は
で割れる回数は等しい。
と、こんな感じだ。
以上をまとめて、
『定理2:進法において、
を
でない自然数とする。このとき、
*10を2で割り切れる最大回数は、
のものと一致する。』
と分かった!
これを応用すると、から
までの数に含まれる素因数
の個数が知りたいときは、
と
と
と
と置き換えて調べればいいと言える。このことから、ならば、
の偶奇と、
の偶奇は一致していると分かる。
というわけで、の場合は簡単に調べられるので、ステップ3へGO!
ステップ3:解法(
のとき、
が奇数であること)
の場合、定理2より、
と
は、
で割り切れる回数が等しい*11。
よって、が1から31までの
の偶奇を調べれば、この問題はほとんど解けたようなものと言えるだろう。実際は、
なので、
は折り返し地点までの
まで調べれば十分十分!そこで、以下、
とする。
ここで、が
進法で
と表せることにジッと注目した。
は仮定より、
進法で
と表せる。
後は、と
が2で割り切れる回数が等しいことを示せば良さそうだ。もうほとんど自明かもしれないけど、一応計算をつけておく。
を
で割れる最大の回数が
の場合、
かつ
なので、
この計算から、は
進数で表すと、その下
桁は
に一致する。
従って、と
が
で割り切れる最大の回数は等しい。
これより、が
で割り切れる最大の回数は
と等しいので、
が奇数であることがわかる。
ここまでの話は、そのまま一般化できて、次の定理が成り立つ。
『定理3:自然数が
進法で
と
のみで表せるとき、
に対して、
は奇数。』
ステップ4:解法(
が偶数であること)
残すは、の場合に、
が偶数になることを示したら終わりだ。これも
進法を使うとかなり楽。
ステップ2で示したように、までは
と
は、
で割り切れる回数が等しい。
そこで、
と分解する。はステップ3の結果より奇数なので、
と
に含まれる素因数
の個数を比較すれば終わりである*12。
仮定より、は
でちょうど
回割れる。次に、
となるので、は
で
回割り切れる。
従って、は2で1回割り切れるので偶数。
ステップ3の結果と合わせて、が偶数となる最小の
は
であることが示せた!
というわけで、なんと……最初から最後まで進法のターンでした!
ステップ4での結果も、ステップ3と同様にそのまま一般化できる気がしている*13。つまり、
『予想1:任意の自然数が、
進法で
と表せるとする*14*15、
が偶数となる最少の
は
。』
正しかったら、これで完全な一般化になっているはず!
合ってたら超嬉しい!やほーーい!
*1:自分で解きたくなったから、途中までしか見てません。もし解法かぶりすぎてたら、動画をupした方、ごめんなさい。
*2:あくまで、数学は趣味と気分転換を兼ねてやってます。解けなくても、あんまり気にしないスタイル。
*3:私のときは、高校で2進法習った覚えがない
*4:と言いつつも、ステップ1の半分くらいは、自分用のメモor思考のスナップショットのつもり。
*5:それはもう、シャキーンと音が聞こえそうなくらいに、ピッタリと一致している。
*6:なんも知らない人の前でやると、「計算はえ~」という感嘆、または宇宙人を見たときのような驚き、どっちかの反応をされるかもしれません。なお、むやみに人を驚かすのは推奨してませんよ~
*7:単に怪しいとかいうレベルじゃなくて、「怪しい」。そう、「怪しい」のだ。
*8:それでも、残り7割残してるのは、が
に対して対称的だから。やっぱり、それなりにオシャレなのかもしれない。
*9:の
の壁の左側の数のこと
*11:含まれる素因数の個数が等しいと、すっきり言ってもいい。
*12:ここで、が自然数ではないじゃないかと一瞬気になるかもしれませんが、素因数として含まれる
の個数だけを取り扱っているので問題にはなりません。おまけに、
は「組み合わせの数」を表してるので、全てかけ合わせれば必ず自然数になる。
*13:眠いのと、疲れてきたのとで、また今度確認にするかも。気が向いたら、更新します。
*14:桁目に始めて
が現れるとする