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

問題：2015年(平成27年)東京大学前期-数学(理科) - [別館]球面倶楽部零八式markIISR

$m$ を $2015$ 以下の正の整数とする． ${}_{2015}\mbox{C}_{m}$ が偶数となる最小の $m$ を求めよ．

2019.01.11記

解説: ${2015}_{(10)}=11111011111_{(2)}$ を2つの数の和に分解したとき、足し算に繰り上がりが生じる最小の $m$ を求めれば良い。そのためには、 $10_{(2)}=1_{(2)}+1_{(2)}$ の計算結果が必要となるので、求める答は $m=100000_{(2)}=32_{(10)}$ である。

なお、 $m$ の最小性を考えると、 ${}_{2015}C_{m}={}_{2015}C_{m-1}\times\frac{2016-m}{m}$ において、 ${}_{2015}C_{m-1}$ が奇数で $\frac{2016-m}{m}$ の分子に偶数が残るような最小の $m$ を求めれば良いことを利用すれば、先程の判定方法を使わなくても解くことができる。 $m=2^{a}\times K$ ( $K$ は奇数)とおくと、 $2016-m=2^5\times 63-2^a\times K=2^a(2^{5-a}\times 63-K)$ だから $\frac{2016-m}{m}=\dfrac{2^{5-a}\times 63-K}{K}$ の分子に偶数が残るのは $a=5$ であり、このとき $m$ が最小になるのは $K=1$ のときである。よって $m=32$ としても良いだろう。

似たようなページを探したら、このようなページがありました。
sky-time-math.hatenablog.jp

なので、 ${}_nC_r$ が2で何回割り切れるかについてそのうち考えよう。

(2019.1.12追記)

二項係数は2で何回割れるか - 球面倶楽部零八式 mark II
により、 $m$ が1から31までのとき、 $(31-m)$ XOR $m=31$ であるから、
$2015_{(10)}=31\times 64+31$ に対して $2015$ XOR $(2015-m)$ XOR $m=0$ となるので、 ${}_{2015}C_{m}$ は奇数であることがわかる。

2020.10.18記
何か動画で「東大2015独自解法」で同じ解法があったけど、この解法、それほど珍しくないので、独自っていうのはどうかと思うんだけど。

二項係数の偶奇(解決編) - 球面倶楽部零八式 mark II
二項係数の偶奇 - 球面倶楽部零八式 mark II
二項係数が素数 p で割り切れない条件 - 球面倶楽部零八式 mark II
素数 p で割り切れない二項係数の個数 - 球面倶楽部零八式 mark II

でも触れたけど、

大学への数学2001年2月号に雲幸一郎さんの「素数で何回割り切れるか」という記事にクンマーの定理とは書いていないが，

「p進展開で a+b を計算するときに"繰り上がり"が何回起こるかで決まります。」

と書いてある．まぁ、雲Kが書いていたことはすっかり忘れていて、2020年7月に別の記事を参照するために大学への数学2001年2月号を見直したら、たまたま載っていて思い出したのだが、これを利用する問題はそこそこ出題されている．

2009年(平成21年)東京大学前期-数学(理科)[1] - [別館]球面倶楽部零八式markIISR
1999年(平成11年)東京大学前期-数学(理科)[5] - [別館]球面倶楽部零八式markIISR
1997年(平成9年)京都大学前期-数学(理系)[2] - [別館]球面倶楽部零八式markIISR
など

2021.03.23記
ちょっと解答っぽく整理しておく．

[大人の解答]

クンマーの定理により， ${2015}_{(10)}=11111011111_{(2)}$ を2つの数の和に分解したとき，足し算に繰り上がりが生じる最小の $m$ を求めれば良い．繰り上がりを生じさせるためには $10_{(2)}=1_{(2)}+1_{(2)}$ の計算結果が必要となるので、求める答は $m=100000_{(2)}=32_{(10)}$ である．

普通に解くなら次のようになる．

[解答]

${}_{2015}\mbox{C}_{m}={}_{2015}\mbox{C}_{m-1}\times\dfrac{2016-m}{m}$ であるから， $\dfrac{2016-m}{m}$ を既約分数で表現したときに分母に偶数が残るような最小の $m$ を求めれば良い．

$m=2^{a}\times K（Kは奇数）$ とおくと $2016-m=2^5\times 63-2^a\times K$ $=2^a(2^{5-a}\times 63-K)$ だから $\dfrac{2016-m}{m}=\dfrac{2^{5-a}\times 63-K}{K}$ となる．

$1\leqq m\leqq 31$ のとき， $a\leqq 4$ であるから
$2^{5-a}\times 63$ は偶数となり， $2^{5-a}\times 63-K$ は奇数となるので， $\dfrac{2016-m}{m}=\dfrac{2^{5-a}\times 63-K}{K}$ は分子も分母も奇数の既約分数となるので， ${}_{2015}\mbox{C}_m$ の計算に偶数は登場しないので，計算結果も奇数である．つまり，
${}_{2015}\mbox{C}_1$ ，…， ${}_{2015}\mbox{C}_{31}$ は奇数である．

次に $m=32$ のとき， $a=5$ ， $K=1$ であるから
$\dfrac{2016-m}{m}=\dfrac{2^0\times 63-1}{1}=62$ は偶数となるので，
${}_{2015}\mbox{C}_{32}={}_{2015}\mbox{C}_{31}\times 62$ は偶数である．

以上から求める $m$ は $32$ である．

このあたりの議論をより丁寧に説明させたのが，
2021年(令和3年)東京大学-数学(理科)[4] - [別館]球面倶楽部零八式markIISR
である．