ヒントを見逃したら二項係数の力ずく計算 – 2009年東大 数学 第１問
余談：小問3で d_m = 2 になる必要十分条件
小問3は dm が1または2であることを証明することがお題であって、どういうときに d_m = 1 になり、どういうときに d_m =2 になるのかはどうでもよいことですが、小問3の解法1を応用すると、その条件を明らかに出来ます。
m = 2n と置くとき、 n が奇数なら、
_{2n} \mathrm{C}_2 = n(2n-1)なので、 _{2n} \mathrm{C}_2 は奇数であり、したがって dm = 1 であることが直ちにわかります。
では、 n が偶数なら dm = 2 になるのかと言うと、必ずしもそうではありません。
m = 4 のとき、
\begin{aligned}
_4 \mathrm{C}_1 & = 4 \\
_4 \mathrm{C}_2 & = 6
\end{aligned}m = 8 のとき、
\begin{aligned}
_8 \mathrm{C}_1 & = 8 \\
_8 \mathrm{C}_2 & = 28 \\
_8 \mathrm{C}_3 & = 56 \\
_8 \mathrm{C}_4 & = 70 \\
\end{aligned}で、いずれの場合も dm = 2 ですが、 m = 12 のとき、
\begin{aligned}
_{12} \mathrm{C}_1 & = 12 \\
_{12} \mathrm{C}_2 & = 66 \\
_{12} \mathrm{C}_3 & = 220 \\
_{12} \mathrm{C}_4 & = 465 \\
_{12} \mathrm{C}_5 & = 792 \\
\end{aligned}で、 d12 = 1となります。
どうも、 m が２のべき乗、すなわち m = 2^n (n \geqq 1) であることが、 dm = 2 であることの必要十分条件になりそうです。以下、それを証明します。
m が２のべき乗のとき
m = 2^n (n \geqq 1) と置きます。このとき、任意の 1 \leqq k \leqq 2^{n-1} に対し、 _{2^n} \mathrm{C}_k が２の倍数であることを示します。
\begin{aligned}
_{2^n} \mathrm{C} _{k} & =\frac{\prod\limits_{j=0}^{k -1} (2^n - j)}{\prod\limits_{j=0}^{k -1} (k - j)} \\
& = \frac{\prod\limits_{j=0}^{k -1} (2^n - j)}{\prod\limits_{j=1}^{k} j} \\
& = \frac{2^n \prod\limits_{j=1}^{k -1} (2^n - j)}{k \prod\limits_{j=1}^{k-1} j} \\
& = \frac{2^n}{k}\prod\limits_{j=1}^{k -1} \frac{2^n-j}{j}
\end{aligned}ここで j を以下のように 2 のべき乗表記します。
j= \sum_{l=0}^{n-1} a_{jl }2^lここに a_{ij} は0か1のいずれかです。
また、 a _{j l_0} を、０でない a_{jl} のうち、最も若番のものとします。すなわち、
\begin{aligned}
a_{jl_0} & =1 \\
a_{jl} &= 0(0 \leqq l < l_0)
\end{aligned}です。
このとき、
\begin {aligned}
& \frac{2^n - j}{j} \\
= & \frac{2^n - \sum\limits_{l=0}^{n-1} a_{jl }2^l}{ \sum\limits_{l=0}^{n-1} a_{jl }2^l} \\
= & \frac{2^n - \sum\limits_{l=l_0}^{n-1} a_{jl }2^l}{ \sum\limits_{l=l_0}^{n-1} a_{jl }2^l} \\
= & \frac{2^{l_0} \left (2^{n - l_0} - \sum\limits_{l=l_0+1}^{n-1} a_{jl }2^{l - l_0}-1 \right )}{ 2^{l_0} \left (\sum\limits_{l=l_0+1}^{n-1} a_{jl }2^{l-l_0} +1 \right )} \\
= & \frac{2^{n - l_0} - \sum\limits_{l=l_0+1}^{n-1} a_{jl }2^{l - l_0}-1 }{ \sum\limits_{l=l_0+1}^{n-1} a_{jl }2^{l-l_0} +1 } \\
= & \frac{ 2 \left (2^{n - l_0 -1 } - \sum\limits_{l=l_0+1}^{n-1} a_{jl }2^{l - l_0 -1} \right )-1 }{ 2 \left (\sum\limits_{l=l_0+1}^{n-1} a_{jl }2^{l-l_0-1} \right ) +1 }
\end{aligned}であり、分母も分子も奇数です。
また、 \frac{2^n}k については、 1 \leqq k \leqq 2^{n-1} であることから、k の2の次数は n-1 以下であり、約分すると分子の2が必ず残ります。
したがって、任意の 1 \leqq k \leqq 2^{n-1} に対し、 _{2^n} \mathrm{C}_k が２の倍数であることが示せました。
m が2のべき乗でないとき
ｍ の素因数分解を、
m= \prod_{i=1}^I p_i^{ \alpha_i}と表記します。ここに I > 1、 p_i は n の素因数、 \alpha_i はその次数です。
このとき、小問3の解法その1と同様にして、m のすべての素因数 piに対し、二項係数 _{m} \mathrm{C}_l, l=1,2, \cdots, m-1 の公約数でないことが示せます。したがって二項係数は互いに素であり、 dm = 1 です。これは m が偶数（すなわち piのいずれかが2に等しい）の場合も同様です。
ゆえに、 dm = 2 である必要十分条件は、 m が2のべき乗であることが示せました。