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

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

方針・初手

(1)は、二項係数の関係式 $n \cdot {}_m\mathrm{C}_{n} = m \cdot {}_{m-1}\mathrm{C}_{n-1}$ を利用し、両辺が持つ素因数2の個数に注目して証明する。

(2)は、(1)の結論を足がかりにする。パスカルの三角形における性質 ${}_{m}\mathrm{C}_{n} = {}_{m-1}\mathrm{C}_{n-1} + {}_{m-1}\mathrm{C}_{n}$ や、二項定理を用いた多項式 $(1+x)^m$ の展開式の係数を比較することで、すべての二項係数が奇数になるような $m$ の形を特定する。

解法1

(1)

二項係数の定義から導かれる以下の関係式を用いる。

$$ n \cdot {}_{m}\mathrm{C}_{n} = m \cdot {}_{m-1}\mathrm{C}_{n-1} $$

$m=2^k$（$k$ は自然数）のとき、この式は次のように書ける。

$$ n \cdot {}_{2^k}\mathrm{C}_{n} = 2^k \cdot {}_{2^k-1}\mathrm{C}_{n-1} $$

ここで、${}_{2^k-1}\mathrm{C}_{n-1}$ は整数であるから、右辺は $2^k$ の倍数である。すなわち、右辺は素因数2を少なくとも $k$ 個持つ。

左辺について考える。$n$ を素因数分解したときの2の指数を $p$ とすると、$n = 2^p \cdot q$（$p$ は非負整数、$q$ は奇数）とおける。条件より $0 < n < 2^k$ であるから、

$$ 2^p \leqq 2^p \cdot q < 2^k $$

となり、$p < k$ すなわち $p \leqq k-1$ が成り立つ。

つまり、$n$ は素因数2を高々 $k-1$ 個しか持たない。等式が成り立つためには、左辺の ${}_{2^k}\mathrm{C}_{n}$ が少なくとも1つの素因数2を持たなければならない。

したがって、$0 < n < 2^k$ を満たすすべての整数 $n$ について、${}_{2^k}\mathrm{C}_{n}$ は偶数である。（証明終）

(2)

任意の自然数 $m$ は、ある自然数 $k$ を用いて $2^{k-1} \leqq m < 2^k$ と表すことができる。この $m$ を以下の2つの場合に分けて考える。

(i)

$m = 2^k - 1$ の場合

二項係数の性質より、以下の式が成り立つ。

$$ {}_{2^k}\mathrm{C}_{n} = {}_{2^k-1}\mathrm{C}_{n-1} + {}_{2^k-1}\mathrm{C}_{n} \quad (1 \leqq n \leqq 2^k-1) $$

(1)より、$1 \leqq n \leqq 2^k-1$ において左辺の ${}_{2^k}\mathrm{C}_{n}$ は偶数である。したがって、両辺を2を法とする合同式で考えると、

$$ {}_{2^k-1}\mathrm{C}_{n-1} + {}_{2^k-1}\mathrm{C}_{n} \equiv 0 \pmod 2 $$

$$ {}_{2^k-1}\mathrm{C}_{n} \equiv {}_{2^k-1}\mathrm{C}_{n-1} \pmod 2 $$

が成り立つ。${}_{2^k-1}\mathrm{C}_{0} = 1$ は奇数であるから、この漸化的な関係から $n = 0, 1, \dots, 2^k-1$ のすべてについて ${}_{2^k-1}\mathrm{C}_{n}$ は奇数となる。よって、$m = 2^k - 1$ は条件を満たす。

(ii)

$2^{k-1} \leqq m < 2^k - 1$ の場合

このとき、$m = 2^{k-1} + l$（$0 \leqq l < 2^{k-1}-1$）とおくことができる。二項定理より、

$$ (1+x)^{2^{k-1}} = 1 + x^{2^{k-1}} + \sum_{i=1}^{2^{k-1}-1} {}_{2^{k-1}}\mathrm{C}_{i} x^i $$

(1)より、$1 \leqq i \leqq 2^{k-1}-1$ に対して ${}_{2^{k-1}}\mathrm{C}_{i}$ は偶数であるため、整数係数の多項式 $P(x)$ を用いて以下のように表せる。

$$ (1+x)^{2^{k-1}} = 1 + x^{2^{k-1}} + 2P(x) $$

これを用いると、$(1+x)^m$ は次のように展開できる。

$$ \begin{aligned} (1+x)^m &= (1+x)^{2^{k-1}} (1+x)^l \\ &= (1 + x^{2^{k-1}} + 2P(x)) \sum_{j=0}^{l} {}_l\mathrm{C}_{j} x^j \\ &= \sum_{j=0}^{l} {}_l\mathrm{C}_{j} x^j + \sum_{j=0}^{l} {}_l\mathrm{C}_{j} x^{2^{k-1}+j} + 2P(x)(1+x)^l \end{aligned} $$

この恒等式の両辺における $x^{l+1}$ の係数を比較する。左辺の $x^{l+1}$ の係数は ${}_m\mathrm{C}_{l+1}$ である。右辺について各項を調べる。

・第1項 $\sum_{j=0}^{l} {}_l\mathrm{C}_{j} x^j$ の最大次数は $l$ であるため、$x^{l+1}$ の項は現れない。

・第2項 $\sum_{j=0}^{l} {}_l\mathrm{C}_{j} x^{2^{k-1}+j}$ の最小次数は $2^{k-1}$ である。$l < 2^{k-1}-1$ より $l+1 < 2^{k-1}$ であるため、ここにも $x^{l+1}$ の項は現れない。

・第3項 $2P(x)(1+x)^l$ は、$P(x)$ が整数係数多項式であることから、展開したときの係数はすべて偶数である。したがって、$x^{l+1}$ の係数も偶数である。

以上より、${}_m\mathrm{C}_{l+1}$ は偶数となる。ここで $l \geqq 0$ より $l+1 \geqq 1$ であり、$l+1 < 2^{k-1} \leqq 2^{k-1}+l = m$ であるから、$n=l+1$ は $0 \leqq n \leqq m$ の範囲にある。ゆえに、偶数となる二項係数が存在するため、この $m$ は条件を満たさない。

以上（i）, （ii）より、条件を満たす自然数 $m$ は $m = 2^k - 1$ の形に限られる。

解法2

(1)の別解として、ルジャンドルの定理を用いて素因数2の個数を直接評価する方法を示す。

実数 $x$ を超えない最大の整数を $\lfloor x \rfloor$ で表す。自然数 $N!$ に含まれる素因数2の個数を $v_2(N!)$ とすると、ルジャンドルの定理より以下が成り立つ。

$$ v_2(N!) = \sum_{i=1}^{\infty} \left\lfloor \frac{N}{2^i} \right\rfloor $$

これを用いると、二項係数 ${}_{2^k}\mathrm{C}_{n} = \frac{(2^k)!}{n!(2^k-n)!}$ に含まれる素因数2の個数 $v_2({}_{2^k}\mathrm{C}_{n})$ は次のように計算できる。

$$ v_2({}_{2^k}\mathrm{C}_{n}) = v_2((2^k)!) - v_2(n!) - v_2((2^k-n)!) = \sum_{i=1}^{k} \left( \left\lfloor \frac{2^k}{2^i} \right\rfloor - \left\lfloor \frac{n}{2^i} \right\rfloor - \left\lfloor \frac{2^k-n}{2^i} \right\rfloor \right) $$

ここで、任意の正の実数 $X, Y$ について $\lfloor X+Y \rfloor \geqq \lfloor X \rfloor + \lfloor Y \rfloor$ が成り立つことから、$X = \frac{n}{2^i}, Y = \frac{2^k-n}{2^i}$ とおくと、各 $i$ について以下の不等式が成り立つ。

$$ \left\lfloor \frac{2^k}{2^i} \right\rfloor - \left\lfloor \frac{n}{2^i} \right\rfloor - \left\lfloor \frac{2^k-n}{2^i} \right\rfloor \geqq 0 $$

特に $i=k$ のときを考える。$0 < n < 2^k$ であるから、$0 < \frac{n}{2^k} < 1$ かつ $0 < \frac{2^k-n}{2^k} < 1$ であり、それぞれガウス記号を外すと0になる。

$$ \left\lfloor \frac{2^k}{2^k} \right\rfloor - \left\lfloor \frac{n}{2^k} \right\rfloor - \left\lfloor \frac{2^k-n}{2^k} \right\rfloor = 1 - 0 - 0 = 1 $$

各項が0以上であり、少なくとも $i=k$ のときの項が1であるため、総和は1以上となる。

すなわち $v_2({}_{2^k}\mathrm{C}_{n}) \geqq 1$ であり、これは ${}_{2^k}\mathrm{C}_{n}$ が素因数2を持つこと、つまり偶数であることを示している。（証明終）

解説

二項係数の偶奇や素因数の個数を問う問題は、整数問題の典型的なテーマである。(1)は $n \cdot {}_m\mathrm{C}_{n} = m \cdot {}_{m-1}\mathrm{C}_{n-1}$ の変形を用いるのが最も簡潔ですが、解法2のようにルジャンドルの定理（あるいはKummerの定理）を用いた評価も汎用性が高いアプローチである。

(2)では、すべての二項係数が奇数になる行が「パスカルの三角形において $2^k-1$ 段目である」という有名な性質の証明を求めている。多項式 $(1+x)^m$ を2の累乗で分解して二項定理を適用する手法は、複雑な二項係数の性質を係数比較に帰着させることができる強力な武器である。