n ≥ 5 のときを考えよう。 1 番目の色と n-1 番目の色が異なるとき、 自動的に n 番目の色が決まるが、それを取り除くと 枚数が 1 減った場合になる。 よってこのような塗り方は P(n-1) とおりある。 (増加を押して下さい) 1 番目の色と n-1 番目の色が同じときは n 番目の塗り方は 2 とおりある。 また、n-1 番目と n 番目を取り除くと、枚数が 2 減った場合になる。 つまり n-2 枚の場合に n-1 番目に 1 番目と同じ色を塗り、n 番目にそれ以外を塗ればよい。 この場合の塗り方は 2P(n-2) である。 P(n) = P(n-1) + 2P(n-2) という式が成り立つ。 P(3) = 6, P(4) = 18, P(n) = P(n-1) + 2P(n-2) 　　　(n ≥ 5) より P(n) を求める。 n ≥ 5 のとき P(n) + P(n-1)= 2(P(n-1) + P(n-2))　である。よって P(n) + P(n-1)= 2n-4(P(4) + P(3)) = 2n-4×24 = 2n-1×3 (-1)k(P(n-k) + P(n-k-1)) = (-1)k2n-k-1×3 　　　(k = 0,1,...,n-4)　であり、これを加えて P(n) + (-1)n-4 P(3) = 2n-1×3×(1 + (-1/2) + (-1/2)2 + ... + (-1/2)n-4) 　　= 2n-1×3×(1 - (-1/2)n-3)/ (1 - (-1/2)) = 2n + (-1)n×8 これより　P(n) = 2n + (-1)n×8 - (-1)n P(3) = 2n + (-1)n×2 を得る。 この式は n = 3, 4 の時も成立する。 問題の答えは n が奇数のきは Pn = 2n+2 + (-1)n×8 であり n が偶数のきは Pn = 2n+2 + (-1)n×8 + 24 である。 一つ戻る 　戻る