読者です 読者をやめる 読者になる 読者になる

理系男子の独り善がり

仕事や生活に役立ちそうな(実際に役立つかは別として)数学・物理ネタをつらつらと書いていこうと思ってます.

「2015年東大前期理系数学第5問の考え方」をメモしておく

Math Exam

受験生のみなさんは,一息ついているところでしょうか?あまり,息を抜きすぎると体調を崩してしまうかもしれないので,注意してくださいね.

 

まだ,多くの大学の問題はWeb公開まで至っていませんが,その中で注目したのは東京大学前期理系数学第5問です.ざっと目を通した中で「おっ?」と目を引いたものです.ここでは,一会社員が答えを導くまでの過程を朝の通勤電車,お昼休みと段階を追って記してみます.備忘録的な意味もあります.

 

問題は,以下のとおり.

 m2015以下の正の整数とする.{}_{2015} C_mが偶数となる最小のmを求めよ.

 

こういうシンプルな問題は,糸口となるヒントを見つける楽しみもあるので好きです.

 

朝の通勤電車(15分)

整数問題の定番といえば「まずは具体例で」ということで,mを1,2,3,と代入してみます.まあ,素因数2はきれいに消えます.

順番が前後しましたが,問題を読んだ時点で「分子に素因数2が残ること」が条件であり,どこで分子に含まれる素因数2の個数が,分母に含まれる素因数2の個数を上回るのか?を探し当てるということは理解できていました.というか,そういう問題ですよね(笑).

ここで,{}_{2015} C_mの「構造」を考えることにしました.ちょっと大げさな言い回しですが,具体的に書くと

f:id:miwotukusi:20150227063246p:plain

のどちらの表現で考えるのがいいのだろうか?ということです.やはり,素因数2が約分されて消えていく様子を考えるのであれば,下の表現だろうと.

もし素因数2の個数をmの式で書き表すことができれば,ちょろっと方程式を立てる方向でmは求められます.でも,mの式で書き表すなんて,到底できません.

そして,倍数の個数ではなく,素因数の個数を考えなければならないので,4の倍数も8の倍数も・・・と数え上げていく必要があります.と,きたところで,頭の中に「1024=2^10」という数字が浮かびました.これは,2015までの自然数の中で現れるもっとも大きな2^nになります.さらに,この1024を頂点とする三角形も現れました.その三角形の底辺の片方は1,もう片方は2047になります.

f:id:miwotukusi:20150227065945p:plain

ん?もしかして,2015~2047に含まれている素因数2の個数を考えれば何かヒントになる?なるかも!というところで,最寄り駅に到着.思考も一度途中下車することになりました.

 

お昼休み(20分)

お昼を食べて,眠くなるところで思考再開です.2015~2047に含まれる素因数2の個数を調べるために,2^nの倍数を数え上げると以下のようになります.

 32=2^5の倍数は,1個

 16=2^4の倍数は,1個

 8=2^3の倍数は,2個

 4=2^2の倍数は,4個

 2の倍数は,8個

よって,2016×・・・×2047に含まれる素因数2は31個あることになります.ここで出てきた31という数字.31=32-1.32といえばちょうど32=2047-2015・・・,「あ!」と,ここでひらめきました.p進法のところでも書きましたが,IT系の仕事をしていると2進法の数字に何かと敏感になります.そのバックボーンが,このひらめきを与えてくれたことになります.*1

上の図のように,mを大きくしていくと,分母は1から順に素因数2を取り込んでいき,分子は2015から下がっていきながら素因数2を取り込んでいきます.一見,取り込み具合が違うように見えるのですが,実は途中まで(m=31まで)は,同じペースで取り込まれていきます.それゆえ,約分されて消えていくわけです.

ところが,m=32になったとき,分母は1~32の積ですが,分子は2015-32+1=1984から2015までの積となり,1984は64の倍数にもなっています.ここで分母と分子に「ズレ」が発生したことになります(2015/2/28:下の補足に,その様子を記しました).そのズレの原因は,先に挙げた2015~2047の部分だったわけです.というわけで,答えは32であることがわかりました.

 

感想

大手予備校さんの問題分析を見ると,「2進法を知らないと無理」のようなコメントもありました.確かに,バックボーンとしては知らないと難しいように思います.「31」と「32」からひらめきを得たのも,まさに2進法からです.先に書いた2015~2047に含まれる2^nの倍数を探すところも,2進法で考えれば

 11111(2)=31(10)*2

とすぐに求められることもわかります.

そしてこの問題,2015年だから出したというよりも,2015年まで待っていたのでは?という気がしてなりません.なにせ,2015(10)=11111011111(2)ですからね.

メモと言いながらわざわざ図を描いていますが,わたしの中では何かと図示(グラフ化)できないかをよく考えています.仕事でも,文字化するよりも図示することで考えていることが多いです.大きな数を扱うような整数問題の場合であれば,その構造を理解するために,倍数などの「分布」を考えて図を用いるのは有効だと思います.*3

まあ,ここまでで35分かかっているわけで,これから解答をまとめて記述することを考えると,この問題だけで1時間ぐらいはかかってしまうことになります.もう受験するわけではないので,じっくり解ければいいかって本人は納得してます(笑).

 

補足(2015/2/28)

素因数2の分布をもう少し具体的に図示したものを出しておきます.点1つが素因数2 1つを表しています.たとえば,m=16のとき,点は縦に4つ並んでおり2^4であることを示しています.

こうやって描くと,「2の倍数が2つ集まって,4の倍数パック(かたまり)」ができ,「4の倍数パックが2つ集まって,8の倍数パック」ができ・・・というように,パターンの繰り返しになって,分布が現れる様子が見えるかと思います.*4

f:id:miwotukusi:20150504150438p:plain

すると,赤い点(64=2^6)の素因数1つがあまることが見えてきます.

また,この分布の様子から,{}_{2047} C_mは,mの値によらず必ず奇数になることもわかります.(ずっと約分されていくから)

*1:2015/2/28追記:直接答えを与えてくれたというよりは,補足に描いたような「パターン」があることに気づかせてくれたという方が正しいです.そういう意味では,2015という数字自体がパターンへのヒントになっている感じですね

*2:2進法表記を(2),10進法表記を(10)と表すことにします.

*3:今回挙げている図は,ほんとうにざっくりとしたイメージ図なので,あまり参考にしない方がいいのかもしれません.ただ,こういうイメージを持てると全体像から理解できるのではないかと思います.

*4:このパターンに対するイメージは,わたしの頭の中では「フラクタル図形(自己相似形)」とかぶっています.2015/5/4:図を描きなおしました