7-3 ガウス記号と２項係数 最後に，ガウス記号の応用として$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 （１）$100!$の末尾に続く$0$の個数を求めよ （２）$_{100}P_{50}$の末尾に続く$0$の個数を求めよ （３）$_{100}C_{50}$の末尾に続く$0$の個数を求めよ 解答 末尾に続く$0$の個数は素因数分解したときの$2$の指数と$5$の指数の小さいほうである． この問題ではいずれも$5$の指数の方が小さいから ５の指数を求めればよい． （１） $\left[\dfrac{100}{5}\right]+\left[\dfrac{100}{5^2}\right]=24$ したがって，24個の$0$が続く （２） $_{100}P_{50}=\dfrac{100!}{50!}$ であるから， $\left[\dfrac{50}{5}\right]+\left[\dfrac{50}{5^2}\right]=12$ より$50!$の５の指数は24-12=12． したがって12個の$0$が続く （３）$_{100}C_{50}=\dfrac{100!}{50!\cdot 50!}$ であるから，（１），（２）より 24−2×12＝0 末尾(1の位)に０はない． 参考 たとえば，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\}$ より($\{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)は組み合わせの定義より明らかですが，ガウス記号を用いて解くのも面白い． 命題 （１）$_{m+n}C_m$は整数である． （２）$p$が素数のとき$_pC_m$は$1\leqq m \leqq p-1$のとき$p$の倍数である． 証明 （１）$_{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]$ より命題が成り立つ． （２）$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$が存在することを示せばよい． ここで，$l=k$のとき $\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の冪だけで表すと(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 < 2^k-1$のとき調べる $m$は$2^k-1=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]$ $(\because \left[\dfrac{a}{2^{h+1}}\right]=0$で$b=m-2^h$は$2^{h+1}$が$2^h$に変わるから$\left[\dfrac{b}{2^{h+1}}\right]=\left[\dfrac{m}{2^{h+1}}\right]-1)$ であるから，$_mC_a$は偶数である． 以上のことより，条件を満たす$m$は$m=2^k-1$である． ＜参考＞ 分かりずらい証明です．２項係数が奇数になる場合を具体例で説明する． $m=19$の場合を考えよう． $19=1+2+2^4=10011_{(2)}$ $1$から$9$までの数を$19$から引いたとき，繰り下がりが起こらないのは $1_{(2)},10_{(2)},11_{(2)}$ だけで， $_{19}C_1,_{19}C_2,_{19}C_3$ だけが奇数になる($_{19}C_{18},_{19}C_{17},_{19}C_{16}$は除く)． $_{19}C_4$を考えよう． $1+2+2^4=2^2+(1+2+2^2+2^3)$ において $\left[\dfrac{1+2+2^4}{2^3}\right] > \left[\dfrac{2^2}{2^3}\right]+\left[\dfrac{1+2+2^2+2^3}{2^3}\right]$ であるので$_{19}C_4$は偶数である． さらに，$2^4$で割った場合も考えれば$_{19}C_4$は$4$の倍数であることが分かる． すなわち$_{19}C_n$で奇数になる$n$は,$19$を２進数表示し，$n$を引いたとき繰り下がりの起こらない数である． ちなみに，２項係数が常に奇数というのは，何を引いても繰り下がりが起こらない，すなわち $111\cdots 1_{(2)}=2^k-1$ である． 証明をもう一度読んでみましょう． 問題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}}$は整数でない.すなわち $[\frac{q}{p^{k-1}}]=l$とおくと$q=lp^{k-1}+r \ (1\leqq r < p^{k-1})$より$[\frac{q-1}{p^{k-1}}]=l)$ $=\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\)を２進数表示すると，\(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(=2^5-1)$のとき任意の\(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\)の倍数ではない． この問題は整数の２進法の問題です．新課程では重要視されている分野です． ２進法表示を用いると比較的簡単に解決する問題をもう１題紹介します． 問題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)(3) $f(x)=a,\ \ 0\leqq a\leqq 1$ のとき $x=\dfrac{a}{2},1-\dfrac{a}{2}$ であるから $a_2=0,\dfrac{2}{3}$のとき $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 ,3\cdot 2^2)\cdots (2)$の答 これを繰り返せばよいから $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})\cdots (3)$の答 
(4)この問題は２進数を利用すると比較的容易に証明できる．$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$が存在する である． この証明を行おう． ２進数で表すと $\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$を２進数で表すと$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}$以上の連続する２項が限りなく現れるので収束しない． 以上で，収束する条件は$(\flat)$であることが証明された． 解説 ２進法を用いて解決したが，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})$をとり除く． 
この操作により取り除いた全体を$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の数を取り除くことを意味している． 以下取り除く数を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)}$ と考え，有限小数で最後が１のときは$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$が可算集合でないこと，すなわち可算個でない測度$0$の集合の存在を示したことです． その証明をしましょう． 背理法(対角線論法)を用います． $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$が可算集合でないことが証明された． (ガウス記号と方程式・不等式の項目終わり) 目次 |