こんにちは。
今回は、昨日から今日にかけて行われた東京大学の入学試験のうち、数学で唯一文系理系共通だった第4問を見ていきたいと思います。
問題
$n, k$ を, $1 \leqq k \leqq n$ を満たす整数とする。$n$ 個の整数
2^m \quad (m = 0, 1, 2, \cdots\cdots, n – 1)
$$
から異なる $k$ 個を選んでそれらの積をとる。$k$ 個の整数の選び方すべてに対しこのように積をとることにより得られる ${}_{n} 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
$$
である。
- $2$ 以上の整数 $n$ に対し, $a_{n,2}$ を求めよ。
- $1$ 以上の整数 $n$ に対し, $x$ についての整式
$$
f_n (x) = 1 + a_{n,1} x + a_{n,2} x^2 + \cdots\cdots + a_{n,n} x^n
$$を考える。$\frac{f_{n+1} (x)}{f_n (x)}$ と $\frac{f_{n+1} (x)}{f_n (2x)}$ を $x$ についての整式として表せ。
- $\frac{a_{n+1,k+1}}{a_{n,k}}$ を $n, k$ で表せ。
解き方
(1)
異なる $2$ 個の整数の選び方は、以下の表の 〇印の部分となります。
表は $n = 4$ の場合を示しています。
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | × | △ | △ | △ |
| 1 | 〇 | × | △ | △ |
| 2 | 〇 | 〇 | × | △ |
| 3 | 〇 | 〇 | 〇 | × |
$a_{n,2}$ は、表の〇印の部分をすべて足したものです。
これを求めるためには、まず表の組み合わせをすべて足し、そこから×印の部分を引き、さらに△印の部分を取り除くために $2$ で割ります。
表のすべての組み合わせの和は、以下で表されます。
表の×印の部分の和は、以下で表されます。
これらを用いて、$a_{n,2}$ は以下のように求められます。
a_{n,2} &=& \frac{1}{2} \left( \left( \sum_{k = 0}^{n – 1} 2^k \right)^2 – \sum_{k = 0}^{n – 1} 2^{2k} \right) \\
&=& \frac{1}{2} \left( (2^n – 1)^2 – \frac{1}{3} (2^{2n} – 1) \right) \\
&=& \frac{1}{2} \left( \frac{2}{3} \cdot 2^{2n} – 2 \cdot 2^n + \frac{4}{3} \right) \\
&=& \frac{1}{3} ( 2^{2n} – 3 \cdot 2^n + 2 ) \\
&=& \frac{1}{3} ( 2^n – 1 )( 2^n – 2 )
\end{eqnarray*}
$$
(2)
$n$ を固定して考えると、$a_{n,k}$ の定義から、$f_n (x)$ は次のように表されます。
\begin{eqnarray*}
f_n (x) &=& 1 + a_{n, 1} x + a_{n, 2} x^2 + \cdots + a_{n,n} x^n \\
&=& ( 2^0 x + 1 )( 2^1 x + 1 )(2^2 x + 1 ) \cdots ( 2^{n – 1} x + 1 )
\end{eqnarray*}
$$
このことに気づくと、問いの答えはすぐに求まります。
\frac{f_{n+1} (x)}{f_n (x)} = 2^n x + 1
$$
$$
\begin{eqnarray*}
\frac{f_{n+1} (x)}{f_n (2x)} &=& 2^0 x + 1 \\
&=& x + 1
\end{eqnarray*}
$$
(3)
問題の流れから (2)は誘導問題の可能性が高いので、(2)から求まった以下の関係式に注目します。
（比較しやすいように整式の形に直してあります）
\begin{eqnarray*}
f_{n+1} (x) &=& ( 2^n x + 1 ) f_n (x) &\qquad& \cdots ① \\
f_{n+1} (x) &=& ( x + 1 ) f_n (2x) &\qquad& \cdots ②
\end{eqnarray*}
$$
これらの左辺と右辺を比較します。簡略化のため、$x^{k + 1}$ の係数比較をします。
\begin{eqnarray*}
a_{n+1,k+1} &=& 2^n &a_{n,k}& &+& &a_{n,k+1}& \qquad \cdots ①’ \\
a_{n+1,k+1} &=& 2^k &a_{n,k}& &+& 2^{k + 1} &a_{n,k+1}& \qquad \cdots ②’
\end{eqnarray*}
$$
（表記簡略化のため、$a_{n,n+1} = 0$ としています）
この2式を連立して、不要な文字（ $a_{n,k+1}$ ）を消去します。
$$
\begin{eqnarray*}
( 2^{k + 1} – 1 ) a_{n+1,k+1} &=& 2^k ( 2^{n + 1} – 1 ) a_{n,k} \\
\frac{a_{n+1,k+1}}{a_{n,k}} &=& \frac{2^k ( 2^{n + 1} – 1 )}{2^{k + 1} – 1}
\end{eqnarray*}
$$
以上で全問終了となります。
最後に
第4問は、(1)からある程度難易度は高かったと思います。
仕組みが分かってしまうとすんなり解けるので、試験時間中に短時間で仕組みを理解できるかが勝負を分けたと思われます。
仕組みというのは、(1)ではすべての組み合わせの和が 和の2乗で表せること、(2)では関数 $f$ の構造のことです。
これらの考え方は、約数の総和を求める方法や二項定理などに似ていて、そのような基礎的な考え方を少し応用することができるかを問う良い問題だったと思います。
実際の試験では、今回の解答の方法を思いつかなくても、漸化式や数学的帰納法で解いても良いでしょう。
また気が向いたら数学に関する話を載せようと思います。
それでは、また。
コメント一覧