皆さんこんにちは。東進衛星予備校 金沢南校の北川と申します。
昨日、そして本日にかけて、全国の国公立大学にて二次試験が実施されました。
戦い抜いた受験生の皆さま、お疲れ様でした！ 素敵な春が来ることを願っております！
今回は今年の東大の問題から1問を抜粋し、ポイントや面白さを解説いたします。どうか最後までお付き合いいただけますと幸いです。
目次
1.2026東大理系第6問 ～約数とmod3～
2.考察のポイント
3.解答
4.終わりに
5.おまけ
それでは、今回扱う問題はこちら！
\(n\)を正の整数とする。\(n\)の正の約数のうち、3で割って1余るものの個数を\(f(n)\),3で割って2余るものの個数を\(g(n)\)とする。
(1) \(f(2800)\),\(g(2800)\) を求めよ。
(2) \(f(n) \geq g(n)\) を示せ。
(3) \(g(n) = 15\) であるとき,\(f(n)\) がとりうる値を求めよ。
(東京大学 入学者選抜2次試験 数学(理科)の第6問より引用・(2)の不等号は正しくは下部が「=」)
問題文が短く、見た目は「普通の整数問題」といったところでしょうか。
しかし、そこはさすが東大。問題になじみがない題材を持ってきています。多くの受験生にとって「ある数の約数が3で割って1余るか2余るか」なんて、興味の対象に無いことの方が多いでしょう。
問題の意味は分かる、題意もシンプル。でも、最初の一手を打つために必要な考察を得ることすら難しい。今年の第6問は、そういう問題といえそうです。
とりあえず(1)を考えてみましょう。\(2800=2^{4}・5^{2}・7\)ですから、約数の候補は\(5×3×2=30\)個あります。
素因数に3はありませんから、いずれの約数も3では割り切れないはずです。
つまり、30個の約数を全部列挙して、3で割った余りで分ける……という方法でも、とりあえず(1)は乗り切れます。
ですが、それでは(2)に繋がりません。もう少し考えてみましょう。
例えば、3で割って2余る数と、2余る数同士を掛け算すると、その結果はどうなるでしょうか？ 計算して確かめると、3で割って1余る数になります。
すると、ある\(n\)の約数について、3で割って2余る素因数が偶数個あるときには、その約数は3で割って1余ることになります。奇数個なら、2余ることになります。
今回は3で割って2余る素因数は2が4個、5が2個あるので、そこから奇数個の素因数を選ぶ方法を数え上げてみると、これは全部で7通りあります。
7通りに対して、7を掛けるか掛けないかの2通りが存在するので、\(g(2800)=14\)となります。同様に、\(f(2800)=16\)も分かります。
ちなみに、素因数を3で割った余りについて考察する問題としては、以前にこちらの問題を取り上げました。
この問題での考察を少し深めると、今回の問題もピンと来やすくなります。未知の問題に対しても、やはり経験がものを言うのかもしれません。
さて、上記の考察により、\(n\)を素因数分解したときの3で割って2余る素因数の個数が鍵を持ちそうなことが分かります。
どうやって考えるか、実はこの先の一歩を踏み出すのが非常に難しい。
私はこのような場合、図表を書いて考えることも多いです。例えば、今回であればこんな表を書きました。
| \(2^{0}・5^{0}\) | \(2^{1}・5^{0}\) | \(2^{2}・5^{0}\) | \(2^{3}・5^{0}\) | \(2^{4}・5^{0}\) |
| \(2^{0}・5^{1}\) | \(2^{1}・5^{1}\) | \(2^{2}・5^{1}\) | \(2^{3}・5^{1}\) | \(2^{4}・5^{1}\) |
| \(2^{0}・5^{2}\) | \(2^{1}・5^{2}\) | \(2^{2}・5^{2}\) | \(2^{3}・5^{2}\) | \(2^{4}・5^{2}\) |
これは、先ほどの2800の約数のうち、3で割って2余る素因数のみを抜き出し、そのいくつかの積によって得られる\(n\)の約数を表として書いたものです。
黒く塗った数は3で割って1余るもの、赤く塗ったものは3で割って2余るものです。こうしてみると、表上の辺で隣り合っている数同士は必ず違う色で塗られていることがよく分かります。
まるでチェス盤を市松模様に塗り分けたような、そんな感じがします。
市松模様での塗り分けといえば、偶奇性を連想します。今回は、表は奇数×奇数マスの長方形型ですから、市松模様同士に塗り分けると黒マスの方が必ず1つだけ多くなります。
あとはこれの、末尾に7をかけたバージョンも色の塗り分けは同じになりますから、最終的に黒マスの方が2つ多くなるのは道理だったわけです。
2800の場合は3で割って2余る素因数は2つしかありませんでしたが、個数が増えるとその分、このチェス盤の「次元」が上がっていきます。
つまり、この問題は多次元のマス目を市松模様に塗り分けることと同様に考えることができるわけですね。
5次元チェスや4Dゴルフは聞いたことがありますが、あいにく4次元以上でチェスをしたことはないので、自分で言った割にピンときてはいませんが……。
ですが、「市松模様に塗り分ける」と考えれば、例えばマス目の個数が偶数であれば\(f(n)\)と\(g(n)\)が等しくなることはすぐにわかります。
また、奇数の場合もそれほど大きな差がつかないことが予測されるので、ここを軸に掘り下げていきましょう。
高次元の場合を考えるのも、またチェス盤を塗り分けるという表現を本番答案で使うのも難しいですが、低次元の場合で実験すると色々な示唆が得られます。
今回なら、小さな場合の具体的な証明手順から、数学的帰納法を思いつけるかどうかもポイントでしたね。
※以下の解答は当社が独自に作成したものであり、東京大学の公式発表とは一切の関係を持ちません。
以下、単に「約数」と言ったら「正の約数」のみを指すものとする。
各問題で使用するために、いくつかの記号の使い方を説明し、補題を証明する。
記号の使い方
正の整数\(n\)について、「\(n\)を割り切る3で割って2余る素数」の個数が\(m\)個、「\(n\)を割り切る3で割って1余る素数」の個数が\(k\)個であるとする。
また、「\(n\)を割り切る3で割って2余る素数」のみの積で表せる\(n\)の約数の個数を\(R_{n}\)個、「\(n\)を割り切る3で割って1余る素数」のみの積で表せる\(n\)の約数の個数を\(S_{n}\)個とする。
特に、\(n\)の値にかかわらず\(m=0\)ならば、\(R_{n}=1\)であることに留意する。
補題
\(R_{n}\)が偶数の時、\(f(n)=g(n)=\frac{1}{2}R_{n}S_{n}\)である。
\(R_{n}\)が奇数の時、\(f(n)=\frac{1}{2}(R_{n} + 1)S_{n}\),\(g(n)=\frac{1}{2}(R_{n} – 1)S_{n}\)である。
補題の証明
\(m\)に関する数学的帰納法で証明する。
\(m=0\)の時、必ず\(R_{n}=1\)である。また、\(n\)が持つ素因数は3か、もしくは3で割って1余る素因数しかない。
\(n\)の約数であって素因数3を含むものは3で割っても余りが出ないから、3で割って1余る素因数にのみ注目すればよい。
3で割って1余る素因数のみを掛け合わせて作られた\(n\)の約数は\(S_{n}\)個あり、これらの約数はすべて3で割った余りが1になる。
よってこの時、\(f(n)=S_{n}\), \(g(n)=0\)であるから、\(m=0\)の時は条件を満たす。
\(m\)の時に成立していると仮定し、\(m+1\)の時を考える。
\(n\)の素因数のうち、3で割って2余るものを1つ選び\(p\)とする。\(n\)がちょうど\(p\)で\(r_{m+1}\)回割れるとする。この時、\(n’=\frac{n}{p^{r_{m+1}}}\)とする。\(n’\)は整数であり、かつ3で割って2余る素因数をちょうど\(m\)個だけ持つ。
(i)\(R_{n’}\)が偶数であるとき
帰納法の仮定から、\(f(n’)=g(n’)=\frac{1}{2}R_{n’}S_{n’}\)である。\(n’\)の定義より、\(S_{n’}=S_{n}\)である。
この時、\(n\)の約数であって3で割れないものは、\(n’\)の約数であって3で割れないものに\(p^{z}(0 \leq z \leq r_{m+1},zは整数)\)をかけたものに限られ、かつそれですべてを尽くす。
ここで、\(n’\)の約数であって3で割れないものを1つとり\(a\)とする。\(ap^{z}\)について、以下のようなことが言える。
・もし\(z\)が奇数であるとき、
→もし\(a\)を3で割って余りが1であるならば、\(ap^{z}\)は3で割った余りが2である。\(a\)として考えられるものは\(f(n’)\)個あるので、\(ap^{z}\)という形で書ける3で割って2余る\(n\)の約数も\(f(n’)\)個ある。
→もし\(a\)を3で割って余りが2であるならば、\(ap^{z}\)は3で割った余りが1である。上と同様に考えると、これは\(g(n’)\)個ある。
・もし\(z\)が偶数であるとき、
→もし\(a\)を3で割って余りが1であるならば、\(ap^{z}\)は3で割った余りが1である。上と同様に考えると、これは\(f(n’)\)個ある。
→もし\(a\)を3で割って余りが2であるならば、\(ap^{z}\)は3で割った余りが2である。上と同様に考えると、これは\(g(n’)\)個ある。
\(f(n’)=g(n’)\)であるから、各\(z(0 \leq z \leq r_{m+1})\)に対し、\(ap^{z}\)という形で書くことのできる3で割って1余る\(n\)の約数と、2余る\(n\)の約数は常に同数ずつある。つまり、全体としてみたときにも\(f(n)=g(n)\)となっている。
\(n\)の3で割りきれない約数の個数は全部で\(R_{n}S_{n}\)個だから、\(f(n)=g(n)=\frac{1}{2}R_{n}S_{n}\)である。
(ii)\(R_{n’}\)が奇数であるとき
帰納法の仮定から、\(f(n’)=\frac{1}{2}(R_{n’} + 1)S_{n’}\),\(g(n’)=\frac{1}{2}(R_{n’} – 1)S_{n’}\)である。\(n’\)の定義より、\(S_{n’}=S_{n}\)である。
(i)と同様に考えると、3で割って1余る約数の個数と、2余る約数の個数について、四角で囲った部分とまったく同じことが言える。
(ii-i) \(r_{m+1}\)が奇数であるとき
0以上\(\frac{r_{m+1}-1}{2}\)以下の整数\(q\)について、\(ap^{2q}\)と書ける3で割って1余る\(n\)の約数と、\(ap^{2q+1}\)と書ける3で割って1余る\(n\)の約数の個数は、上記の考察より\(f(n’)+g(n’)\)個である。
同様に、\(ap^{2q}\)と書ける3で割って2余る\(n\)の約数と、\(ap^{2q+1}\)と書ける3で割って2余る\(n\)の約数の個数も、やはり\(f(n’)+g(n’)\)個である。
よって、各\(q=0,1,…\frac{r_{m+1}-1}{2}\)に対し、3で割って1余る\(n\)の約数の個数と、3で割って2余る約数の個数は常に等しくなる。つまり、全体としても\(f(n)=g(n)\)となる。
あとは(i)と同様に考えると、\(f(n)=g(n)=\frac{1}{2}R_{n}S_{n}\)である。
(ii-ii) \(r_{m+1}\)が偶数であるとき
途中までは(ii-i)と同様に考えることができ、各\(q=0,1,…\frac{r_{m+1}-2}{2}\)に対し、3で割って1余る\(n\)の約数の個数と、3で割って2余る約数の個数は常に等しくなることが分かる。
あとは、\(ap^{r_{m+1}}\)という形で書ける約数の個数を考えればよいが、これは(ii)冒頭の考察より、3で割って1余るものが\(f(n’)\)個、2余るものが\(g(n’)\)個ある。
\(f(n’)-g(n’)=S_{n}\)なので、全体としても\(f(n)\)と\(g(n)\)は\(S_{n}\)個だけ差が出る。
3で割れない約数の全体数から\(f(n)+g(n)=R_{n}S_{n}\)であるから、差が\(S_{n}\)であることと合わせ、\(f(n)=\frac{1}{2}(R_{n} + 1)S_{n}\),\(g(n)=\frac{1}{2}(R_{n} – 1)S_{n}\)を得る。□
補題の証明は以上である。
以下、この補題を使って問題に解答していく。
(1) \(2800=2^{4}・5^{2}・7\)である。\(R_{2800}=15\)であり、\(S_{2800} = 2\)である。
補題より、\(f(2800)=\frac{1}{2}(15 + 1)・2=16\)であり、\(g(2800)=\frac{1}{2}(15 – 1)・2=14\)である。
(2) 補題より\(R_{n}\)が偶数のときは\(f(n)=g(n)\)であるし、奇数のときは\(f(n)>g(n)\)であるから、明らかである。
(3) \(R_{n}\)が偶数であるとき、\(f(n)=g(n)=15\)である。
\(R_{n}\)が奇数であるとき、補題により\(f(n)=\frac{1}{2}(R_{n} + 1)S_{n}\),\(g(n)=\frac{1}{2}(R_{n} – 1)S_{n}\)であり、\(g(n)=15\)であるから\(R_{n}S_{n} = 30 + S_{n}\)かつ\(f(n)=R_{n}S_{n} – 15\)が分かる。
明らかに\(S_{n}\)は30の約数でなければならず、かつ\(R_{n}\)は偶数であるので、この条件下では\(S_{n}=1,3,5,15\)のみに候補が限られる。
この時、\(f(n)=16,18,20,30\)である。
逆に、\(g(n)=15\)のとき、\(f(n)=15,16,18,20,30\)となるような\(n\)はそれぞれに存在するので、これが答えである。
今年の東大数学の問題はどの大問も非常に難しく、時間内にすべての問題はおろか、2問以上完答することすらも難しかったのではないかと想像します。
試験場の絶望的な様子が容易に目に浮かぶようです。ピークと思われた昨年をさらに上回る難易度に立ち向かった受験生各位に、敬意を表します。
あまりできなかったと感じる方も、どうか胸を張ってください。やり切ったその姿は、称えられて然るべきであると、少なくとも私は感じます。
今月の記事はここまで。来月もお楽しみに！
今回の問題について、補題が正しいであろうことを実際に例を挙げて計算してくれるプログラムを書いてみました。
# 約数を列挙する関数
def deviders(n):
res = []
for i in range(1, n + 1):
if i * i > n:
break
if n % i == 0:
res.append(i)
if i != n // i:
res.append(n // i)
res.sort()
return res
# 素因数分解する関数
def primefrac(n):
N = n
res = []
for i in range(2, n + 1):
if i * i > n:
break
if N % i == 0:
s = 0
while N % i == 0:
s += 1
N //= i
res.append([i, s])
if N != 1:
res.append([N, 1])
return res
# 問題文中のfとgの働きを同時に行う関数
def fg(n):
f = 0
g = 0
for d in deviders(n):
if d % 3 == 1:
f += 1
elif d % 3 == 2:
g += 1
return f, g
# ここからがコードの本体
M = int(input())
for n in range(1, M + 1):
# fはf(n)の値で、gはg(n)の値
f, g = fg(n)
# rはR_{n}の値で、sはS_{n}の値
P = primefrac(n)
r = 1
s = 1
for q in P:
if q[0] % 3 == 2:
r *= q[1] + 1
elif q[0] % 3 == 1:
s *= q[1] + 1
# r = R_{n}の偶奇によって分岐、補題の主張と合致していないもののみ弾く
if r % 2 == 0:
if f == g and f == r * s // 2:
pass
else:
print(f'Unmatched:{n}')
else:
if f == (r + 1) * s // 2 and g == (r - 1) * s // 2:
pass
else:
print(f'Unmatched:{n}')
そもそも証明できているので大丈夫だとは思いますが、M=100000として走らせても反例はなさそうでした。
【記事監修者】塾長 柳生 好春
1951年5月16日生まれ。石川県羽咋郡旧志雄町(現宝達志水町)出身。中央大学法学部法律学科卒業。 1986年、地元石川県で進学塾「東大セミナー」を設立。以来、38年間学習塾の運営に携わる。現在金沢市、野々市市、白山市に「東大セミナー」「東進衛星予備校」「進研ゼミ個別指導教室」を展開。 学習塾の運営を通じて自ら課題を発見し、自ら学ぶ「自修自得」の精神を持つ人材育成を行い、社会に貢献することを理念とする。
Copyright ©金沢市・野々市市・白山市の塾なら東大セミナー All Rights Reserved.