トップ› 東京大学› 2015年› 理系第5問

東京大学 2015年理系第5問解説

方針・初手

組合せの数 ${}_{n}\mathrm{C}_{m}$ がもつ素因数の個数を調べる問題である。直接階乗の計算を行うことは不可能なので、以下のいずれかのアプローチをとる。

隣り合う項の比を利用する ${}_{n}\mathrm{C}_{m}$ と ${}_{n}\mathrm{C}_{m-1}$ の間に成り立つ漸化式を利用し、素因数 $2$ の個数がいつ増加するかを順に追っていく。
階乗の素因数の個数に関する定理（ルジャンドルの定理）を利用する $N!$ に含まれる素因数 $p$ の個数を求める公式を利用し、さらに $2$ 進数表示と結びつけて繰り上がりの回数を考える（Kummerの定理の背景）。

ここでは、両方のアプローチを解法として提示する。

解法1

組合せの定義より、${}_{2015}\mathrm{C}_{m}$ を次のように変形する。

$$ {}_{2015}\mathrm{C}_{m} = \frac{2015!}{m!(2015-m)!} = \frac{2016-m}{m} \cdot \frac{2015!}{(m-1)!(2016-m)!} $$

すなわち、次の漸化式が成り立つ。

$$ {}_{2015}\mathrm{C}_{m} = \frac{2016-m}{m} {}_{2015}\mathrm{C}_{m-1} $$

任意の非零有理数 $x$ に対して、$x$ を素因数分解（分母と分子それぞれ）したときの素因数 $2$ の指数を $v_2(x)$ と表すことにする。上の漸化式より、次が成り立つ。

$$ v_2({}_{2015}\mathrm{C}_{m}) = v_2(2016-m) - v_2(m) + v_2({}_{2015}\mathrm{C}_{m-1}) $$

$2016$ を素因数分解すると、$2016 = 32 \times 63 = 2^5 \times 63$ である。

ここで、$1 \le m \le 31$ の範囲の整数 $m$ について考える。 $m$ は $2^5$ の倍数ではないため、$m = 2^k \cdot q$（$q$ は奇数、$0 \le k \le 4$）とおくことができる。このとき、$2016 - m$ は次のように計算できる。

$$ 2016 - m = 2^5 \times 63 - 2^k \cdot q = 2^k (2^{5-k} \times 63 - q) $$

$k \le 4$ より $5-k \ge 1$ であるから、$2^{5-k}$ は偶数である。したがって、$2^{5-k} \times 63$ は偶数であり、奇数 $q$ を引いた $2^{5-k} \times 63 - q$ は奇数となる。よって、$v_2(2016-m) = k$ となるため、次が成り立つ。

$$ v_2(2016-m) = v_2(m) $$

これより、$1 \le m \le 31$ のとき $v_2(2016-m) - v_2(m) = 0$ となり、次が言える。

$$ v_2({}_{2015}\mathrm{C}_{m}) = v_2({}_{2015}\mathrm{C}_{m-1}) $$

$m=1$ のとき、${}_{2015}\mathrm{C}_{1} = 2015$ は奇数であるから $v_2({}_{2015}\mathrm{C}_{1}) = 0$ である。したがって、帰納的に $m=1, 2, \dots, 31$ のすべてにおいて $v_2({}_{2015}\mathrm{C}_{m}) = 0$、すなわち奇数となる。

次に、$m=32$ のときを考える。

$$ 2016 - 32 = 1984 = 32 \times 62 = 2^6 \times 31 $$

これより、$v_2(2016-32) = 6$ である。一方、$v_2(32) = 5$ であるから、次のように計算できる。

$$ v_2({}_{2015}\mathrm{C}_{32}) = v_2(2016-32) - v_2(32) + v_2({}_{2015}\mathrm{C}_{31}) = 6 - 5 + 0 = 1 $$

したがって、${}_{2015}\mathrm{C}_{32}$ は素因数 $2$ をちょうど $1$ つ持つ偶数である。以上より、${}_{2015}\mathrm{C}_{m}$ が偶数となる最小の $m$ は $32$ である。

解法2

自然数 $N$ の階乗 $N!$ に含まれる素因数 $2$ の個数を $f(N)$ とおく。ルジャンドルの定理より、次が成り立つ。

$$ f(N) = \sum_{k=1}^{\infty} \left\lfloor \frac{N}{2^k} \right\rfloor $$

$N$ の $2$ 進数表示における $1$ の個数を $S_2(N)$ とすると、$f(N) = N - S_2(N)$ となることが知られている。 ${}_{2015}\mathrm{C}_{m}$ がもつ素因数 $2$ の個数を $V$ とすると、次のように表せる。

$$ V = f(2015) - f(m) - f(2015-m) $$

$$ V = (2015 - S_2(2015)) - (m - S_2(m)) - (2015-m - S_2(2015-m)) = S_2(m) + S_2(2015-m) - S_2(2015) $$

$m$ と $2015-m$ を $2$ 進法で足し算して $2015$ を得る過程を考える。一般に、$2$ つの数を $2$ 進法で足すとき、ある位で繰り上がりが $1$ 回発生するごとに、計算後の $1$ の個数は $1$ つ減る。したがって、$S_2(m) + S_2(2015-m) - S_2(2015)$ は、この足し算において発生する「繰り上がりの総回数」に等しい。 ${}_{2015}\mathrm{C}_{m}$ が偶数になる（$V \ge 1$ となる）ことは、この足し算で繰り上がりが少なくとも $1$ 回発生することと同値である。

$2015$ を $2$ 進数で表す。$2015 = 2048 - 32 - 1 = 2^{11} - 2^5 - 2^0$ より、

$$ 2015 = 11111011111_{(2)} $$

である。下から $6$ 桁目（$2^5$ の位）のみが $0$ であり、それ以外の $10$ 個の位はすべて $1$ である。

$1 \le m \le 31$ のとき、$m < 2^5$ であるため、$m$ の $2$ 進数表示において $1$ となり得る位は $2^0, 2^1, 2^2, 2^3, 2^4$ のいずれかのみである。和である $2015$ のこれらの位はすべて $1$ であるため、$2015-m$ との足し算においてこれらの位で繰り上がりが発生することはあり得ない。したがって、繰り上がり回数は $0$ 回となり、$V=0$（奇数）である。

一方、$m=32$ のとき、$m = 100000_{(2)}$ である。 $2015 - 32 = 1983 = 11110111111_{(2)}$ となり、これらを足し合わせると $2^5$ の位において $1+1$ となり、初めて繰り上がりが発生する。したがって、繰り上がり回数は $1$ 回となり、$V=1$（偶数）である。以上より、最小の $m$ は $32$ である。

解説

二項係数 ${}_{n}\mathrm{C}_{m}$ の偶奇や、特定の素数で何回割り切れるかを問う問題は、整数問題における典型テーマの一つである。解法1のように、${}_{n}\mathrm{C}_{m} = \frac{n-m+1}{m} {}_{n}\mathrm{C}_{m-1}$ という漸化式を利用して素因数の増減を調べる方法は、前提知識をあまり必要とせず、論理を正確に積み上げやすいため試験本番で有効である。

解法2は「Kummerの定理（クンマーの定理）」の背景となる考え方を用いている。「二項係数 ${}_{n}\mathrm{C}_{m}$ が素数 $p$ で割り切れる回数は、$m$ と $n-m$ を $p$ 進法で足し算したときの繰り上がりの回数に等しい」という事実を知っていると、本問は $2015$ を $2$ 進数に直すだけで見通しが立つ。