東京大学 1973年 理系 第2問 解説

方針・初手

$x_i$ が $0, 1, 2$ のいずれかの値しかとらないという強い制約を活かす。各 $x_i$ がどの値をとるかの「個数」に注目して $f_k$ を表す方針と、$x_i = 0, 1, 2$ で成り立つ「恒等式」を作って和をとる方針の2通りが考えられる。

解法1

$n$ 個の変数 $x_1, x_2, \cdots\cdots, x_n$ のうち、 値が $0$ であるものの個数を $n_0$ 値が $1$ であるものの個数を $n_1$ 値が $2$ であるものの個数を $n_2$ とする。

任意の自然数 $k$ に対して、$0^k = 0, 1^k = 1, 2^k = 2^k$ であるから、$f_k$ の定義より、

$$ f_k = \sum_{i=1}^n {x_i}^k = 0^k \cdot n_0 + 1^k \cdot n_1 + 2^k \cdot n_2 = n_1 + 2^k n_2 $$

が成り立つ。

この関係式を用いて、与えられた $f_1, f_2$ を書き換えると、

$$ f_1 = n_1 + 2n_2 $$

$$ f_2 = n_1 + 4n_2 $$

となる。これを $n_1, n_2$ についての連立方程式とみて解く。第2式から第1式を引くと、

$$ f_2 - f_1 = 2n_2 $$

$$ n_2 = \frac{f_2 - f_1}{2} $$

となる。これを第1式に代入して $n_1$ を求めると、

$$ n_1 = f_1 - 2n_2 = f_1 - (f_2 - f_1) = 2f_1 - f_2 $$

となる。

求めた $n_1, n_2$ を $f_k = n_1 + 2^k n_2$ に代入する。

$$ f_k = (2f_1 - f_2) + 2^k \cdot \frac{f_2 - f_1}{2} $$

$$ = 2f_1 - f_2 + 2^{k-1} (f_2 - f_1) $$

$$ = (2 - 2^{k-1})f_1 + (2^{k-1} - 1)f_2 $$

以上より、$f_k$ を $f_1, f_2$ を用いて表すことができた。

解法2

各 $x_i$ は $0, 1, 2$ のいずれかの値をとるため、任意の自然数 $k$ に対して、

$$ {x_i}^k = A {x_i}^2 + B x_i + C $$

を満たすような定数 $A, B, C$ を探す。

$x_i = 0$ を代入すると、

$$ 0 = C $$

$x_i = 1$ を代入すると、

$$ 1 = A + B $$

$x_i = 2$ を代入すると、

$$ 2^k = 4A + 2B $$

これらを連立させて $A, B$ を求める。$1 = A + B$ の両辺を2倍して、

$$ 2 = 2A + 2B $$

$2^k = 4A + 2B$ からこの式を辺々引くと、

$$ 2^k - 2 = 2A $$

$$ A = 2^{k-1} - 1 $$

このとき、$B$ は、

$$ B = 1 - A = 1 - (2^{k-1} - 1) = 2 - 2^{k-1} $$

となる。

したがって、$i$ によらず、任意の $x_i \in \{0, 1, 2\}$ に対して、以下の恒等式が成り立つ。

$$ {x_i}^k = (2^{k-1} - 1){x_i}^2 + (2 - 2^{k-1})x_i $$

この式の両辺について、$i = 1$ から $n$ までの和をとる。

$$ \sum_{i=1}^n {x_i}^k = (2^{k-1} - 1) \sum_{i=1}^n {x_i}^2 + (2 - 2^{k-1}) \sum_{i=1}^n x_i $$

条件の $f_k = \sum_{i=1}^n {x_i}^k$、$f_1 = \sum_{i=1}^n x_i$、$f_2 = \sum_{i=1}^n {x_i}^2$ を適用して、

$$ f_k = (2 - 2^{k-1})f_1 + (2^{k-1} - 1)f_2 $$

を得る。

解説

変数が離散的な有限個の値しかとらない問題における典型的な処理を問う問題である。

解法1は、値の種類が $0, 1, 2$ の3種類であることを利用し、それぞれの値をとる「個数」を変数として設定する自然なアプローチである。未知の個数が $n_1, n_2$ の2つであるため、与えられた2つの式 ($f_1, f_2$) から完全に決定できるという見通しが立つ。

解法2は、変数が特定の値しかとらないことから、「その値でのみ成立する多項式の等式」を構成するアプローチである。計算量が少なく、和の記号 $\Sigma$ の線形性を美しく活用できるため、より高度な応用問題でも役立つ強力な手法である。

答え

$$ f_k = (2 - 2^{k-1})f_1 + (2^{k-1} - 1)f_2 $$