トップ› 名古屋大学› 1987年› 文系第3問

名古屋大学 1987年文系第3問解説

方針・初手

硬貨を投げて進む距離が、表なら2、裏なら1と決まっているため、「表が何回出たか」に注目して進んだ合計距離を計算する方針が最も簡明である。また、各頂点間の移動を状態遷移と見なし、漸化式を立てて解くこともできる。(2) のように試行回数が増えた場合は、漸化式から対称性や周期性を見出すとよい。

解法1

$n$ 回硬貨を投げる反復試行を考える。表が $k$ 回（$0 \le k \le n$）出たとすると、裏は $n-k$ 回出る。このとき、進む距離の合計 $L$ は

$$L = 2k + 1 \cdot (n-k) = n + k$$

となる。頂点 $A$ から出発し、最後に $A$ にいるための条件は、合計距離 $L$ が4の倍数になることである。すなわち、ある整数 $m$ を用いて

$$n + k = 4m$$

と表されることである。

(1)

$n=3$ のとき、$L = 3+k$ であり、$0 \le k \le 3$ である。この範囲で $3+k$ が4の倍数となるのは、$3+k = 4$ すなわち $k=1$ のときのみである。したがって、求める場合の数は3回のうち表が1回出る場合の数に等しく、

$${}_{3}\mathrm{C}_{1} = 3$$

より、3通りである。

(2)

$n=10$ のとき、$L = 10+k$ であり、$0 \le k \le 10$ である。この範囲で $10+k$ が4の倍数となるのは、

$$10+k = 12, 16, 20$$

のいずれかである。これらを満たす $k$ の値は、それぞれ

$$k = 2, 6, 10$$

である。したがって、求める場合の数は10回のうち表が2回、6回、10回出る場合の数の和に等しく、

$${}_{10}\mathrm{C}_{2} + {}_{10}\mathrm{C}_{6} + {}_{10}\mathrm{C}_{10} = \frac{10 \cdot 9}{2 \cdot 1} + \frac{10 \cdot 9 \cdot 8 \cdot 7}{4 \cdot 3 \cdot 2 \cdot 1} + 1 = 45 + 210 + 1 = 256$$

より、256通りである。

解法2

各頂点にいる場合の数についての漸化式を立てる。 $n$ 回硬貨を投げた後に頂点 $A, B, C, D$ にいる場合の数を、それぞれ $a_n, b_n, c_n, d_n$ とする。頂点の並びは時計回りに $A, B, C, D$ であり、表なら2つ前、裏なら1つ前の頂点から移動してくるため、以下の漸化式が成り立つ。

$$ \begin{aligned} a_n &= c_{n-1} + d_{n-1} \\ b_n &= d_{n-1} + a_{n-1} \\ c_n &= a_{n-1} + b_{n-1} \\ d_n &= b_{n-1} + c_{n-1} \end{aligned} $$

出発点は $A$ なので、0回投げたあとの状態を $a_0 = 1, b_0 = 0, c_0 = 0, d_0 = 0$ と定める。

(1)

漸化式を順次計算する。 $n=1$ のとき

$$ \begin{aligned} a_1 &= 0 + 0 = 0 \\ b_1 &= 0 + 1 = 1 \\ c_1 &= 1 + 0 = 1 \\ d_1 &= 0 + 0 = 0 \end{aligned} $$

$n=2$ のとき

$$ \begin{aligned} a_2 &= 1 + 0 = 1 \\ b_2 &= 0 + 0 = 0 \\ c_2 &= 0 + 1 = 1 \\ d_2 &= 1 + 1 = 2 \end{aligned} $$

$n=3$ のとき

$$a_3 = 1 + 2 = 3$$

したがって、3回投げたあとに $A$ にいる場合の数は3通りである。

(2)

漸化式から $a_n$ と $c_n$ に関する関係式を導く。

$$a_n + c_n = c_{n-1} + d_{n-1} + a_{n-1} + b_{n-1} = a_{n-1} + b_{n-1} + c_{n-1} + d_{n-1}$$

$n$ 回投げたときの場合の数の総和は $2^n$ であるため、$a_{n-1} + b_{n-1} + c_{n-1} + d_{n-1} = 2^{n-1}$ となり、

$$a_n + c_n = 2^{n-1} \quad (n \ge 1)$$

が成り立つ。次に、差の数列 $x_n = a_n - c_n$, $y_n = b_n - d_n$ を考えると、

$$ \begin{aligned} x_n &= (c_{n-1} + d_{n-1}) - (a_{n-1} + b_{n-1}) = -x_{n-1} - y_{n-1} \\ y_n &= (d_{n-1} + a_{n-1}) - (b_{n-1} + c_{n-1}) = x_{n-1} - y_{n-1} \end{aligned} $$

第1式より $y_n = -x_{n+1} - x_n$ と変形して $y_n, y_{n-1}$ を消去し、$x_n$ の隣接3項間漸化式を作る。

$$ \begin{aligned} x_{n+2} &= -x_{n+1} - y_{n+1} \\ &= -x_{n+1} - (x_n - y_n) \\ &= -x_{n+1} - x_n + y_n \\ &= -x_{n+1} - x_n + (-x_{n+1} - x_n) \\ &= -2x_{n+1} - 2x_n \end{aligned} $$

さらに、この式から $x_{n+4}$ を求めると、

$$ \begin{aligned} x_{n+4} &= -2x_{n+3} - 2x_{n+2} \\ &= -2(-2x_{n+2} - 2x_{n+1}) - 2x_{n+2} \\ &= 2x_{n+2} + 4x_{n+1} \\ &= 2(-2x_{n+1} - 2x_n) + 4x_{n+1} \\ &= -4x_n \end{aligned} $$

となり、$x_n$ は4つ項が進むごとに $-4$ 倍される数列であることがわかる。 $n=2$ のとき、$x_2 = a_2 - c_2 = 1 - 1 = 0$ であるため、

$$x_{10} = -4x_6 = (-4)^2 x_2 = 16 \cdot 0 = 0$$

よって、$a_{10} - c_{10} = 0$ すなわち $a_{10} = c_{10}$ が成り立つ。和の条件 $a_{10} + c_{10} = 2^9 = 512$ と連立して解くと、

$$2a_{10} = 512$$

より $a_{10} = 256$ となる。したがって、求める場合の数は256通りである。

解説

確率や場合の数の問題において、試行の結果によって「進む距離」が変わるなどのルールが与えられた場合は、二項定理（反復試行の確率の考え方）を用いて「特定の事象が何回起こったか」を変数に設定すると、見通しよく解けることが多い（解法1）。一方で、状態の推移がルール化されているため、漸化式を利用して解く手法も有効である。漸化式を利用する場合は、本問のように対称性を生かして和や差を取ることで、簡単に一般項や特定の項の値を求めることができる（解法2）。