東京大学 1982年 文系 第4問 解説

方針・初手

点列を生成する手続きにおいて、行列 $A$ または $B$ を掛ける操作が $x_n + y_n$ の値にどのような影響を与えるかを調べることが鍵である。まずは具体的に $P_1, P_2$ を計算して操作の規則性を把握し、一般の $n$ について $x_n + y_n$ の漸化式を立てる。

解法1

(1)

点 $P_0$ の座標は $(1, 1)$ であり、$x_0 + y_0 = 2$ である。 $2 \geqq \frac{1}{100}$ より(イ)の条件を満たすため、$P_1$ は $A P_0$ または $B P_0$ のどちらかである。

$$ A P_0 = \begin{pmatrix} \frac{1}{2} & -\frac{1}{2} \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \end{pmatrix} $$

$$ B P_0 = \begin{pmatrix} 1 & 0 \\ -\frac{1}{2} & \frac{1}{2} \end{pmatrix} \begin{pmatrix} 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix} $$

よって、$P_1$ は $(0, 1)$ または $(1, 0)$ である。

次に、$P_1(0, 1)$ のとき、$x_1 + y_1 = 1 \geqq \frac{1}{100}$ より(イ)を満たす。

$$ A \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} -\frac{1}{2} \\ 1 \end{pmatrix}, \quad B \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ \frac{1}{2} \end{pmatrix} $$

$P_1(1, 0)$ のときも、$x_1 + y_1 = 1 \geqq \frac{1}{100}$ より(イ)を満たす。

$$ A \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} \frac{1}{2} \\ 0 \end{pmatrix}, \quad B \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ -\frac{1}{2} \end{pmatrix} $$

したがって、$P_2$ として可能な点の座標は $\left(-\frac{1}{2}, 1\right), \left(0, \frac{1}{2}\right), \left(\frac{1}{2}, 0\right), \left(1, -\frac{1}{2}\right)$ の4点である。 これらは $xy$ 平面上の直線 $x + y = \frac{1}{2}$ 上に等間隔に並ぶ4点であり、これらを座標平面にプロットすることで図示される。

(2)

操作によって得られる $x_{n+1} + y_{n+1}$ の値を調べる。 行列 $A$ を用いた場合、

$$ \begin{pmatrix} x_{n+1} \\ y_{n+1} \end{pmatrix} = \begin{pmatrix} \frac{1}{2}x_n - \frac{1}{2}y_n \\ y_n \end{pmatrix} $$

であるから、

$$ x_{n+1} + y_{n+1} = \left(\frac{1}{2}x_n - \frac{1}{2}y_n\right) + y_n = \frac{1}{2}(x_n + y_n) $$

行列 $B$ を用いた場合、

$$ \begin{pmatrix} x_{n+1} \\ y_{n+1} \end{pmatrix} = \begin{pmatrix} x_n \\ -\frac{1}{2}x_n + \frac{1}{2}y_n \end{pmatrix} $$

であるから、

$$ x_{n+1} + y_{n+1} = x_n + \left(-\frac{1}{2}x_n + \frac{1}{2}y_n\right) = \frac{1}{2}(x_n + y_n) $$

よって、$A, B$ のどちらを選んでも、常に $x_{n+1} + y_{n+1} = \frac{1}{2}(x_n + y_n)$ が成り立つ。 数列 $\{x_n + y_n\}$ は初項 $x_0 + y_0 = 2$、公比 $\frac{1}{2}$ の等比数列であるため、

$$ x_n + y_n = 2 \left(\frac{1}{2}\right)^n = \left(\frac{1}{2}\right)^{n-1} $$

となる。

(3)

手続きにおいて $A, B$ の選択肢が生じる(イ)の条件は $x_n + y_n \geqq \frac{1}{100}$ である。(2)の結果を用いると、

$$ \left(\frac{1}{2}\right)^{n-1} \geqq \frac{1}{100} \iff 2^{n-1} \leqq 100 $$

$2^6 = 64$、$2^7 = 128$ であるから、この不等式を満たす最大の整数 $n$ は $n-1 = 6$ より $n = 7$ である。 したがって、$n = 0, 1, 2, \dots, 7$ のとき（$P_1$ から $P_8$ までを順に決定するとき）は(イ)の条件が適用され、毎回 $A, B$ の2通りの操作を選ぶことができる。 一方で $n = 8, 9$ のとき（$P_9, P_{10}$ を決定するとき）は $x_n + y_n < \frac{1}{100}$ となり、(ロ)の条件により操作は $A$ のみに確定する。

操作の選び方の総数は、

$$ 2^8 \times 1 \times 1 = 256 \text{ 通り} $$

である。次に、これら256通りの異なる操作列が、すべて異なる点 $P_{10}$ に到達することを示す。 行列 $A, B$ による $x$ 座標の変化に着目すると、

$$ A \begin{pmatrix} x_n \\ y_n \end{pmatrix} = \begin{pmatrix} x_n - \frac{1}{2}(x_n + y_n) \\ y_n \end{pmatrix} $$

$$ B \begin{pmatrix} x_n \\ y_n \end{pmatrix} = \begin{pmatrix} x_n \\ y_n - \frac{1}{2}(x_n + y_n) \end{pmatrix} $$

となる。第 $k$ 回目の操作（$P_{k-1}$ から $P_k$ を得るとき）において、$A$ を選んだとき $c_k = 1$、$B$ を選んだとき $c_k = 0$ とすると、$x_k$ は次のように表せる。

$$ x_k = x_{k-1} - c_k \frac{1}{2} (x_{k-1} + y_{k-1}) = x_{k-1} - c_k \left(\frac{1}{2}\right)^{k-1} $$

これを $k=1$ から $10$ まで繰り返し適用すると、$x_{10}$ の値は

$$ x_{10} = x_0 - \sum_{k=1}^{10} c_k \left(\frac{1}{2}\right)^{k-1} = 1 - \sum_{k=1}^{10} \frac{c_k}{2^{k-1}} $$

となる。右辺の和は各桁が $c_k \in \{0, 1\}$ である2進小数展開に対応するため、数列 $\{c_k\}$ が異なれば $x_{10}$ の値も必ず異なる。 よって、256通りの操作列はすべて異なる $x$ 座標を持つ点を与えるため、重複して同じ点に到達することはない。 以上より、$P_{10}$ として可能な点の個数は256個である。

解説

一見すると複雑な行列の変換であるが、$x+y$ という和を評価することで、変換が非常にシンプルな性質を持つことが見抜ける良問である。 行列による変換を幾何学的に解釈すると、点 $(x, y)$ から直線 $x+y=0$ に平行な方向へ移動させる操作となっている。また、到達点の重複がないことを示すために、各ステップでの移動量を2進数展開のアナロジーで説明する論理構成が鮮やかである。(3)で場合の数を求めた後、「異なる操作が同じ点に行き着かないか」という単射性の確認を忘れないようにしたい。

答え

(1)

$P_2$ の座標は $\left(-\frac{1}{2}, 1\right), \left(0, \frac{1}{2}\right), \left(\frac{1}{2}, 0\right), \left(1, -\frac{1}{2}\right)$ （図示は直線 $x+y=\frac{1}{2}$ 上のこれらの4点）

(2)

$x_n + y_n = \left(\frac{1}{2}\right)^{n-1}$

(3)

$256$ 個