日比谷高校のススメ

日比谷高校出身者たちが日比谷高校の紹介や、勉強に関する様々なことを語ります。

【超難問】大学"院"入試過去問 京大院の整数問題

↓ここからカテゴリー別に記事を見ることができます。↓

大学院入試の過去問を眺めていたら、たまたま運よく高校生でも解ける(ここでの解けるは、問題文の意味を理解でき、そして高校までの知識のみで答えを出せるという意味で、簡単に解けるとは言ってません*1 )問題を見つけたので、記事にしようと思います。問題文自体は簡潔で簡単ですが、きっちりと解答を書こうとするとかなり長くなる、そんな問題です。

 

問題

1以上3500以下の整数x のうち、x^3+3x が3500で割り切れるものの個数を求めよ。

 

 

 

方針

とりあえずx^3+3x=x(x^2+3)因数分解できるので、x,\ (x^2+3) にそれぞれ3500=2^2\times5^3\times7 の素因数をどう"振り分ける"かを考えて候補を絞っていきます。個数を聞いていますが、ここでは全てちゃんと値を求めようと思います。

それだけではまだ候補が多すぎるので、x,\ (x^2+3) の偶奇などにも注目していきます。今回の解答では高校で発展として扱われる" mod " を使います。modの扱い方や、modの方程式の解き方を知っていれば、解答は十分理解できると思います。

 

 

解答①

とりあえずプログラムを組んでそれに解かせてみました。

f:id:hby:20190723210121j:plain

どうやら9個あるそうです。

各行の左には該当するxの値、その右にはそのときのx^3+3xの値が表示されていて、一番下の行で個数がでています。

 

 

解答②

x^3+3x=x(x^2+3) である。また、3500=2^2\times5^3\times7 である。

x が偶数のとき、x^2 は偶数だからx^2+3 は奇数である。

x が奇数のとき、x^2 は奇数だからx^2+3 は偶数である。

よって、xx^2+3 の偶奇は異なる。...

x\equiv 0 \pmod{5}\ のとき\ x^2+3\equiv 3  \pmod{5}\\x\equiv \pm1\pmod{5}\ のとき\ x^2+3\equiv 4  \pmod{5}\\x\equiv \pm2\pmod{5}\ のとき\ x^2+3\equiv 7\equiv 2\pmod{5}

以上から、x がいかなる整数のときも、x^2+3 は5の倍数ではない。よって、求めるx は少なくとも5^3=125 の倍数である。...

 

(i) x が偶数のとき

①よりx^2+3 は奇数、つまり素因数2をもたない。これと②から、n を整数として、x=2^2\times5^3\times n=500n と書ける。ただし、x は1以上3500以下だから、n は1以上7以下であるx^3+3x が3500の倍数になるのは、

(i-1) x が7の倍数となる または (i-2) x^2+3 が7の倍数となる

ときである。

 

(i-1)

x が7の倍数となるのは、n が7の倍数となるときのみで、x は3500以下より、n=7 のときのx=\underline{3500} のみ。

 

(i-2)

x^2+3\equiv (500n)^2+3\equiv250000n^2+3\equiv2n^2+3 \pmod{7}

であり、2n^2+3\equiv0\pmod{7} を解くと、

n\equiv\pm3\pmod{7}

である。n は1以上7以下だから、当てはまるのは、n=3,\ 4 のとき、すなわち

x=\underline{1500,\ 2000} のときである。

 

(ii) x が奇数のとき

①と②より、x^2x^2+3 の値としてとりえるのは、

(ii-1) x5^3\times7=875 の倍数かつx^2+32^2=4 の倍数となる または (ii-2) x5^3=125 の倍数かつx^2+32^2\times7=28 の倍数となる

ときである。

 

(ii-1)

m を奇数としてx=875m とすると、x は3500以下より、m=1,\ 3

m=1 のとき、x=875 で、x\equiv3\pmod{4} よりx^2+3\equiv9+3\equiv0\pmod{4} より、x^2+3 は4の倍数である。

m=3 のとき、x=2625 で、x\equiv1\pmod{4} よりx^2+3\equiv1+3\equiv0\pmod{4} より、x^2+3 は4の倍数である。

以上より、x=\underline{875,\ 2625} は題意を満たす。

 

(ii-2)

n を整数として、x=125(2n+1) と書ける。ただし、x は1以上3500以下だから、2n+1は1以上27以下である。

このとき、x\equiv (2n+1) \pmod{4} だから、x^2+3\equiv (2n+1)^2+3\equiv4n^2+4n+4\equiv0 \pmod{4} より、x^2+3 は常に4の倍数。よって、x^2+3 が7の倍となるnを考えればよい。

x\equiv -(2n+1) \pmod{7} より、x^2+3\equiv4n^2+4n+4 \pmod{7}だから、

4n^2+4n+4\equiv0 \pmod{7}

を解く。4と7は互いに素だから、

n^2+n+1\equiv0 \pmod{7}

これを解くと、

n\equiv2,\ -3\pmod{7}

よって、

2n+1=5,\ 9,\ 19,\ 23すなわち

x=\underline{625,\ 1125,\ 2375,\ 2875}

 

以上より、求めるx は、

x=\underline{625,\ 875,\ 1125,\ 1500,\ 2000,\ 2375,\ 2625,\ 2875,\ 3500}

9つ

 

 

 

コメント

解答が長い。

x^2+3 が5の倍数とならないことに気づけばせいぜい4つの場合を調べるだけだと分かるので解答が書けますが、これに気づかないと素因数の振り分けの候補が膨れ上がって大変です。

大学院入試は大学で習う知識を使わないと解けない問題ばかりで、今回の問題以外に、高校までの知識で解ける問題は一つも見つけられませんでした。院試は難しい。

 

 

 

written by k

*1:私がずっとやってる中学生でも解けるシリーズもそうですが

Copyright © 2017 日比谷高校のススメ All rights reserved.