1999年(平成11年)東京大学前期-数学(理科)[5] - [別館]球面倶楽部零八式markIISR

[5] (1) $k$ を自然数とする． $m$ を $m=2^k$ とおくとき， $0\lt n\lt m$ を満たすすべての整数 $n$ について，二項係数 ${}_{m}\mbox{C}_{n}$ は偶数であることを示せ．

(2) 以下の条件を満たす自然数 $m$ をすべて求めよ．

条件： $0\leqq n\leqq m$ を満たすすべての整数 $n$ について二項係数 ${}_{m}\mbox{C}_{n}$ は奇数である．

本問のテーマ

Kummer の定理

2019.01.12記

を利用する。

[大人の解答]
(1) $2^k_{(10)}=10\cdots 0_{(2)}$ を $n+(2^k-n)$ の足し算で表現したとき、 $0\lt n\lt m$ を満たすすべての整数 $n$ について、 $n$ を2進数で表現したときの最高位において繰り上がりが生じるので ${}_m\mbox{C}_{n}$ は偶数である。

(2) $0\leqq n\leqq m$ を満たすすべての整数 $n$ について2進数表示における $n+(m-n)$ の計算で繰り上がりが生じないためには、 $m$ の2進数表示の全ての桁が1であることが必要十分。よって、 $m=2^k-1(k=1,2,...)$

上記答案をそのまま書いても零点である。

2024.02.11記

[解答]
(1) ${}_{m}\mbox{C}_{n}$ $=\dfrac{m}{n}{}_{m-1}\mbox{C}_{n-1}$ $=\dfrac{2^k\times(整数)}{n}$ であるが， $0\lt n\lt m$ より $n$ のもつ素因数2の個数は $k$ 未満であるから，この分数を約分して整数としたときに分子に素因数2が少くとも1つ残ることになり，よってこれは偶数となる．

(2) 条件を満たす自然数 $m$ に対して， $0\leqq n\lt m$ を満たすすべての整数 $n$ について
${}_{m}\mbox{C}_{n}+{}_{m}\mbox{C}_{n+1}$ $={}_{m+1}\mbox{C}_{n+1}$
は全て偶数である．

逆に ${}_{m+1}\mbox{C}_{n+1}$ （ $0\leqq n\lt m$ ）が;全て偶数のとき， ${}_{m}\mbox{C}_{0}$ が奇数であることに着目すると， $0\leqq n\leqq m$ を満たすすべての整数 $n$ について ${}_{m}\mbox{C}_{n}$ は全て奇数である．

よって(1)より，任意の自然数 $k$ に対して $0\leqq n\leqq m=2^k-1$ を満たすすべての整数 $n$ について二項係数 ${}_{m}\mbox{C}_{n}$ は奇数である，つまりパスカルの三角形の $2^k-1$ 段目は全て奇数となる．

ある $k$ に対してパスカルの三角形の $2^k-1$ 段目は全て奇数となった次にパスカルの三角形のある段が全て奇数となるのは $2^{k+1}$ 段目であることを示せば，求める必要十分条件は $m$ がある自然数 $k$ を用いて $m=2^k-1$ と表せることとなる．(1) より任意の自然数 $k$ に対してパスカルの三角形の $m=2^k$ 段目の左から $1$ 番目は奇数で， $2$ 〜 $2^k$ 番目は偶数で， $2^k+1$ 番目は奇数である．

関係式 ${}_{m}\mbox{C}_{n}+{}_{m}\mbox{C}_{n+1}$ $={}_{m+1}\mbox{C}_{n+1}$ を繰り返し用いると
パスカルの三角形の $m=2^k+1$ 段目の左から $2$ 番目は奇数で， $3$ 〜 $2^k$ 番目は偶数で， $2^k+1$ 番目は奇数，
パスカルの三角形の $m=2^k+2$ 段目の左から $3$ 番目は奇数で， $4$ 〜 $2^k$ 番目は偶数で， $2^k+1$ 番目は奇数，
…，
パスカルの三角形の $m=2^k+(2^k-2)$ 段目の左から $2^k-1$ 番目は奇数で， $2^k$ 番目は偶数で， $2^k+1$ 番目は奇数
となる．

つまり，ある $k$ に対してパスカルの三角形の $2^k-1$ 段目は全て奇数となったとき $2^k$ 〜 $2^{k+1}-2$ 段目までは全てが奇数とはならないことが言えた．そして $2^{k+1}-1$ 段目は全て奇数となるので，ある $k$ に対してパスカルの三角形の $2^k-1$ 段目は全て奇数となった次にパスカルの三角形のある段が全て奇数となるのは $2^{k+1}$ 段目であることが示せた．よって求める必要十分条件は $m$ がある自然数 $k$ を用いて $m=2^k-1$ と表せることとなる．