【超難問】大学"院"入試過去問 京大院の整数問題
↓ここからカテゴリー別に記事を見ることができます。↓
大学院入試の過去問を眺めていたら、たまたま運よく高校生でも解ける(ここでの解けるは、問題文の意味を理解でき、そして高校までの知識のみで答えを出せるという意味で、簡単に解けるとは言ってません*1 )問題を見つけたので、記事にしようと思います。問題文自体は簡潔で簡単ですが、きっちりと解答を書こうとするとかなり長くなる、そんな問題です。
問題
1以上3500以下の整数 のうち、 が3500で割り切れるものの個数を求めよ。
方針
とりあえず と因数分解できるので、 にそれぞれ の素因数をどう"振り分ける"かを考えて候補を絞っていきます。個数を聞いていますが、ここでは全てちゃんと値を求めようと思います。
それだけではまだ候補が多すぎるので、 の偶奇などにも注目していきます。今回の解答では高校で発展として扱われる" mod " を使います。modの扱い方や、modの方程式の解き方を知っていれば、解答は十分理解できると思います。
解答①
とりあえずプログラムを組んでそれに解かせてみました。
どうやら9個あるそうです。
各行の左には該当するの値、その右にはそのときのの値が表示されていて、一番下の行で個数がでています。
解答②
である。また、 である。
が偶数のとき、 は偶数だから は奇数である。
が奇数のとき、 は奇数だから は偶数である。
よって、 と の偶奇は異なる。...①
以上から、 がいかなる整数のときも、 は5の倍数ではない。よって、求める は少なくとも の倍数である。...②
(i) が偶数のとき
①より は奇数、つまり素因数2をもたない。これと②から、 を整数として、 と書ける。ただし、 は1以上3500以下だから、 は1以上7以下である。 が3500の倍数になるのは、
(i-1) が7の倍数となる または (i-2) が7の倍数となる
ときである。
(i-1)
が7の倍数となるのは、 が7の倍数となるときのみで、 は3500以下より、 のときの のみ。
(i-2)
であり、 を解くと、
である。 は1以上7以下だから、当てはまるのは、 のとき、すなわち
のときである。
(ii) が奇数のとき
①と②より、 と の値としてとりえるのは、
(ii-1) が の倍数かつ が の倍数となる または (ii-2) が の倍数かつ が の倍数となる
ときである。
(ii-1)
を奇数として とすると、 は3500以下より、
のとき、 で、 より より、 は4の倍数である。
のとき、 で、 より より、 は4の倍数である。
以上より、 は題意を満たす。
(ii-2)
を整数として、 と書ける。ただし、 は1以上3500以下だから、2n+1は1以上27以下である。
このとき、 だから、 より、 は常に4の倍数。よって、 が7の倍となるnを考えればよい。
より、だから、
を解く。4と7は互いに素だから、
これを解くと、
よって、
すなわち
以上より、求める は、
の9つ
コメント
解答が長い。
が5の倍数とならないことに気づけばせいぜい4つの場合を調べるだけだと分かるので解答が書けますが、これに気づかないと素因数の振り分けの候補が膨れ上がって大変です。
大学院入試は大学で習う知識を使わないと解けない問題ばかりで、今回の問題以外に、高校までの知識で解ける問題は一つも見つけられませんでした。院試は難しい。
*1:私がずっとやってる中学生でも解けるシリーズもそうですが