こんにちは。東久留米市の学習塾塾長です。
今日も晴れの蒸し暑い日になりましたが、天気は下り坂で、夕方から雲が多くなり、明日には雨になるようです。降雨のおかげで気温は低くなるようで、少し過ごしやすくなってくれるといいのですが。
さて、今回は２０１１年日本数学オリンピック予選に出題された場合の数の問題を取り上げます。
問題は、
「赤い玉、青い玉、黄色い玉合わせて１２個を横一列に並べるとき、以下の条件をみたす並べ方は何通りあるか。ただし、並べる玉の色が２種類以下の場合も考えるものとする。
条件：どの玉に対しても、その玉と同じ色で、その玉に隣接するような玉が存在する。」
です。
早速、取り掛かりましょう。
１２個の玉の列を２個以上のグループに分割して、それらのすべての場合について玉の並べ方を勘定し、それらを足し合わせても正解にたどり着けそうですが、とても煩雑そうなので、ここは漸化式を利用するのがよさそうです。
そこで、問題の条件を満たすｎ個の玉の並べ方の場合の数をＡ（ｎ）とします。
ここで、下図のように、ｎ－２個の玉の列からｎ個の玉の列を作る場合を調べます。
▲図．ｎ－２個の玉の列からｎ個の玉の列を作る場合を調べます（ｎ－２個目を赤い玉にしました）
ｎ－２個目の玉の色と同じ色の玉をｎ－１個目に置くと、条件を満たすｎ－１個の玉の列を作ることができて、その場合の数はＡ（ｎ－１）です。
さらに、ｎ個目に玉を置いて、条件を満たすｎ個の玉の列を作る場合を考えると、ｎ個目にはｎ－１個目の玉と同じ色の玉を置くしかなく、その場合の数はＡ（ｎ－１）になります。
次に、ｎ－２個目の玉の色と異なる色の玉をｎ－１個目に置く場合、ｎ個目も同じ色の玉を置かなければなりません。このとき、ｎ－２個目の玉の色と異なる色は２色なので、その場合の数は、２Ａ（ｎ－２）になります。
したがって、条件を満たすｎ個の玉の場合の数Ａ（ｎ）は、
Ａ（ｎ）＝Ａ（ｎ－１）＋２Ａ（ｎ－２） （１）
という漸化式になります。
あとは、（１）を解くだけです。
まず、（１）の特性方程式ｘ^2－ｘ－２＝０の解ｘ＝－１、２から、（１）は
Ａ（ｎ）－２Ａ（ｎ－１）＝－（Ａ（ｎ－１）－２Ａ（ｎ－２）） （２）
Ａ（ｎ）＋Ａ（ｎ－１）＝２（Ａ（ｎ－１）＋Ａ（ｎ－２）） （３）
と変形することができます。
まず、（２）について、
Ｂ（ｎ）＝Ａ（ｎ）－２Ａ（ｎ－１） （４）
とすると、（２）は、
Ｂ（ｎ）＝－Ｂ（ｎ－１）
で、
Ｂ（ｎ）＝（－１）^(n-3)・Ｂ（３）
＝３・（－１）^n
です。（Ｂ（３）＝Ａ（３）－２Ａ（２）＝３－６＝－３）
これを（４）に代入して、
Ａ（ｎ）－２Ａ（ｎ－１）＝３・（－１）^n （５）
です。
次に、（３）について、
Ｃ（ｎ）＝Ａ（ｎ）＋Ａ（ｎ－１） （６）
とすると、（３）は、
Ｃ（ｎ）＝２Ｃ（ｎ－１）
で、
Ｃ（ｎ）＝２^(n-3)・Ｃ（３）
＝６・２^(n-3)
＝３・２^(n-2)
です。（Ｃ（３）＝Ａ（３）＋Ａ（２）＝３＋３＝６）
これを（６）に代入して、
Ａ（ｎ）＋Ａ（ｎ－１）＝３・２^(n-2) （７）
です。
最後に、（５）と（７）からＡ（ｎ－１）を消去して、
Ａ（ｎ）＝２^(n-1)＋（－１）^n （８）
と、Ａ（ｎ）を求めることができました。
ここで、（８）にｎ＝１２を代入すると、
Ａ（１２）＝２^11＋（－１）^12
＝２０４８＋１
＝２０４９
で、問題の条件を満たす玉の並べ方は２０４９通りで、これが答えです。
３項間漸化式を解くのが面倒なときは、
Ａ（２）＝３
Ａ（３）＝３
Ａ（４）＝Ａ（３）＋２Ａ（２）＝３＋６＝９
Ａ（５）＝Ａ（４）＋２Ａ（３）＝９＋６＝１５
・・・・・
Ａ（１２）＝Ａ（１１）＋２Ａ（１０）＝１０２３＋１０２６＝２０４９
と順番に計算するとよいでしょう。
今日も晴れの蒸し暑い日になりましたが、天気は下り坂で、夕方から雲が多くなり、明日には雨になるようです。降雨のおかげで気温は低くなるようで、少し過ごしやすくなってくれるといいのですが。
さて、今回は２０１１年日本数学オリンピック予選に出題された場合の数の問題を取り上げます。
問題は、
「赤い玉、青い玉、黄色い玉合わせて１２個を横一列に並べるとき、以下の条件をみたす並べ方は何通りあるか。ただし、並べる玉の色が２種類以下の場合も考えるものとする。
条件：どの玉に対しても、その玉と同じ色で、その玉に隣接するような玉が存在する。」
です。
早速、取り掛かりましょう。
１２個の玉の列を２個以上のグループに分割して、それらのすべての場合について玉の並べ方を勘定し、それらを足し合わせても正解にたどり着けそうですが、とても煩雑そうなので、ここは漸化式を利用するのがよさそうです。
そこで、問題の条件を満たすｎ個の玉の並べ方の場合の数をＡ（ｎ）とします。
ここで、下図のように、ｎ－２個の玉の列からｎ個の玉の列を作る場合を調べます。
▲図．ｎ－２個の玉の列からｎ個の玉の列を作る場合を調べます（ｎ－２個目を赤い玉にしました）
ｎ－２個目の玉の色と同じ色の玉をｎ－１個目に置くと、条件を満たすｎ－１個の玉の列を作ることができて、その場合の数はＡ（ｎ－１）です。
さらに、ｎ個目に玉を置いて、条件を満たすｎ個の玉の列を作る場合を考えると、ｎ個目にはｎ－１個目の玉と同じ色の玉を置くしかなく、その場合の数はＡ（ｎ－１）になります。
次に、ｎ－２個目の玉の色と異なる色の玉をｎ－１個目に置く場合、ｎ個目も同じ色の玉を置かなければなりません。このとき、ｎ－２個目の玉の色と異なる色は２色なので、その場合の数は、２Ａ（ｎ－２）になります。
したがって、条件を満たすｎ個の玉の場合の数Ａ（ｎ）は、
Ａ（ｎ）＝Ａ（ｎ－１）＋２Ａ（ｎ－２） （１）
という漸化式になります。
あとは、（１）を解くだけです。
まず、（１）の特性方程式ｘ^2－ｘ－２＝０の解ｘ＝－１、２から、（１）は
Ａ（ｎ）－２Ａ（ｎ－１）＝－（Ａ（ｎ－１）－２Ａ（ｎ－２）） （２）
Ａ（ｎ）＋Ａ（ｎ－１）＝２（Ａ（ｎ－１）＋Ａ（ｎ－２）） （３）
と変形することができます。
まず、（２）について、
Ｂ（ｎ）＝Ａ（ｎ）－２Ａ（ｎ－１） （４）
とすると、（２）は、
Ｂ（ｎ）＝－Ｂ（ｎ－１）
で、
Ｂ（ｎ）＝（－１）^(n-3)・Ｂ（３）
＝３・（－１）^n
です。（Ｂ（３）＝Ａ（３）－２Ａ（２）＝３－６＝－３）
これを（４）に代入して、
Ａ（ｎ）－２Ａ（ｎ－１）＝３・（－１）^n （５）
です。
次に、（３）について、
Ｃ（ｎ）＝Ａ（ｎ）＋Ａ（ｎ－１） （６）
とすると、（３）は、
Ｃ（ｎ）＝２Ｃ（ｎ－１）
で、
Ｃ（ｎ）＝２^(n-3)・Ｃ（３）
＝６・２^(n-3)
＝３・２^(n-2)
です。（Ｃ（３）＝Ａ（３）＋Ａ（２）＝３＋３＝６）
これを（６）に代入して、
Ａ（ｎ）＋Ａ（ｎ－１）＝３・２^(n-2) （７）
です。
最後に、（５）と（７）からＡ（ｎ－１）を消去して、
Ａ（ｎ）＝２^(n-1)＋（－１）^n （８）
と、Ａ（ｎ）を求めることができました。
ここで、（８）にｎ＝１２を代入すると、
Ａ（１２）＝２^11＋（－１）^12
＝２０４８＋１
＝２０４９
で、問題の条件を満たす玉の並べ方は２０４９通りで、これが答えです。
３項間漸化式を解くのが面倒なときは、
Ａ（２）＝３
Ａ（３）＝３
Ａ（４）＝Ａ（３）＋２Ａ（２）＝３＋６＝９
Ａ（５）＝Ａ（４）＋２Ａ（３）＝９＋６＝１５
・・・・・
Ａ（１２）＝Ａ（１１）＋２Ａ（１０）＝１０２３＋１０２６＝２０４９
と順番に計算するとよいでしょう。