正 $n$ 角形 $A_1 A_2 \dots A_n$ の各頂点に、赤、青、白のいずれかの色の旗を1本ずつ配置する。隣接する頂点に同じ色の旗を配置しないような旗の配置方法は何通りか。ただし、$n$ は3以上の自然数とする。

1. 問題の内容

正 $n$ 角形 $A_1 A_2 \dots A_n$ の各頂点に、赤、青、白のいずれかの色の旗を1本ずつ配置する。隣接する頂点に同じ色の旗を配置しないような旗の配置方法は何通りか。ただし、$n$ は3以上の自然数とする。

2. 解き方の手順

この問題は漸化式を用いて解くことができる。

$a_n$ を $n$ 個の頂点に隣接する頂点に同じ色の旗を配置しないように旗を配置する方法の数とする。ただし、1番目と $n$ 番目の頂点の色は異なるとする。

$b_n$ を $n$ 個の頂点に隣接する頂点に同じ色の旗を配置しないように旗を配置する方法の数とする。ただし、1番目と $n$ 番目の頂点の色は同じとするとする。

$n=1$ のとき、 $a_1=3$

$n=2$ のとき、 $a_2 = 3 \times 2 = 6$

$n \ge 3$ のとき、$a_n$ と $b_n$ について考える。

$A_n$ に旗を配置することを考える。

$A_n$ に $A_1$ と異なる色の旗を配置する場合、$n-1$ 個の頂点 $A_1, A_2, \dots, A_{n-1}$ に隣接する頂点に同じ色の旗を配置しないように旗を配置する方法の数は $a_{n-1}$ である。$A_n$ には $A_{n-1}$ と異なる色の旗を配置するので、2通りの選択肢がある。この場合は $a_{n-1}$ 通りである。

$A_n$ に $A_1$ と同じ色の旗を配置する場合、$n-1$ 個の頂点 $A_1, A_2, \dots, A_{n-1}$ に隣接する頂点に同じ色の旗を配置しないように旗を配置する方法の数は $b_{n-1}$ である。$A_n$ には $A_{n-1}$ と異なる色の旗を配置するので、1通りの選択肢がある。この場合は $b_{n-1}$ 通りである。

したがって、$a_n = 2a_{n-1} + b_{n-1}$ となる。

一方、$n-1$ 個の頂点 $A_1, A_2, \dots, A_{n-1}$ に隣接する頂点に同じ色の旗を配置しないように旗を配置する方法の数は $a_{n-1}$ である。$A_n$ には $A_1$ と同じ色の旗を配置するため、$A_{n-1}$ と異なる色の旗を配置する必要がある。つまり、$a_{n-1}$ 通りのうち $A_{n-1}$ は $A_1$ と同じ色の場合とそうでない場合があるので、 $a_{n-1}$ のうち、$A_{n-1}$ が $A_1$ と同じ色のものは $b_{n-2}$ であり、$A_{n-1}$ が $A_1$ と異なる色のものは $a_{n-2}$ である。

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

$A_n$ に $A_1$ と同じ色の旗を配置する場合、$A_{n-1}$ と異なる色の旗を配置する必要がある。$A_n$ の色は $A_1$ と同じなので、 $A_{n-1}$ は $A_1$ と異なる色の旗を配置する必要がある。つまり、$a_{n-1}$ の場合において、$A_{n-1}$ が $A_1$ と異なる色のものを選ぶことになるので、 $a_{n-1}$ 通りのうち $a_{n-2}$ 通りの場合に、$A_n$ は $A_1$ と同じ色を塗ることができる。

したがって、$b_n = a_{n-1}$ となる。

よって、$a_n = 2a_{n-1} + a_{n-2}$ となる。

ここで、求めるべきは $a_n + b_n$ ではなく、隣り合う頂点の色が異なる配置の総数である。これを $c_n$ とおく。

$c_n = a_n + b_n$ ではない。

$c_n =$ (最初の頂点と最後の頂点が同じ色の配置数) + (最初の頂点と最後の頂点が異なる色の配置数)

$c_n = b_n + a_n$ でもない。

$c_1 = 3$

$c_2 = 6$

$c_3 = 6$ (赤青白, 赤白青, 青赤白, 青白赤, 白赤青, 白青赤)

漸化式は $c_n = 2c_{n-1} + 2c_{n-2}$ ではない。

$c_n = 2c_{n-1}+b_{n-1}$

$c_n = 2^n+2 (-1)^n$

3. 最終的な答え

$3 \times 2^{n-1} - (-1)^n \times 3$

$2^n+2(-1)^n$

最終的な答えは $2^n+2(-1)^n$ 通りである。