縦2、横$n$の長方形に、2$n$枚の白色または黒色の正方形タイルを敷き詰めます。ただし、どの2つの黒色タイルも頂点を共有しません。 $a_n$：左上と左下がともに白色の場合の数 $b_n$：左上が黒色で左下が白色の場合の数 $c_n$：すべての敷き詰め方の場合の数 (1) $a_1$, $b_1$, $c_1$, $a_2$, $b_2$, $c_2$ を求めよ。 (2) $a_{n+1}$, $b_{n+1}$ を $a_n$, $b_n$ を用いて表せ。 (3) $a_{n+1} + a_n$ を求めよ。また、$a_{n+1} - 2a_n$ を求めよ。 (4) $c_n$ を求めよ。

1. 問題の内容

縦2、横$n$の長方形に、2$n$枚の白色または黒色の正方形タイルを敷き詰めます。ただし、どの2つの黒色タイルも頂点を共有しません。

$a_n$：左上と左下がともに白色の場合の数

$b_n$：左上が黒色で左下が白色の場合の数

$c_n$：すべての敷き詰め方の場合の数

(1) $a_1$, $b_1$, $c_1$, $a_2$, $b_2$, $c_2$ を求めよ。

(2) $a_{n+1}$, $b_{n+1}$ を $a_n$, $b_n$ を用いて表せ。

(3) $a_{n+1} + a_n$ を求めよ。また、$a_{n+1} - 2a_n$ を求めよ。

(4) $c_n$ を求めよ。

2. 解き方の手順

(1)

$n = 1$ のとき、タイルは2枚。

- $a_1$: 左上と左下がともに白色。つまり、2枚とも白色。1通り。

- $b_1$: 左上が黒色で左下が白色。1通り。

- $c_1$: すべての場合。2枚とも白、左上が黒で左下が白、左上が白で左下が黒、2枚とも黒。3通り。条件から2枚とも黒はありえないので、$1 + 1 + 1 = 3$ ではなく、$1 + 1 + 0 = 2$？

- $c_1= a_1+2b_1$ とすると、$c_1 = 1 + 2*1 = 3$

$n = 2$ のとき、タイルは4枚。

- $a_2$: 左上と左下がともに白色。

- 1段目も2段目も両方白：1通り

- 1段目白黒、2段目白白：1通り

- 1段目白白、2段目白黒：1通り

よって、$a_2 = 3$

- $b_2$: 左上が黒色で左下が白色。

- 1段目黒白、2段目白白：1通り

- 1段目黒黒、2段目白白：0通り

- 1段目黒白、2段目白黒：1通り

よって、$b_2 = 2$

- $c_2$: すべての場合

- 1段目2段目ともに白白：1

- 1段目黒白2段目白白：1

- 1段目白黒2段目白白：1

- 1段目白白2段目黒白：1

- 1段目白白2段目白黒：1

- 1段目黒白2段目白黒：1

よって$c_2=6$，$c_2=a_2+2b_2=3+2\times 2=7$

$a_n$ : 左上と左下がともに白色の場合の数

$b_n$ : 左上が黒色で左下が白色の場合の数

$c_n = a_n + 2b_n$

(2)

$a_{n+1}$: 左上と左下がともに白色

- 一番左の列が白白の場合: 残りの $n$ 列は $a_n$ 通り

- 一番左の列が白黒の場合: 残りの $n$ 列は $b_n$ 通り

- 一番左の列が黒白の場合: 残りの $n$ 列は $b_n$ 通り (これは$a_n$にはならないので考える必要がない)

$a_{n+1} = a_n + b_n$

$b_{n+1}$: 左上が黒色で左下が白色

- 一番左の列が白白：ありえない

- 一番左の列が白黒の場合: 残りの $n$ 列は $a_n$ 通り

- 一番左の列が黒白の場合：残りn列は白白以外。白白は$a_n$通りなので$c_n - a_n$通り。

- 一番左の列が黒黒：残りn列は黒タイルの頂点が接しないように敷き詰めればよいから場合分けすると$b_n-1$通り？

- 一番左の列が黒白：$b_n$から黒タイル頂点が接する場合を引く？

したがって、$b_{n+1} = a_n + b_n$。

(3)

$a_{n+1} = a_n + b_n$ より、$b_n = a_{n+1} - a_n$。

$a_{n+1} = a_n + b_n$、$b_{n+1} = a_n + b_n$なので、$b_{n+1} = a_{n+1}$

$a_{n+2}=a_{n+1}+b_{n+1}=a_{n+1}+a_{n+1}=2a_{n+1}$.

よって、$a_{n+1} + a_n = b_{n+2}$.

$a_{n+1} + a_n = F_{n+3}$ ($F_n$はフィボナッチ数)

$a_{n+1} - 2a_n = (a_n + b_n) - 2a_n = b_n - a_n$

$a_{n+1}+a_n=a_n+b_n+a_n = 2a_n + b_n$

(4)

$c_n = a_n + 2b_n$

$b_n = a_{n+1} - a_n$

$c_n = a_n + 2(a_{n+1} - a_n) = 2a_{n+1} - a_n$

3. 最終的な答え

(1)

$a_1 = 1$, $b_1 = 1$, $c_1 = 3$, $a_2 = 3$, $b_2 = 2$, $c_2 = 7$

(2)

$a_{n+1} = a_n + b_n$

$b_{n+1} = a_n + b_n$

(3)

$a_{n+1} + a_n = ?$

$a_{n+1} - 2a_n = b_n - a_n$

(4)

$c_n = 2a_{n+1} - a_n$