東大 2009年度理系数学第1問｜問題・解答・解説

方針

(1) (2)は文系第2問と同じ構造で，素数の場合は $r_{m} C_{r} = m_{m - 1} C_{r - 1}$ ，帰納法では二項定理を使う。(3)では $d_{m}$ に含まれ得る素因数を調べる。奇素数 $p$ については $m = p^{q} v$ と書き，特定の二項係数 $_{m} C_{p^{q}}$ が $p$ で割り切れないことを，分子と分母に現れる $p$ の個数を比較して示す。さらに2について， $m = 2^{q} v$ で $v > 1$ なら奇数の二項係数を作り， $m = 2^{q}$ なら4で割り切れない二項係数を作る。

解答

(1)

$m$ を素数とする。 $1 ≦ r ≦ m - 1$ では $r$ と $m$ は互いに素である。二項係数には $r_{m} C_{r} = m_{m - 1} C_{r - 1}$ という関係があるので， $r_{m} C_{r}$ は $m$ で割り切れる。 $r$ と $m$ が互いに素であるから， $_{m} C_{r}$ が $m$ で割り切れる。

よって $_{m} C_{1},_{m} C_{2}, \dots,_{m} C_{m - 1}$ はすべて $m$ の倍数である。一方で $_{m} C_{1} = m$ であるから，これらの最大公約数は $m$ を超えられない。したがって $d_{m} = m$ である。

(2)

$k = 1$ のときは $1^{m} - 1 = 0$ なので $d_{m}$ で割り切れる。

ある自然数 $k$ について $k^{m} - k$ が $d_{m}$ で割り切れると仮定する。二項定理より $(k + 1)^{m} = k^{m} +_{m} C_{1} k +_{m} C_{2} k^{2} + \dots +_{m} C_{m - 1} k^{m - 1} + 1$ であるから $\begin{aligned} (k + 1)^{m} - (k + 1) & = k^{m} - k +_{m} C_{1} k +_{m} C_{2} k^{2} + \dots +_{m} C_{m - 1} k^{m - 1} \end{aligned}$ である。右辺第1項は帰納法の仮定により $d_{m}$ で割り切れる。また， $d_{m}$ の定義により各 $_{m} C_{r}$ は $d_{m}$ で割り切れる。したがって右辺全体が $d_{m}$ で割り切れる。

ゆえに $(k + 1)^{m} - (k + 1)$ も $d_{m}$ で割り切れる。数学的帰納法により，すべての自然数 $k$ に対して $k^{m} - k は d_{m} で割り切れる$ ことが成り立つ。

(3)

$m$ を偶数とする。まず， $d_{m}$ が奇素数を約数にもたないことを示す。 $p$ を $m$ を割る奇素数とし， $m$ を割る $p$ の最大の累乗を $p^{q}$ とする。すなわち $m = p^{q} v$ と書き， $v$ は $p$ で割り切れないとする。 $m$ は偶数で $p$ は奇素数なので， $p^{q} < m$ であり， $_{m} C_{p^{q}}$ は $d_{m}$ を考える並びの中に含まれる。

この二項係数を $_{m} C_{p^{q}} = \frac{m (m - 1) (m - 2) \dots (m - p^{q} + 1)}{p^{q} (p^{q} - 1) (p^{q} - 2) \dots 1}$ と書き，先頭の $m / p^{q} = v$ を外すと $_{m} C_{p^{q}} = v \cdot \frac{(m - 1) (m - 2) \dots (m - p^{q} + 1)}{(p^{q} - 1) (p^{q} - 2) \dots 1}$ である。

$1 ≦ j ≦ p^{q} - 1$ について， $j$ が $p$ でちょうど $e$ 回割り切れるとする。このとき $e < q$ であり， $m - j = p^{q} v - j$ も $p$ でちょうど $e$ 回割り切れる。したがって積 $(m - 1) (m - 2) \dots (m - p^{q} + 1)$ に含まれる $p$ の個数は， $(p^{q} - 1) (p^{q} - 2) \dots 1$ に含まれる $p$ の個数と等しい。さらに $v$ は $p$ で割り切れない。よって $_{m} C_{p^{q}}$ は $p$ で割り切れない。したがって $d_{m}$ は奇素数を約数にもたない。

次に2の因数を調べる。 $m = 2^{q} v$ と書き， $v$ を奇数とする。 $v > 1$ の場合， $_{m} C_{2^{q}}$ を考えると，同様に $_{m} C_{2^{q}} = v \cdot \frac{(m - 1) (m - 2) \dots (m - 2^{q} + 1)}{(2^{q} - 1) (2^{q} - 2) \dots 1}$ である。 $1 ≦ j ≦ 2^{q} - 1$ について $m - j$ と $j$ に含まれる2の個数は等しく， $v$ は奇数である。したがって $_{m} C_{2^{q}}$ は奇数である。この場合， $d_{m}$ は奇素数も2も約数にもたないので $d_{m} = 1$ である。

残るのは $m = 2^{q}$ の場合である。このとき $m$ は偶数なので $q ≧ 1$ である。 $m = 2$ なら並びは $_{2} C_{1} = 2$ だけなので $d_{2} = 2$ である。以下 $m ≧ 4$ とする。 $_{m} C_{m / 2}$ を考えると $_{m} C_{m / 2} = 2 \cdot \frac{(m - 1) (m - 2) \dots (m / 2 + 1)}{(m / 2 - 1) (m / 2 - 2) \dots 1}$ である。ここでも $1 ≦ j ≦ m / 2 - 1$ について $m - j$ と $j$ に含まれる2の個数は等しいので，分数部分は奇数である。したがって $_{m} C_{m / 2}$ は2で割り切れるが4では割り切れない。

以上より， $m$ が偶数のとき $d_{m}$ は奇素数を約数にもたず，また4でも割り切れない。したがって $d_{m} は 1 または 2$ である。

総評

難度7、計算量6。目安時間は25分前後で，(3)の素因数評価が山である。(1)(2)は文系第2問と共通なので，ここを短時間で確実に処理し，(3)に時間を残したい。奇素数 $p$ を消すには「 $d_{m}$ がすべての二項係数を割る」ことの逆を使い， $p$ で割り切れない二項係数を1つ作ればよい。2についても， $m$ が2の累乗でない場合と2の累乗の場合を分ける。典型的なミスは， $p^{q}$ が $m$ を割る最大の累乗であることを使わず，分子分母の素因数の個数比較を曖昧にすることである。

出典: 東京大学 2009年度前期数学（大学公式の問題PDF）。問題文はHTML表示のために再入力・数式組版しています。

東京大学 2009年度 前期日程 第2次学力試験理系数学 第1問

方針

解答

総評

東京大学 2009年度前期日程第2次学力試験理系数学第1問