[答273] 3色での塗り分け
[答273] 3色での塗り分け
図のように、14個の長方形が1列に並んでおり、両端に赤を塗ります。
中の 12個の長方形を、赤・緑・青で塗り分けます。
隣り合う長方形には異なる色を塗るとき、塗り方は何通り?
[解答1]
中の長方形がn個のときの塗り方を an 通りとします。
中の 12個の長方形を、左から順に、左隣と異なる色を塗る方法は、212 通りあって、
そのうちの右端が赤の塗り方は a11 通りで、それ以外が a12 通りです。
従って、a12=212-a11 になります。
同様に、漸化式 an+1=2n+1-an が得られます。
an+1-2n+2/3=-(an-2n+1/3) 、
数列{ an-2n+1/3 }は公比が -1 の等比数列です。
an-2n+1/3=(a1-4/3)(-1)n-1 、
ここで、a1=2 だから、an=2{2n-(-1)n}/3 になります。
a12=2{212-(-1)12 }/3=2730 通りです。
[解答2] uch*n*anさんのコメントより
左端が赤で n 個の長方形を並べた場合において,
さらにその右,n+1 番目が,赤を an 通り,青を bn 通り,黄を cn 通り,とすると,
an=bn-1+cn-1=(an-2+cn-2)+(an-2+bn-2)
=(bn-2+cn-2)+2an-2=an-1+2an-2
ただし,a1=2, a2=2 です。
☆ 漸化式 an=an-1+2an-2 の解き方
an+an-1=2(an-1+2an-2) と変形すれば、
数列{ an+1+an }は公比が 2 の等比数列です。
an+1+an=(a2+a1)・2n-1=2n+1
以下、[解答1]と同様に解いてもいいし、
an-2an-1=-(an-1-2an-2) と変形すれば、
数列{ an+1-2an }は公比が -1 の等比数列です。
an+1-2an=(a2-2a1)・(-1)n-1=2(-1)n
an+1+an=2n+1,an+1-2an=2(-1)n の差をとれば、
3an=2n+1-2(-1)n です。
[解答3] 再出発さんのコメントより
左端(第0枠)が赤で 第n枠が 赤を an 通り,青または黄色を bn 通りとすると、
a1=0,b1=2,an+1=bn,bn+1=2an+bn
が成り立ちます。
an+1+bn+1=2(an+bn) だから、
数列{ an+bn }は公比が 2 の等比数列です。
an+bn=(a1+b1)・2n-1=2n
an+1-bn+1/2=-(an-bn/2) だから、
数列{ an-bn/2 }は公比が -1 の等比数列です。
an-bn/2=(a1-b1/2)・(-1)n-1=(-1)n
an+bn=2n,an-bn/2=(-1)n の差をとれば、
(3/2)bn=2n-(-1)n 、bn=2{2n-(-1)n}/3 になります。
本問で求めるのは b12=2{212-(-1)12 }/3=2730 通りです。
.