${}_{100}C_{50}$ が $3^n$ で割り切れるとき、最大の自然数 $n$ を求めよ。

1. 問題の内容

${}_{100}C_{50}$ が $3^n$ で割り切れるとき、最大の自然数 $n$ を求めよ。

2. 解き方の手順

${}_{100}C_{50} = \frac{100!}{50!50!}$ である。

$100!$ を素因数分解したときの $3$ の指数を $e_3(100!)$ と表す。同様に $e_3(50!)$ を定義する。

ルジャンドルの公式より、

$e_3(100!) = \lfloor \frac{100}{3} \rfloor + \lfloor \frac{100}{3^2} \rfloor + \lfloor \frac{100}{3^3} \rfloor + \dots = 33 + 11 + 3 + 1 = 48$

$e_3(50!) = \lfloor \frac{50}{3} \rfloor + \lfloor \frac{50}{3^2} \rfloor + \lfloor \frac{50}{3^3} \rfloor + \dots = 16 + 5 + 1 = 22$

したがって、${}_{100}C_{50}$ を素因数分解したときの $3$ の指数は

$e_3({}_{100}C_{50}) = e_3(100!) - 2e_3(50!) = 48 - 2 \times 22 = 48 - 44 = 4$

${}_{100}C_{50} = 3^4 \times k$ ($k$ は $3$ で割り切れない整数) と表せるので、${}_{100}C_{50}$ は $3^4$ で割り切れるが、$3^5$ では割り切れない。

したがって、求める最大の自然数 $n$ は $4$ である。

3. 最終的な答え

4