２のべき乗がいっぱい – 2020年東大 数学 第4問
2020年東大 数学 第4問 は、2のべき乗が怒涛のようにあたりを埋め尽くす、取り付く島のない難問です。問題文は以下の通りです。
n,k を、 1 \leqq k \leqq n を満たす整数とする。 n 個の整数 2^m(m=0,1,2, \cdots,n-1) から異なる k 個を選んでそれらの積をとる。 k 個の整数の選び方すべてに対しこのように積をとることにより得られる {}_n \mathrm{C}_k 個の整数の和を a_{n,k} とおく。例えば、 a_{4,3} = 2^0 \cdot 2^1 \cdot 2^2+2^0 \cdot 2^1 \cdot 2^3+2^0 \cdot 2^2 \cdot 2^3+2^1 \cdot 2^2 \cdot 2^3 =120 である。
(1) 2以上の整数 n に対し、 a_{n,2} を求めよ。
(2) 1以上の整数 n に対し、 x についての整式
f_n(x) = 1 + a_{n,1} x + a_{n,2} x^2 + \cdots + a_{n,n} x^n
を考える。 \frac{f_{n+1}(x)}{f_n (x)} と \frac{f_{n+1}(x)}{f_n (2x)} を x についての整式として表せ。
(3) \frac{a_{n+1,k+1}}{a_{n,k}} を n,k で表せ。
本問もまた、「どうすりゃいいのか見当もつかない」系の問題です。とりあえず小問1に取り掛かります。
2020年東大 数学 第4問 小問１の解法
n 個の要素から異なる2個を取り出して掛け合わせ、その和を足しこむというのは、どこかで見たことがあります。
そう、1次式の2乗の展開です。たとえば、
\begin{aligned}
& (a+b+c)^2 \\
&= a^2+b^2 +c^2 \\
&+ 2(ab+bc+ac)
\end{aligned}の ab+bc+ac が正にそれです。
これを、 1+2^1+2^2+ \cdots +2^{n-1} に適用すると、
\begin{aligned}
& a_{n,2} = \frac{1}{2} \{ (1+2^1+2^2+ \cdots +2^{n-1})^2 \\
& \text{ }- (1^2+2^2+2^4+ \cdots +2^{2(n-1)}) \} \\
& \text{ } = \frac{1}{2} \left \{ \left (\sum_{m=0}^{n-1}2^m \right )^2 - \sum_{m=0}^{n-1}4^m \right\} \\
& \text{ } = \frac{1}{2} \left \{ ( 2^n -1 )^2 - \frac{4^n -1}{3} \right\} \\
& \text{ } = \frac{1}{2} ( 2^n -1 ) \left \{ ( 2^n -1 ) - \frac{2^n +1}{3} \right\} \\
& \text{ } = \frac{1}{6} ( 2^n -1 ) \{ ( 3 \cdot2^n -3 ) - (2^n +1)
\} \\
& \text{ } = \frac{1}{6} ( 2^n -1 ) ( 2 \cdot2^n -4 )
\\
& \text{ } = \frac{2}{3} ( 2^n -1 ) ( 2^{n-1} -1 )
\\
\end{aligned}を得ます。
2020年東大 数学 第4問 小問２の解法
解と係数の関係から着想を得て、 f_n(x) の具体的な式を求める
小問1で1次式の2乗がうまくいったなら、 a_{n,k } なら k 乗か？と言う発想は単純すぎて、ダメそうです。
しかし、よく考えてみると、 a_{n,k} というのは、代数方程式における解と係数の関係式に似ています。
たとえば x の3次式において、
\begin{aligned}
& (x+a)(x+b)(x+c) \\
& = x^3 \\
&+(a+b+c)x^2 \\
&+ (ab+ac+bc)x \\
&+abc
\end{aligned}なので、 a= 2^0,b=2^1,c=2^2 とおくと、
\begin{aligned}
& (x+2^0)(x+2^1)(x+2^2) \\
& = x^3 +a_{3,1}x^2 + a_{3,2}x +a_{3,3}
\end{aligned}です。 x の係数のかかり方がちょっと違うので、式の左辺で x のほうに 2^k をかけてやれば、
\begin{aligned}
& (2^0x+1)(2^1x+1)(2^2x+1) \\
& = 1 +a_{3,1}x + a_{3,2}x^2 +a_{3,3}x^3 \\
& = f_3(x)
\end{aligned}です。
これを一般の n \geqq 2 に拡張して、
f_n(x) = \prod_{k=0}^{n-1}(2^kx+1)が成り立ちます。
東大の入試だし、これくらいなら明らかであると押し切っていいような気もしますが、念のためにこれを数学的帰納法で証明します。
すでに見たように、 n =3 のときは成り立ちますが、明らかに n =2 の時も成り立ちます。
n =m (m \geqq 2 ) のときに
f_m(x) = \prod_{k=0}^{m-1}(2^kx+1)が成り立つと仮定すると、
\begin{aligned}
&(2^{m}x + 1)f_m(x)\\
= &(2^{m}x + 1)(1+ \sum_{k=1}^m a_{m,k} x^k) \\
= & 2^{m}x + \sum_{k=1}^{m} 2^{m}a_{m,k} x^{k+1} \\
& +1+ \sum_{k=1}^m a_{m,k} x^k \\
= &2^{m}x + \sum_{k=2}^{m+1} 2^{m}a_{m,k-1} x^{k} \\
& +1+ \sum_{k=1}^m a_{m,k} x^k \\
= & 2^{m}x +2^{m}a_{m,m} x^{m+1} \\
&+ \sum_{k=2}^{m} 2^{m}a_{m,k-1} x^{k} \\
& +1+ a_{m,1} x+\sum_{k=2}^m a_{m,k} x^k \\
= & 1+(a_{m,1} + 2^{m})x \\
&+ \sum_{k=2}^m (2^{m}a_{m,k-1} + a_{m,k})x^k \\
&+ 2^{m}a_{m,m} x^{m+1}
\end{aligned}となりますが、 a_{n,k} の定義から明らかに
\begin{aligned}
&a_{m,1} + 2^{m} = a_{m+1,1} \\
&2^{m}a_{m,k-1} + a_{m,k} = a_{m+1,k} \\
& \text{ } (2 \leqq k \leqq m) \\
&2^{m}a_{m,m} = a_{m+1,m+1}
\end{aligned}なので、
\begin{aligned}
& (2^{m+1}x + 1)f_m(x) \\
& = 1+ \sum_{k=1}^{m+1} a_{m+1,k} x^k \\
& = f_{m+1}(x)
\end{aligned}が成り立ちます。よって帰納法の仮定により、
f_{m+1}(x) = \prod_{k=0}^{m}(2^kx+1)が成り立ちます。ゆえに n \geqq 2 のとき
f_n(x) = \prod_{k=0}^{n-1}(2^kx+1)が成り立つことが示せました。
整式を導出する
これまでの推論からすでに明らかなように、
\frac{f_{n+1}(x)}{f_n(x)} = 2^nx+1です。また、
\begin{aligned}
&\frac{f_{n+1}(x)}{f_n(2x)} = \frac{\prod_{k=0}^{n}(2^kx+1)}{\prod_{k=0}^{n-1}(2^k \cdot 2x+1)} \\
& \text{ } = \frac{\prod_{k=0}^{n}(2^kx+1)}{\prod_{k=0}^{n-1}(2^{k +1}x+1)} \\
& \text{ } = \frac{\prod_{k=0}^{n}(2^kx+1)}{\prod_{k=1}^{n}(2^{k }x+1)} \\
& \text{ } = x+1
\end{aligned}です。
2020年東大 数学 第4問 小問３の解法
小問1および小問2は、代数方程式の解と係数の関係に着目することで、比較的容易に解くことが出来ましたが、小問3の方針がすぐには浮かびません。小問1や小問2が小問3への分かりやすい誘導になっていないことも、厳しさを倍加させています。
整式それ自体ではなく、係数に関する問題なので、小問2はそのままでは使えそうにないし、どうしようかとかんがえていましたが、そういえば小問2の証明過程で、係数に関する式が出てきたことを思い出しました。
すなわち、
\begin{aligned}
&2^{m}a_{m,k-1} + a_{m,k} = a_{m+1,k} \\
& \text{ } (2 \leqq k \leqq m) \\
\end{aligned}です。
m \rightarrow n, k \rightarrow k+1 と置き換えて
\begin{aligned}
& a_{n+1, k+1} = 2^na_{n,k}+ a_{n,k+1} \\
& \text{ } (1 \leqq k \leqq n-1)\\
& \text{ } \cdots (1)
\end{aligned}です。右辺の a_{n,k+1} が邪魔ですが、小問2で証明した式のもう一つの方
\begin{aligned}
&\frac{f_{n+1}(x)}{f_n(2x)} = x+1
\end{aligned}から何かが導出できるかもしれません。
そこで上の式の分母を払ってみます。
\begin{aligned}
&f_{n+1}(x) = (x+1)f_n(2x)
\end{aligned}両辺の x^k の係数を比較すると
\begin{aligned}
& a_{n+1,k+1} = 2^k a_{n, k} + 2^{k+1}a_{n,k+1} \\
& \text{ } (1 \leqq k \leqq n-1) \\
& \text{ } \cdots (2)
\end{aligned}を得ます。式(1)の両辺に 2^{k+1} を掛けて、式(2)を引くことにより、
\begin{aligned}
& (2^{k+1} -1)a_{n+1,k+1} = (2^{n+k+1} -2^k )a_{n, k} \\
& \text{ }(1 \leqq k \leqq n-1) \\
\end{aligned}が成り立ちます。したがって、
\begin{aligned}
& a_{n+1,k+1} = 2^k\frac{2^{n+1} -1}{2^{k+1} -1}a_{n, k} \\
& \text{ }(1 \leqq k \leqq n-1) \\
\end{aligned}が成り立ちます。上式は k=n の時も成り立つので、
\begin{aligned}
& \frac{a_{n+1,k+1} } {a_{n, k} }= 2^k\frac{2^{n+1} -1}{2^{k+1} -1} \\
& \text{ } (1 \leqq k \leqq n) \\
\end{aligned}となります。
解法のポイント
a_{n,k} が代数方程式の解と係数の関係に似ていると気づくことが、ポイントです。これがあると、小問1および小問2は割と容易に解けると思います。
また、小問3は、恒等式の係数が両辺で一致することを使おうと気が付けば、こちらも何とかなると思います。
この手の気づきは、対称式に関する問題を多く解くと、得られやすくなると思います。たくさん問題を解いて、感覚を養うようにして見てください。