問題
以下の問いに答えよ。
\((1)\) 正の奇数\(K, L\)と正の整数\(A, B\)が\(KA = LB\)を満たしているとする。\(K\)を\(4\)で割った余りが\(L\)を\(4\)で割った余りと等しいならば、\(A\)を\(4\)で割った余りは\(B\)を\(4\)で割った余りと等しいことを示せ。
\((2)\) 正の整数\(a, b\)が\(a>b\)を満たしているとする。
このとき\(A = {_{4a+1}\mathrm{C}_{4b+1}}, \ B = {_a\mathrm{C}_b}\)に対して\(KA = LB\)となるような正の奇数\(K, L\)が存在することを示せ。
\((3)\) \(a, b\)は\((2)\)の通りとし、さらに\(a-b\)が\(2\)で割り切れるとする。\({_{4a+1}\mathrm{C}_{4b+1}}\)を\(4\)で割った余りは\({_a\mathrm{C}_b}\)を\(4\)で割った余りと等しいことを示せ。
\((4)\) \({_{2021}\mathrm{C}_{37}}\)を\(4\)で割った余りを求めよ。
方針
誘導に従うが、それでも難しい。
解答
\((1)\) \(K, L\)は奇数なので\(4\)で割った余りは\(1\)か\(-1\)である。\(K\)と\(L\)を\(4\)で割った余りは等しいので、どちらの場合でも\(A, B\)を\(4\)で割った余りは等しくなる。より詳しくやると、\(K, L\)を\(4K^{\prime}\pm1, L = 4L^{\prime}\pm1\)（複号同順）として、\(A, B\)を\(4\)で割った余りを\(c, d\)と置いて、\(A = 4A^{\prime}+c, B = 4B^{\prime}+d\)とすると、$$KA = LB$$ $$(4K^{\prime}\pm1)(4A^{\prime}+c) = (4L^{\prime}\pm1)(4B^{\prime}+d)$$となり、両辺とも最後の展開項以外はすべて\(4\)で割り切れるので、\(\pm c\)と\(\pm d\)を\(4\)で割った余りは等しくなり、\(A, B\)を\(4\)で割った余りは等しくなるという次第である。
\((2)\) 一般に、整数\(n\)に対して、\(n!\)の中に含まれる素因数\(k\)の個数は$$\left[\frac{n}{k}\right] + \left[\frac{n}{k^2}\right] + \left[\frac{n}{k^3}\right] + \cdots$$となる。ただし\([\ ]\)はガウス記号で、\([x]\)は実数\(x\)に対して\(x\)を超えない最大の整数を表す。今、\(a!,\ b!,\ (a-b)!\)に含まれる\(2\)の個数をそれぞれ\(p, q, r\)とする。すなわち、$$p = \left[\frac{a}{2}\right] + \left[\frac{a}{2^2}\right] + \left[\frac{a}{2^3}\right] + \cdots$$ $$q = \left[\frac{b}{2}\right] + \left[\frac{b}{2^2}\right] + \left[\frac{b}{2^3}\right] + \cdots$$ $$r = \left[\frac{a-b}{2}\right] + \left[\frac{a-b}{2^2}\right] + \left[\frac{a-b}{2^3}\right] + \cdots$$である。こうすると、\((4a)!, \ (4b)!,\ {4(a-b)}!\)に含まれる\(2\)の個数をそれぞれ\(p^{\prime}, q^{\prime}, r^{\prime}\)とすると、$$p^{\prime} = \left[\frac{4a}{2}\right] + \left[\frac{4a}{2^2}\right] + \left[\frac{4a}{2^3}\right] + \cdots$$ $$ = \left[2a\right] + \left[a\right] + \left[\frac{a}{2}\right] + \cdots$$ $$ = 2a + a + p$$ $$ = 3a + p$$あり、同様にして$$q^{\prime} = 3b + q$$ $$r^{\prime} = 3(a-b) + r$$となる。\({_a\mathrm{C}_b} = \frac{a!}{b!(a-b)!}\)だから、これに含まれる\(2\)の個数は\(p-q-r\)である。\({_{4a+1}\mathrm{C}_{4b+1}}\)に含まれる\(2\)の個数は$$p^{\prime}-q^{\prime}-r^{\prime} = 3a+p -(3b+q) – {3(a-b)+r}$$ $$ = p-q-r$$であり、\({_a\mathrm{C}_b}\)に含まれる\(2\)の数と等しい。（\(4a+1, 4b+1\)がそれぞれ奇数で、\((4a+1)-(4b+1)=4(a-b)\)であることに注意）。以上より、適当な奇数\(K, L\)を用いて\(KA = LB\)とすることができる。
\((3)\) \({_{4a+1}\mathrm{C}_{4b+1}}\)の中から\({_{a}\mathrm{C}_{b}}\)を括りだす。$${_{4a+1}\mathrm{C}_{4b+1}} = \frac{(4a+1)\cdot 4a\cdot (4a-1)\cdots {4(a-b)+1}}{(4b+1)\cdot 4b\cdot(4b-1)\cdots 1}$$ $$ = \frac{a\cdot (a-1)\cdots {(a-b)+1}}{b\cdot (b-1)\cdots 1}\times$$ $$\frac{(4a+1)\cdot(4a-1)\cdot(4a-2)\cdot(4a-3)\cdot(4a-5)\cdots {4(a-b)+2}\cdot{4(a-b)+1}}{(4b+1)\cdot(4b-1)\cdot(4b-2)\cdot(4b-3)\cdot(4b-5)\cdots 2\cdot1}$$ $$ = {_{a}\mathrm{C}_{b}}\times \frac{(4a+1)(4a-1)(2a-1)\cdots {4(a-b)+1}}{(4b+1)(4b-1)(2b-1)\cdots 1}$$なので、$$K = (4b+1)(4b-1)(2b-1)(4b-3)(4b-5)(2a-3)\cdots 5\cdot3\cdot1,$$ $$L = (4a+1)(4a-1)(2a-1)(4a-3)(4a-5)(2a-3)\cdots$$ $$\times{4(a-b)+5}{4(a-b)+3}\cdot{2(a-b)+1}\cdot{4(a-b)+1}$$となる。任意の整数\(r\)について\(4a+r\)と\(4b+r\)を\(4\)で割った余りは等しく、\((2a+r)-(2b+r) = 2(a-b)\)が\(4\)で割り切れることから、\(2a+r\)と\(2b+r\)を\(4\)で割った余りは等しい。\(K, L\)の各項を見比べると、\(K, L\)を\(4\)で割った余りは等しい。\((1)\)から\(A, B\)を\(4\)で割った余りも等しくなる。
\((4)\) \((3)\)からmodを\(4\)として$${_{2021}\mathrm{C}_{37}} \equiv {_{505}\mathrm{C}_{9}}$$ $$\equiv {_{126}\mathrm{C}_{2}}$$ $$ = \frac{126\cdot 125}{2\cdot 1}$$ $$ = 63 \cdot 125$$ $$\equiv 3 \cdot 1$$ $$ = 3$$である。よって、\({_{2021}\mathrm{C}_{37}}\)を\(4\)で割った余りは
\(3\)
である。
解説
\((2)\)が難しい。素直にやると、$${_{4a+1}\mathrm{C}_{4b+1}} = \frac{(4a+1)!}{(4b+1){4(a-b)}!}$$ $$ = \frac{(4a+1)4a(4a-1)\cdots}{(4b+1)4b(4b-1)\cdots}$$として、ここから\({_a\mathrm{C}_b}\)を括りだすことになる。解答では、二項係数の中に含まれる素因数\(2\)の個数に着目している。
ガウス記号は便利なので覚えておくと良い。階乗の中に含まれる素因数の個数についてだが、例えば\(7!\)の中の素因数\(2\)の個数を考えると、\(2\)の倍数は\(\left[\frac{7}{2}\right]\)個、\(4\)の倍数は\(\left[\frac{7}{4}\right]\)個、\(8\)の倍数は\(\left[\frac{7}{8}\right]\)個、というようになるが、ある大きさ以上になると\(\left[\frac{7}{2^l}\right]\)はすべて\(0\)になるので、考える必要がなくなるという訳だ。
また、\((4a+1)!\)を持ち出すと、\(\left[\frac{4a+1}{2}\right]\)などを相手にしなくてはならず、考えにくい。どうせ\(4a+1\)は奇数であることが分かっているので、\((4a)!\)までの\(2\)の個数を考えれば十分である。解答の過程から、\({_{a}\mathrm{C}_{b}}, \ {_{2a}\mathrm{C}_{2b}},\ {_{4a}\mathrm{C}_{4b}},\ {_{8a}\mathrm{C}_{8b}}, \cdots\)に含まれる素因数\(2\)の数はすべて等しいことがわかる。
二項係数の偶奇については東京大学は好物のようで、例えば以下のような問題がある。
\((1)\) \(k\)を自然数とする。\(m = 2^k\)とおくとき、\(0<n<m\)を満たすすべての整数\(n\)について、二項係数\({_m\mathrm{C}_n}\)は偶数であることを示せ。
\((2)\) 以下の条件を満たす自然数\(m\)をすべて求めよ。
条件：\(0\leq n\leq m\)を満たすすべての整数\(n\)について二項係数\({_m\mathrm{C}_n}\)は奇数である。（1999年度理系）
次は\(2015\)年度の出題である。
\(m\)を\(2015\)以下の正の整数とする。\({_{2015}\mathrm{C}_{m}}\)が偶数となる最小の\(m\)を求めよ。
\((2)\)では\({_{4a+1}\mathrm{C}_{4b+1}}, \ {_a\mathrm{C}_b}\)の具体的な形を相手にせずに済んだが、\((3)\)では結局\(K, \ L\)を具体的に求めなければならない。そういった意味では、大学入試問題としては極めて解法の限定された問題である。
なお、一般に素数\(p\)と整数\(a, b\)に対して、$${_{ap}\mathrm{C}_{bp}} \equiv {_a\mathrm{C}_b}\ (mod \ p^2)$$であることが知られている。これを用いると、\({_{a}\mathrm{C}_{b}}\)と\({_{2a}\mathrm{C}_{2b}}\)を\(2^2 = 4\)で割った余りは等しく、\({_{2a}\mathrm{C}_{2b}}\)と\({_{4a}\mathrm{C}_{4b}}\)を\(4\)で割った余りも等しい。$${_{4a+1}\mathrm{C}_{4b+1}} = \frac{4a+1}{4b+1}{_{4a}\mathrm{C}_{4b}}$$であり、これを$$(4b+1){_{4a+1}\mathrm{C}_{4b+1}} = (4a+1){_{4a}\mathrm{C}_{4b}}$$と変形すると、\(4a+1, \ 4b+1\)を\(4\)で割った余りは等しいので、\((1)\)から\({_{4a+1}\mathrm{C}_{4b+1}}\)と\({_{4a}\mathrm{C}_{4b}}\)を\(4\)で割った余りが等しいことがわかる。結局、\({_{4a+1}\mathrm{C}_{4b+1}}\)と\({_{a}\mathrm{C}_{b}}\)を\(4\)で割った余りが等しいことが言える。
\((4)\) \(2021 = 4\cdot505+1, \ 37 = 4\cdot9+1\)などと変形して、\((3)\)の結果をどんどん利用して計算できるところまで簡単にしていく。採点基準は明らかではないが、\((2), \ (3)\)を解かずに\((4)\)だけ解いても点数は低いものと考えられる。
コメント