東京大学 1995年 理系 第3問 解説

方針・初手

• (1)は図形の敷き詰めの総数を漸化式を用いて求める典型問題である。横幅が $n$ の領域の右端（または左端）にどのようにタイルを配置するかで場合分けを行う。配置したタイルの幅によって、残りの領域の横幅が $n-1$ になるか $n-2$ になるかが決まる。
• (2)は(1)で求めた隣接3項間漸化式を解く。特性方程式を用いて2種類の等比数列を作り、そこから $A_n$ を求める。

解法1

(1)

縦2、横 $n$ の部屋を過不足なく敷き詰める方法について、右端のタイルの配置は次の3つの場合が考えられる。

（i） 右端に $1 \times 2$ の長方形タイルを縦に1枚置く場合 このタイルで縦2、横1のスペースを占めるため、残りのスペースは縦2、横 $n-1$ の長方形となる。この残りの部分の敷き詰め方は $A_{n-1}$ 通りである。

（ii） 右端に $1 \times 2$ の長方形タイルを横に2枚（上下に）置く場合 この2枚のタイルで縦2、横2のスペースを占めるため、残りのスペースは縦2、横 $n-2$ の長方形となる。この残りの部分の敷き詰め方は $A_{n-2}$ 通りである。

（iii） 右端に $2 \times 2$ の正方形タイルを1枚置く場合 このタイルで縦2、横2のスペースを占めるため、残りのスペースは縦2、横 $n-2$ の長方形となる。この残りの部分の敷き詰め方は $A_{n-2}$ 通りである。

（i）、（ii）、（iii） の各場合は互いに排反である。$n \geqq 3$ のとき、これらを足し合わせて以下の漸化式を得る。

$$ A_n = A_{n-1} + 2A_{n-2} $$

(2)

(1)で求めた漸化式 $A_n - A_{n-1} - 2A_{n-2} = 0$ の特性方程式 $\alpha^2 - \alpha - 2 = 0$ を解くと、

$$ (\alpha - 2)(\alpha + 1) = 0 \quad \therefore \alpha = 2, -1 $$

これより、与えられた漸化式は次の2通りに変形できる。

$$ A_n - 2A_{n-1} = -(A_{n-1} - 2A_{n-2}) \quad \cdots ① $$

$$ A_n + A_{n-1} = 2(A_{n-1} + A_{n-2}) \quad \cdots ② $$

問題文より $A_1 = 1$、$A_2 = 3$ である。

①より、数列 $\{ A_n - 2A_{n-1} \}$ は初項 $A_2 - 2A_1 = 3 - 2 = 1$、公比 $-1$ の等比数列であるから、

$$ A_n - 2A_{n-1} = 1 \cdot (-1)^{n-2} = (-1)^n \quad \cdots ③ $$

②より、数列 $\{ A_n + A_{n-1} \}$ は初項 $A_2 + A_1 = 3 + 1 = 4$、公比 $2$ の等比数列であるから、

$$ A_n + A_{n-1} = 4 \cdot 2^{n-2} = 2^n \quad \cdots ④ $$

④ $\times 2\ +$ ③ を計算して $A_{n-1}$ を消去すると、

$$ 3A_n = 2 \cdot 2^n + (-1)^n = 2^{n+1} + (-1)^n $$

したがって、求める一般項は、

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

解説

• 領域の敷き詰め方（タイリング）の総数を求める問題は、漸化式を立てて解くのが定石である。端に配置するタイルのパターンで場合分けし、残りの領域の形が元の形と同じ（サイズだけが縮小された形）になることに着目する。
• 本問では、残りの幅が $n-2$ になるパターンが2種類（$1 \times 2$ を横に2枚、$2 \times 2$ を1枚）あることに注意する。ここを数え落とすと漸化式が誤ったものになる。
• 隣接3項間漸化式の解法は標準的である。求めた一般項に $n=1, 2, 3$ を代入し、問題文に与えられている $A_1=1, A_2=3, A_3=5$ の値と一致するかどうかで検算を行うとよい。

答え

(1)

$$ A_n = A_{n-1} + 2A_{n-2} $$

(2)

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