【超難問】大学"院"入試過去問 京大院の整数問題
大学院入試の過去問を眺めていたら、たまたま運よく高校生でも解ける(ここでの解けるは、問題文の意味を理解でき、そして高校までの知識のみで答えを出せるという意味で、簡単に解けるとは言ってません*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:私がずっとやってる中学生でも解けるシリーズもそうですが
中学生でも解ける大学入試数学56★★ 2019年静岡大
問題を少し変えています。
問題
★★
3桁の自然数の百の位の数をa、十の位の数をb、一の位の数をcとする。
(1) 10a+b-2cが7の倍数ならばもとの自然数は7の倍数であることを示せ。
(2) a≠b, a=cであるとき、もとの自然数が7の倍数となるようなaとbの組は何通りあるか。
ヒント、着眼点
倍数判定法の証明に関する問題です。
3の倍数の判定法はよく知られていて、使う機会は多いです。
Aの各位の数の和が3の倍数ならば、Aは3の倍数
例
123456は1+2+3+4+5+6=21より3の倍数。実際、123456=3×41152
この証明を見てみましょう。今回の問題にも役立つはずです。ここではAが3桁の数である場合を示します。
証明
Aの百の位の数をa、十の位の数をb、一の位の数をcとすると、
A=100a+10b+c
と表される。Aの各位の数の和が3の倍数だから、nを整数として
a+b+c=3n
と書ける。このとき
A=99a+9b+(a+b+c)=99a+9b+3n=3(33a+3b+n)
a,b,nは整数だから、3(33a+3b+n)は3の倍数である。よってAは3の倍数である。
Aの桁数が変わっても、同様に示すことができます。このように、「〇が3の倍数」とあれば、「nを整数として〇=3nと書ける」とするのが定石です。
この3の倍数判定法を証明が理解できたならば、9の倍数判定法の証明がかけるでしょう。
Aの各位の数の和が9の倍数ならば、Aは9の倍数
では、これらの証明のキーポイントを掴んで、今回の問題も考えてみましょう。ただ、ちょっとひねりをいれる必要があるかもしれません。
以下、解答
解答
(1) 解説参照
(2) 11通り
解説
(1)
3桁の自然数は100a+10b+cを書ける。
10a+b-2cが7の倍数なので、nを整数として
10a+b-2c=7n
と書ける。このとき
100a+10b+c
=(70a+7b+7c)+(30a+3b-6c)
=7(10a+b+c)+3(10a+b-2c)
=7(10a+b+c)+21n
=7(10a+b+c+3n)
a,b,c,nは整数だから7(10a+b+c+3n)は7の倍数である。よってもとの自然数は7の倍数である。
100a+10b+c=(90a+9b+3c)+(10a+b-2c)としてもうまくいかず、7の倍数を作るために上のような一工夫をするのが少し思いつきにくいでしょうか。
(2)
(1)より、10a+b-2cが7の倍数となることを考えればよい。a=cより、
10a+b-2c=8a+b=7a+(a+b)
7aは7の倍数より、これが7の倍数となるのはa+bが7の倍数となるときで、a+b=7,14となるときであり、
(a,b)=(1,6), (2,5), (3,4), (4,3), (5,2), (6,1), (7,0), (5,9), (6,8), (8,6), (9,5)
の11通り。
(a,b)=(0,7) は3桁の自然数でなくなることに注意。
(a,b)=(7,7) はa≠bに反することに注意。
前回
中学生でも解ける大学入試数学55 2002年お茶女大 - 日比谷高校のススメ
次回
written by k
中学生でも解ける大学入試数学55★ 2002年お茶女大
問題
★
1から2002までの自然数のうち、45で割ったときの余りが45で割ったときの商より小さいものはいくつあるか。
ヒント、着眼点
「何通りあるか」問題は、計算でパパっと求められるものもあれば、根気よく順に数えて求めるものもあります。今回はうまく順に数えればよいでしょう。
このような問題で、うまく数えることができる、というのはいわゆるセンスがしばしば要求されます。この問題を通して、センスを磨きましょう。
以下、解答
解答
969個
解説
まず、該当する自然数はどのように現れるのかを把握しましょう。1から2002までの自然数を45で割ったときの商とあまりがどのように変化するかが分かれば、該当する自然数の現れ方も分かります。
ここでは、うまく数えるコツとして、周期性に注目した場合分けをします。1から順に自然数を45で割ると、余りが(0~44)が繰り返し現れます。この長さ45の周期を利用するために、商で場合分けをしてみましょう。
①1から44
商0 あまり1~44
該当なし
②45から89
商1 あまり0~44
該当1つ(45÷45=1...0)
③90から134
商2 あまり0~44
該当2つ(90÷45=2...0, 91÷45=2...1)
④135から179
商3 あまり0~44
該当3つ(135÷45=3...0, 136÷45=3...1, 137÷45=3...2)
ここまでやると、該当するものが、0つ、1つ、2つ、3つ、4つ、...となっていくことが分かります。あとは、場合分けがどこで終わるか、最後を確認すればよいでしょう。
2002÷45=44...22、45×44=1980であるから、
〇1935~1979
商43 あまり0~44
該当43つ(あまり0~42)
〇1980~2002
商44 あまり0~22
該当23つ
よって、答えは、
(1+2+3+...+43)+23=969
補足
このように、闇雲に探すのではなく、うまーく数える。これはある程度の訓練なしでは身に付きません。答えがでればオッケー、という楽観的な思考をせず、よりよい解法、より効率的な見通しの良い解法はないか、と貪欲になりましょう。
(当然私の解法が一番エレガントであるとは限りません。このブログは考えるヒントとしてご活用ください。)
前回
中学生でも解ける大学入試数学54 1999年大阪大 - 日比谷高校のススメ
次回
中学生でも解ける大学入試数学56 2019年静岡大 - 日比谷高校のススメ
written by k