7-3 ガウス記号と2項係数

最後に,ガウス記号の応用として$n!, \ _nP_r, \ _nC_r$を素因数分解したときの素数のべきを調べよう.
$p$を素数とする.
$n!$を素因数分解したときの$p$の冪は
$1$から$n$までの$p$の倍数の個数,$p^2$の倍数の個数,・・・
を加えればよいから
$\left[\dfrac{n}{p}\right]+\left[\dfrac{n}{p^2}\right]+\left[\dfrac{n}{p^3}\right]+\cdots$
である.これを利用して 次の問題をといてみよう.

問題6
(1)$100!$の末尾に続く$0$の個数を求めよ
(2)$_{100}P_{50}$の末尾に続く$0$の個数を求めよ
(3)$_{100}C_{50}$の末尾に続く$0$の個数を求めよ

解答
末尾に続く$0$の個数は素因数分解したときの$2$の指数と$5$の指数の小さいほうである.
この問題ではいずれも$5$の指数の方が小さいから 5の指数を求めればよい.
(1) $\left[\dfrac{100}{5}\right]+\left[\dfrac{100}{5^2}\right]=24$
したがって,24個の$0$が続く
(2) $_{100}P_{50}=\dfrac{100!}{50!}$
であるから,
$\left[\dfrac{50}{5}\right]+\left[\dfrac{50}{5^2}\right]=12$
より$50!$の5の指数は24-12=12.
したがって12個の$0$が続く
(3)$_{100}C_{50}=\dfrac{100!}{50!\cdot 50!}$
であるから,(1),(2)より
24−2×12=0
末尾(1の位)に0はない.

参考
たとえば,1から123までの整数の中で,10の倍数は12個,100の倍数は1個である.同様に考えると
(1) $100$を$5$進法で表すと
$100=4\cdot 5^2=400_{(5)}$
したがって,末尾に続く$0$の個数は
$40_{(5)}+4_{(5)}=44_{(5)}=24$
となる.


つぎに,任意の実数$m,n$で $m=[m]+\{m\}, \ \ n=[n]+\{n\}$
より
$[m+n]=\left[[m]+[n]+\{m\}+\{n\}\right]=[m]+[n]+\left[\{m\}+\{n\}\right]$ $\therefore [m]+[n]\leqq [m+n] \leqq [m]+[n]+1$

次の(1)は組み合わせの定義より明らかですが,ガウス記号を用いて解くのも面白い.
命題
(1)$_{m+n}C_m$は整数である.
(2)$p$が素数のとき$_pC_m$は$1\leqq m \leqq p-1$のとき$p$の倍数である.
証明
(1)$_{m+n}C_m=\dfrac{(m+n)!}{m!\cdot n!}$ 任意の素数$p$で
$\left[\dfrac{m}{p}\right]+\left[\dfrac{n}{p}\right]\leqq \left[\dfrac{m+n}{p}\right]$
より命題が成り立つ.

(2)$p$が素数のとき$1\leqq m\leqq p-1$をみたす$m$は素因数$p$を持たない.
$_pC_m=\dfrac{p!}{m!\cdot (p-m)!}$
分母は$p$を素因数として持たないが,分子は$p$を素因数として持つから$_pC_m$は$p$の倍数である.

次の問題は2項係数の偶奇を調べる面白い問題です.
問題7
(1) $k$を自然数とする.$m$を$m=2^k$とおくとき,$0$<$n$<$m$を満たすすべての整数$n$について,2項係数$_mC_n$は偶数である ことを証明せよ.

(2) 以下の条件を満たす自然数$m$をすべて求めよ.
条件:$0\leqq n \leqq m$を満たすすべての整数$n$について二項係数$_mC_n$は奇数である.
(1999年 東京大)

解答
(1) $_mC_n=\dfrac{m!}{(m-n)!\cdot n!}$
自然数$l$に対して
$\left[\dfrac{m}{2^l}\right]\geqq \left[\dfrac{m-n}{2^l}\right]+\left[\dfrac{n}{2^l}\right] \ \ \cdots (\sharp)$
が成り立つ.
$m=2^k$のとき,任意の$1$<$n$<$2^k$を満たす$n$で$(\sharp)$で等号が成り立たない$l$が存在することを示せばよい.
ここで,
$\left[\dfrac{2^k}{2^k}\right]=1$
$\left[\dfrac{2^k-n}{2^k}\right]+\left[\dfrac{n}{2^k}\right]=0$
であるから$(\sharp)$で等号が成り立たないので証明された.

(2)
$m=2^k-1$のとき,
$m=1+2+2^2+\cdots +2^{k-1}$・・・@
である.
$m$を正の整数$a,b$で
$m=a+b$
と表す.$a$を2の冪だけで表すと,@より$a$で用いた2の冪を除いたものが$b$であるから, 任意の$1\leqq l \leqq k-1$を満たす$l$で,
$\left[\dfrac{m}{2^l}\right]=\left[\dfrac{a}{2^l}\right]+\left[\dfrac{b}{2^l}\right]$ が成り立つ.
さらに$_mC_0=1,_mC_m=1$であるから$m=2^k-1$のときの2項係数は奇数である.
次に, $2^{k-1}+1\leqq m \leqq 2^k-1$のとき調べる
$m$は$1+2+2^2+\cdots +2^{k-1}$から少なくとも1つの項を除いたものである.
たとえば$2^{h+1}$の項は含むが$2^h$の項は含まないとすると,$a,b$を
$a=2^h,b=m-2^h$
で定めれば,
$\left[\dfrac{m}{2^{h+1}}\right]$>$\left[\dfrac{a}{2^{h+1}}\right]+\left[\dfrac{b}{2^{h+1}}\right]$
であるから,$_mC_a$は偶数である.
以上のことより,条件を満たす$m$は$m=2^k-1$である.

<参考>
解答は少し分かりづらい.もう少し説明する.
\(m=1+2+2^2+\cdots +2^{k-1}\)から少なくとも1つの項を除いた数を考える.
ここでは\(2^h\)を含まないとする.
\(m\)を\(2^h\)と\(m-2^h\)に分けると
\(2^{h+1}=2^h+2^h\cdots (\sharp)\)
\(2^{h+2}=2^h+(2^h+2^{h+1})\cdots (\flat)\)
となる.\((\sharp)\)は
\(\left[\dfrac{2^{h+1}}{2^{h+1}}\right]=1, \left[\dfrac{2^h}{2^{h+1}}\right]+\left[\dfrac{2^h}{2^{h+1}}\right]=0\)
\((\flat)\)は
\(\left[\dfrac{2^{h+2}}{2^{h+1}}\right]=2, \left[\dfrac{2^h}{2^{h+1}}\right]+\left[\dfrac{2^h+2^{h+1}}{2^{h+1}}\right]=1\)
である.
\(_mC_n\)のとき.\(m\)を2進数表示し,1の位から見て最初に\(0\)になる位が\(2^h\)なら,数列 \(\{_mC_k\};k=0,1,2,3,\dots ,m\)は\(k=2^h\)のときはじめて偶数になる.
以上のことが理解できれば,2項係数で偶数になる場合をすべて見つけることが出来る.
奇数になるのは,2進法表示し引いたとき位下がり起こるときである.
たとえば
\(m=1+2+2^4=19=10011_{(2)}\)
で調べれば,位下がりが起こらないのは(すなわち奇数)は
\(n=1_{(2)},10_{(2)},11_{(2)}=1,2,3\)
だけである.実際奇数になるのは,明らかな\(_{19}C_0,_{19}C_{19}\)を除けば
\(_{19}C_1(=_{19}C_{18}),_{19}C_2(=_{19}C_{17}),_{19}C_3(=_{19}C_{16})\)
だけである.


問題8
$n$が相異なる素数$p,q$の積$n=pq$であるとき,$(n-1)$個の数
$_nC_k \ \ (1\leqq k \leqq n-1)$
の最大公約数は$1$であることを示せ.

解答
$_{pq}C_1=pq$
であるから,素数$p,q$が公約数でないことを示せばよい.
$_{pq}C_p=\dfrac{(pq)(pq-1)\cdots (pq-p+1)}{p!}$
分子は
$(pq)(pq-1)\cdots \{(p(q-1)+1)\}$・・・@
であり,$p$は素数より
$pq-1,pq-2,\cdots ,p(q-1)+1$
それぞれ$p$を素因数として持たない.
したがって,@の分子,分母の素数$p$の冪は$1$で等しいから $p$は\(_{pq}C_p\)の素因数ではない.
同様に$_{pq}C_q$は素数$q$を素因数に持たない.
したがって,証明された.

と証明するのが一般的であるが,
$_{pq}C_p=\dfrac{(pq)!}{(pq-p)!\cdot p!}$
の分子,分母の素数$p$の冪を調べるのも面白い.

$\bullet \ \ p$<$q$のとき.
$p^h$<$q$<$p^{h+1}$
で$h$を定める.
$\left[\dfrac{pq}{p}\right]=q,$ $\left[\dfrac{pq-p}{p}\right]+\left[\dfrac{p}{p}\right]=q$
$k\geqq 2$のとき,
$\left[\dfrac{pq-p}{p^k}\right]+\left[\dfrac{p}{p^k}\right]$
$=\left[\dfrac{q-1}{p^{k-1}}\right]=\left[\dfrac{q}{p^{k-1}}\right]$
$(\because \ \ \frac{q}{p^{k-1}}\text{は整数でない})$
$=\left[\dfrac{pq}{p^k}\right]$
したがって,$_{pq}C_p$は素数$p$を素因数に持たない.
$\bullet \ \ q$<$p$のとき.
$\left[\dfrac{pq}{p}\right]=q,$ $\left[\dfrac{pq-p}{p}\right]+\left[\dfrac{p}{p}\right]=q$
であるから,この場合も$_{pq}C_p$は素数$p$を素因数に持たない.
したがって,証明が終了した.


以下2015年4月追加しました.

問題9
\(m\)を\(2015\)以下の正の整数とする.\(_{2015}C_m\)が偶数となる最小の\(m\)を求めよ.
(2015年 東京大)

解答
\(2048=1024\times 2=2^{11}\)
したがって,\(2047=2048-1\)を2進数表示すると,\(2047\) より小さいどのような正の数を引いても2進法では位下がりが起こらない.
一方\(2015=2047-2^5\)より
\(2015=1+2^1+2^2+2^3+2^4+2^6+2^7+2^8+2^9+2^{10}+2^{11}=111111011111_{(2)}\)
\(1\leqq k\leqq 31\)のとき任意の\(k\)で
\(\left[\dfrac{2015}{2^h}\right]=\left[\dfrac{k}{2^h}\right] +\left[\dfrac{2015-k}{2^h}\right]\)
が成り立つから,\(_{2015}C_k\)は奇数である.一方,
\(2015=2^5+(2015-2^5)\)
と分けると,
\(2015-2^5=1+2^1+2^2+2^3+2^4+2^5+2^7+2^8+2^9+2^{10}+2^{11}\)
であるから,
\(\left[\dfrac{2015}{2^6}\right] =\left[\dfrac{2^6+2^7+2^8+2^9+2^{10}+2^{11}}{2^6}\right]\)

\(\left[\dfrac{2^5}{2^6}\right]+\left[\dfrac{2015-2^5}{2^6}\right] =\left[\dfrac{2^7+2^8+2^9+2^{10}+2^{11}}{2^6}\right]\)
したがって,
\(\left[\dfrac{2015}{2^6}\right] =\left[\dfrac{2^5}{2^6}\right]+\left[\dfrac{2015-2^5}{2^6}\right]+1\)
より,\(_{2015}C_{2^5}\)は偶数である.なお.\(2^h (7\leqq h)\)で割ったときの整数部分は等しいから \(_{2015}C_{2^5}\)は偶数であるが\(4\)の倍数ではない.


解説
次の式は\((1+x)^n\)の展開式である.スライダーを動かすとnは\(1\leqq n\leqq 32\)の範囲で 動きます.もちろん\(x\)の係数が2項係数です.

(スライダーをドラッグするとnが1から32の範囲で動きます.
もし,画面にGet the Wolfram CDF Player とあらわれたら,画面をクリックしCDF Playerをインストールしてください.
ブラウザによって差があるので,うまくいかないときはほかのブラウザをお試しください. ブラウザの差が実感できると思います)


\(_{32}C_k,_{31}C_k,_{30}C_k\)の偶奇を調べてみましょう.その後例題7の解答を読んでみましょう. すっきり理解できると思います.
この問題は整数の2進法の問題です.新課程では重要視されてる分野です.


2進法表示を用いると比較的簡単に解決する問題をもう1題紹介します.
問題10
区間$[0,1]$において関数$f(x)$を
$f(x)=\begin{cases}2x & (x\leqq \dfrac{1}{2}) \\ -2x+2 & (x > \dfrac{1}{2})\end{cases}$
とおく.
$0\leqq a_1\leqq 1$を満たす実数$a_1$を初項として数列$\{a_n\}$を
$a_n=f(a_{n-1}) \ \ (n=2,3,\dots )$
で定める.このとき次の問いに答えよ.
(1) $f(b)=b$を満たす,$0\leqq b\leqq 1$なる実数$b$をすべて求めよ.
(2) $a_4$が(1)で求めた$b$の値に等しくなるような初項$a_1$をすべて求めよ.
(3) 条件「ある$n\geqq 1$に対して,$a_n$が(1)で求めた$b$の値に等しくなる」をみたす初項$a_1$ はどのような実数として表されるか.
(4)初項$a_1$が(3)の条件を満たさないとき,$a_n\geqq \dfrac{3}{4}$となるような$n\geqq 1$ が存在することを示せ.
(5) 数列$\{a_n\}$が収束するために初項$a_1$が満たすべき必要十分条件を求めよ.
(2002年 東京大・後期)


解答
(1)$f(b)=b$より$b=0,\dfrac{2}{3}.$
(2) $a_n=2a_{n-1}$より$a_{n-1}=\dfrac{a_n}{2}$
したがって,$a_2=0,\dfrac{2}{3}$のとき
$a_1=0,\dfrac{1}{3}.$
$a_n=-2a_{n-1}+2$より$a_{n-1}=1-\dfrac{a_n}{2}.$
さらに$\dfrac{a_n}{2}$と$1-\dfrac{a_n}{2}$は$\dfrac{1}{2}$に関して対称であるから
$a_1=0,\dfrac{1}{3},\dfrac{2}{3},1$
この操作を繰り返せばよいから
同様に$a_3=0,\dfrac{2}{3}$のとき
$a_1=0,\dfrac{1}{3\cdot 2},\dfrac{2}{3\cdot 2}\dfrac{3}{3\cdot 2}\dfrac{4}{3\cdot 2},\dfrac{5}{3\cdot 2},1$
$a_4=0,\dfrac{2}{3}$のとき
$a_1=\dfrac{k}{3\cdot 2^2} \ \ (k=0,1,2,\dots ,12)$
(3) 同様に$a_n=0,\dfrac{2}{3}$のとき
$a_1=\dfrac{k}{3\cdot 2^{n-2}} \ \ (k=0,1,2,\dots ,3\cdot 2^{n-2})$

(4)この問題は2進数を利用すると比較的容易に証明できる.
$f_n=\overbrace{f\circ \cdots \circ f}^{n\text{個}}$
とおくと$y=f_n(x)$のグラフは右図.
$f_n(x) \geqq \dfrac{3}{4}$
を解くと
$\dfrac{1}{2^n}-\dfrac{1}{4}\dfrac{1}{2^n} \leqq x \leqq \dfrac{1}{2^n}+\dfrac{1}{4}\dfrac{1}{2^n}, \dfrac{3}{2^n}-\dfrac{1}{4}\dfrac{1}{2^n} \leqq x \leqq \dfrac{3}{2^n}+\dfrac{1}{4}\dfrac{1}{2^n},$
$\dots ,\dfrac{2^n-1}{2^n}-\dfrac{1}{4}\dfrac{1}{2^n} \leqq x \leqq \dfrac{2^n-1}{2^n}+\dfrac{1}{4}\dfrac{1}{2^n}$
まとめると
$\dfrac{2k-1}{2^n}-\dfrac{1}{4}\dfrac{1}{2^n} \leqq x \leqq \dfrac{2k-1}{2^n}+\dfrac{1}{4}\dfrac{1}{2^n} \ \ (k=1,2,\dots ,2^{n-1})$
両辺に$2^{n+2}$をかけて
$4(2k-1)-1\leqq 2^{n+2}x \leqq 4(2k-1)+1 \cdots (\sharp)$
証明すべき内容は
$x$が$0\leqq x \leqq 1$かつ$x\neq \dfrac{l}{3\cdot 2^m} \ (m=0,1,2,\dots ,l=0,1,2,\dots ,3\cdot 2^m)$
を満たすとき$(\sharp)$を満たす $n,k$が存在
である.
この証明を行おう.
2進数で表すと
$\dfrac{2}{3}=0.101010\cdots_{(2)}$
であるから
$\dfrac{2}{3\cdot 2^n}=0.\overbrace{0\dots 0}^{n\text{個}}1010\cdots _{(2)}$
したがって,$x\neq \dfrac{l}{3\cdot 2^m}$より,$x$を2進数で表すと$1$が現れてから どこかで$0$または$1$が連続する.
$\bullet \ 0$が連続するとき
$x=0.\cdots 100\cdots _{(2)}$
であるから 適当な自然数$n$を選ぶことにより
$2^nx=\cdots100.\cdots _{(2)}$
これは
$2^nx=4\times(奇数)+\alpha ,0\leqq \alpha <1$
を意味している.
$\bullet \ 1$が連続するとき
$x=0.\cdots 011\cdots _{(2)}$
であるから 適当な自然数$n$を選ぶことにより
$2^nx=\cdots011.\cdots _{(2)}=\cdots 100_{(2)}-1+0.\cdots _{(2)}$
これは
$2^nx=4\times(奇数)-\beta ,0\leqq \beta <1$
を意味している.
以上で証明が終了した.
(5)(4)が解決すると大きな問題はない.
$a_1=\dfrac{k}{3\cdot 2^{n-2}} \ \ (k=0,1,2,\dots ,3\cdot 2^{n-2})\cdots (\flat)$
のとき収束することは示されている.
初項が$(\flat)$以外のとき,$a_n\geqq \dfrac{3}{4}$を満たす$n$が存在することが(4)であった.
$\dfrac{3}{4}\leqq x\leqq 1$のとき$0\leqq f(x)\leqq \dfrac{1}{2}$
であるから,
$0\leqq a_{n+1}=f(a_n)\leqq \dfrac{1}{2}$
さらに,$a_n$は$(\flat)$の条件を満たさないから,$a_n$を新しく初項と考えれば,正の整数$m$が 存在して
$a_{n+m}\geqq \dfrac{3}{4},a_{n+m+1}\leqq \dfrac{1}{2}$.
この議論は繰り返すことができる.すなわち,差が$\frac{1}{4}$以上の連続する2項が限りなく現れるので収束しない. 以上で,収束する条件は$(\flat)$であることが証明された.

解説
2進法を用いて解決したが,2進法を用いないとなかなかの難問である.そのむずかしさを説明する.
区間
$\dfrac{2k-1}{2^n}-\dfrac{1}{4}\dfrac{1}{2^n} \leqq x \leqq \dfrac{2k-1}{2^n}+\dfrac{1}{4}\dfrac{1}{2^n} \ \ (k=1,2,\dots ,2^{n-1})$
の$n=1,2,3,\cdots$の和集合を計算するのであるが,$x=\frac{1}{3}$に注目し,区間がどのようになっているかを調べてみよう.
$n=1,3,5,\cdots$の場合.$\frac{1}{3}$以上の最初の区間の左端点に注目すると
$\dfrac{1}{2}-\dfrac{1}{2\cdot 4}-\dfrac{1}{2\cdot 4^2}-\dots =\dfrac{1}{3}$
$n=2,4,6,\cdots$の場合.$\frac{1}{3}$以下の最初の区間の右端点に注目すると
$\dfrac{1}{4}+\dfrac{1}{4\cdot 4}+\dfrac{1}{4\cdot 4^2}+\dots =\dfrac{1}{3}$
このことから,$\frac{1}{3}$はどの区間にも含まれない.また$\frac{1}{3}$に近い数はある区間に 含まれるが,$\frac{1}{3}$に近づけば近づくほどnの値は大きくなることがわかる (これは解答の証明でも読み取れる). このような理由から解決するには極限操作が必要となり, 直接解くためには高い数学の処理能力が求められる.

問題10は2進法で考えることで比較的簡単に解決した. 解答で用いた方法は,Cantor(カントル)の零集合を想起する.
Cantorの零集合を述べてこの項を終わりにする.
区間$I$を$I=[0,1]$とする.
まず,$I$を3等分し真ん中の開区間$(\frac{1}{3},\frac{2}{3})$を取り除く.
つぎに残った区間$[0,\frac{1}{3}],[\frac{2}{3},1]$をそれぞれ3等分し,真ん中の開区間 $(\frac{1}{3^2},\frac{2}{3^2}),(\frac{2}{3}+\frac{1}{3^2},\frac{2}{3}+\frac{2}{3^2})$をとり除く.

今度は4つの区間が残るが,それぞれに区間を3等分し,真ん中の開区間を取り除く. この操作をいつまでも続けていく.
この操作により取り除いた全体を$A$とし,残った全体を$B$とする.
$A$は無限個(可算個)の開区間に分かれ,それらは共通部分を持たない.それぞれの区間の長さの和を求めよう.
最初 取り除いた区間の長さは$\frac{1}{3}$,
つぎに取り除いたのは$\frac{1}{3}\times \frac{1}{3}\times 2=\frac{1}{3}\times \frac{2}{3}$
つぎに取り除いたのは$\frac{1}{3}\times \frac{1}{3}\times \frac{1}{3}\times 2^2=\frac{1}{3}\times (\frac{2}{3})^2$
これらの和を求めると
$\dfrac{1}{3}+\dfrac{1}{3}\times \dfrac{2}{3}+\dfrac{1}{3}\times (\dfrac{2}{3})^2+\cdots =1$
$I$の長さは$1$であるから,残った$B$の長さは$0$である.
つぎに$B$がどのような集合かを調べよう.
取り除いた集合$A$に注目すると考えやすい.
最初に取り除くのは
$\dfrac{1}{3} < x < \dfrac{2}{3}$
であるから,3進法で表すと
$0.1_{(3)} < x < 0.2_{(3)}$
これは,3進法で表した時小数第1位が1の数を取り除くことを意味している.
以下取り除く数を3進法で表せば
$0.01_{(3)} < x < 0.02_{(3)},0.21_{3} < x < 0.22_{(3)}$
さらに
$0.001_{(3)} < x 0.002_{(3)},0.021_{3} < x < 0.022_{(3)} ,$
$0.201_{(3)} < x 0.202_{(3)},0.221_{3} < x < 0.222_{(3)} $
$\cdots$
より取り除くのは,3進法で表した時,数字$1$が現れる数は取り除かれるものがわかる.
なお,ここで$0.1_{(3)},0.21_{(3)}$は取り除かれないので
$0.1_{(3)}=0.02222\cdots_{(3)},0.21_{(3)}=0.20222\cdots _{(3)}$ と考え,有限小数で最後が1のときは$022\cdots$とする.
したがって,取り除かれる数は3進法で表した時どうしても$1$を使わなければならない数といった方がよい.
残った数の集合$B$は3進法表示したとき$1$が現れない数であるから
$B=\{x|x=0.a_1a_2a_3\dots _{3}, \ \ (a_i=0,2) \}$
となる.
思ったりスッキリ解決しました.
ここで,$B$のどの要素に対しても,いくらでもその要素に近い$A$の要素があります. 言い方を変えれば,任意の$a\in B$に対して $x_n\in A$が存在して
$x_n \to a$
が成り立つ.
たとえば$a=0.202_{(3)}$なら
$0.202_{(3)}=0.201222\cdots _{(3)}$とみて$\{x_n\}$を作ればよい.
さて,話はここでは終わりません.Cantorのすごさは,集合$B$が可算集合でないことを示したことです.
その証明をしましょう.
背理法を用います.
$B$が可算集合,すなわち順番付けできるとします.
$B=\{x_1,x_2,\cdots ,x_n,\cdots \}$
$x_n=0.a_{n1}a_{n2}\cdots a_{np}\cdots ,(a_{np}=0,2)$
さて,ここで$b_n$を
$a_{nn}=0$なら$b_n=2$
$a_{nn}=2$なら$b_n=0$
で定義し
$x=0.b_1b_2\cdots b_n\cdots$
とおけば,$x\in B$であるが$x\notin \{x_1,x_2,\cdots ,x_n,\cdots \}$
となり矛盾.したがって$B$が可算集合でないことが証明された.
(ガウス記号と方程式・不等式の項目終わり)






目次