トップ› 京都大学› 2001年› 理系第5問

京都大学 2001年理系第5問解説

方針・初手

$z_k$ は1の $p$ 乗根のうち $1$ 以外の $p-1$ 個のいずれかであることに着目します。 $n$ 個の積が $1$ になる条件（ロ）を扱うために、最初の $n-1$ 個を自由に選び、最後の1個で積を調整するという考え方で漸化式を導きます。最後の1個が $1$ になってはいけないという条件（イ）から、求める個数 $a_n$ に関する漸化式が得られます。

解法1

条件（イ）より、各 $z_k$ は方程式 $z^p = 1$ の解のうち $z = 1$ を除く $p-1$ 個の複素数のいずれかである。 $n \ge 2$ に対し、条件（イ）、（ロ）を満たす組の個数 $a_n$ を考える。

(1)

$n = 2$ のとき、条件（イ）を満たす $z_1$ の選び方は $p-1$ 通りある。 $z_1$ を1つ選んだとき、条件（ロ）より $z_1 z_2 = 1$ すなわち $z_2 = z_1^{-1}$ と定まる。このとき $z_2^p = (z_1^{-1})^p = (z_1^p)^{-1} = 1^{-1} = 1$ であり、また $z_1 \neq 1$ より $z_2 \neq 1$ となるため、自動的に $z_2$ も条件（イ）を満たす。したがって、$a_2 = p-1$ である。

次に $n = 3$ のときを考える。条件（イ）を満たす $z_1, z_2$ を自由に選ぶと、その選び方は $(p-1)^2$ 通りある。このとき、条件（ロ）$z_1 z_2 z_3 = 1$ より、$z_3 = (z_1 z_2)^{-1}$ とただ1つに定まる。

$z_3^p = (z_1 z_2)^{-p} = (z_1^p)^{-1} (z_2^p)^{-1} = 1$ であるため、$z_3$ が条件（イ）を満たさないのは $z_3 = 1$ となるときのみである。 $z_3 = 1 \iff z_1 z_2 = 1$ であり、これを満たす組 $(z_1, z_2)$ の個数は、上で求めた $a_2$ に等しい。よって、すべての選び方から $z_3 = 1$ となってしまう選び方を除いて、

$$ a_3 = (p-1)^2 - a_2 = (p-1)^2 - (p-1) = (p-1)(p-2) $$

(2)

$n+2$ 個の組 $(z_1, \cdots, z_{n+2})$ について考える。最初の $n+1$ 個の複素数 $z_1, \cdots, z_{n+1}$ を条件（イ）を満たすように自由に選ぶ。この選び方は $(p-1)^{n+1}$ 通りある。このとき、条件（ロ）$z_1 \cdots z_{n+1} z_{n+2} = 1$ より $z_{n+2} = (z_1 \cdots z_{n+1})^{-1}$ とただ1つに定まる。

$z_{n+2}^p = 1$ は常に満たされるので、$z_{n+2}$ が条件（イ）を満たさないのは $z_{n+2} = 1$ のとき、すなわち $z_1 \cdots z_{n+1} = 1$ のときである。 $z_1 \cdots z_{n+1} = 1$ を満たす組 $(z_1, \cdots, z_{n+1})$ の個数は、定義より $a_{n+1}$ 個である。したがって、全体の $(p-1)^{n+1}$ 通りから、不適となる $a_{n+1}$ 通りを除くことで $a_{n+2}$ が得られる。

$$ a_{n+2} = (p-1)^{n+1} - a_{n+1} $$

(3)

(2)で求めた漸化式より、$n \ge 2$ について

$$ a_{n+1} = -a_n + (p-1)^n $$

が成り立つ。この式の両辺を $(-1)^{n+1}$ で割ると、

$$ \frac{a_{n+1}}{(-1)^{n+1}} = \frac{a_n}{(-1)^n} - (1-p)^n $$

$$ \frac{a_{n+1}}{(-1)^{n+1}} - \frac{a_n}{(-1)^n} = - (1-p)^n $$

となるから、数列 $\left\{ \frac{a_n}{(-1)^n} \right\}$ の階差数列の第 $n$ 項は $-(1-p)^n$ である。したがって、$n \ge 3$ のとき、

$$ \frac{a_n}{(-1)^n} = \frac{a_2}{(-1)^2} + \sum_{k=2}^{n-1} \left\{ - (1-p)^k \right\} $$

$a_2 = p-1$ であり、右辺の和を等比数列の和の公式を用いて計算すると、

$$ \frac{a_n}{(-1)^n} = (p - 1) - \frac{(1-p)^2 \{1 - (1-p)^{n-2}\}}{1 - (1-p)} $$

$$ = (p - 1) - \frac{(p-1)^2 - (p-1)^2 (1-p)^{n-2}}{p} $$

ここで、$(p-1)^2 (1-p)^{n-2} = (1-p)^2 (1-p)^{n-2} = (1-p)^n$ であるから、

$$ \frac{a_n}{(-1)^n} = \frac{p(p-1) - (p-1)^2 + (1-p)^n}{p} $$

$$ = \frac{(p-1)\{p - (p-1)\} + (1-p)^n}{p} = \frac{p-1 + (1-p)^n}{p} $$

両辺に $(-1)^n$ を掛けると、

$$ a_n = \frac{(-1)^n (p-1) + (-1)^n (1-p)^n}{p} $$

$$ a_n = \frac{(-1)^n (p-1) + (p-1)^n}{p} $$

この式に $n=2$ を代入すると、

$$ a_2 = \frac{(-1)^2 (p-1) + (p-1)^2}{p} = \frac{p - 1 + p^2 - 2p + 1}{p} = p - 1 $$

となり、$n=2$ のときも成り立つ。

解説

「条件を満たす組の数」を漸化式を用いて求める典型的な数え上げ問題です。(1)の $a_3$ を求める過程で「最後の1つが自動的に決まるが、それが条件から外れる場合を引く」という考え方に気づくことができれば、(2)の漸化式も自然に導出できます。 (3)は1次非斉次の隣接2項間漸化式になります。両辺を $c^{n+1}$（今回は $(-1)^{n+1}$）で割って階差数列に帰着させる手法は定石なので、確実に処理できるようにしておきましょう。等比数列の和の計算において、底が $1-p$ なのか $p-1$ なのか、符号の扱いに気をつける必要があります。