[答1546] オセロの石の並べ方
オセロの石を 同じ色が５個以上続かないように 横一列に11個を並べる方法は何通り？
[解答1]
◎は◯でも●でもよいものとし、まず 同じ色が５個以上続くものを求めます。
◯が５個以上続くものは、◯◯◯◯◯◎◎◎◎◎◎ ，●◯◯◯◯◯◎◎◎◎◎ ，
◎●◯◯◯◯◯◎◎◎◎ ，◎◎●◯◯◯◯◯◎◎◎ ，◎◎◎●◯◯◯◯◯◎◎ ，
◎◎◎◎●◯◯◯◯◯◎ ，◎◎◎◎◎●◯◯◯◯◯ であり、
◯◯◯◯◯◎◎◎◎◎◎ は 26＝64 通りで 他は 25＝32 通り、
◯◯◯◯◯●◯◯◯◯◯ が重複しているので、64＋32･6－1＝255 通り、
●が５個以上続くものも同数で 255 通り、
◯◯◯◯◯●●●●●◯ ，●●●●●◯◯◯◯◯● ，●◯◯◯◯◯●●●●● ，
◯●●●●●◯◯◯◯◯ ，◯◯◯◯◯◎●●●●● ，●●●●●◎◯◯◯◯◯ の
８通りが重複しているので、255＋255－8＝502 通りです。
同じ色が５個以上続かないのは 211－502＝2048－502＝1546 通りです。
[解答2]
11個の石の間の10ヶ所に着目し、左右の色が異なるとき×，同じとき－とすれば、
図の場合は ×－－×－－－×－× という並びになります。
同じ色が５個以上続かないようにするためには －は４個以上続かないようにすればいい。
－が４個以上続く場合は、？が×－のどちらでもよいものとして、
－－－－？？？？？？ ，×－－－－？？？？？ ，？×－－－－？？？？ ，
？？×－－－－？？？ ，？？？×－－－－？？ ，？？？？×－－－－？ ，
？？？？？×－－－－ ですが、
－－－－？？？？？？ は 26＝64 通り、他は 25＝32 通り、
－－－－×－－－－？ ，
－－－－－×－－－－ ，－－－－××－－－－ ，×－－－－×－－－－
の５通りは重複しますので、
－は４個以上続く場合は、64＋32･6－5＝251 通りです。
先頭は●，◯の両方が考えられるので、211－2･251＝1546 通りです。
[解答3]
オセロの石を 同じ色が５個以上続かないように 横一列にｎ個を並べる方法を an 通りとします。
？？？？？？？？？●◯ または ？？？？？？？？？◯● …… 合計 a10 通り、
？？？？？？？？●◯◯ または ？？？？？？？？◯●● …… 合計 a9 通り、
？？？？？？？●◯◯◯ または ？？？？？？？◯●●● …… 合計 a8 通り、
？？？？？？●◯◯◯◯ または ？？？？？？◯●●●● …… 合計 a7 通り、
従って、a11＝a10＋a9＋a8＋a7 です。
同様に、n≧5 のとき、an＝an-1＋an-2＋an-3＋an-4 です。
n≦4 のときは 裏表を任意に置けるので an＝2n 、a1＝2 ，a2＝4 ，a3＝8 ，a4＝16 、
a5＝a4＋a3＋a2＋a1＝30 ，a6＝a5＋a4＋a3＋a2＝58 ，
a7＝a6＋a5＋a4＋a3＝112 ，a8＝a7＋a6＋a5＋a4＝216 ，
a9＝a8＋a7＋a6＋a5＝416 ，a10＝a9＋a8＋a7＋a6＝802 ，
a11＝a10＋a9＋a8＋a7＝1546 です。
[解答4]
11個の石の間の10ヶ所に着目し、左右の色が異なるとき×，同じとき－とすれば、
図の場合は ×－－×－－－×－× という並びになります。
同じ色が５個以上続かないようにするためには －は４個以上続かないようにすればいい。
－が４個以上個以上続かないように 横一列にｎ個を並べる方法を bn 通りとします。
？？？？？？？？？× または ？？？？？？？？×－ または ？？？？？？？×－－
または ？？？？？？×－－－ ですので、合計 b9＋b8＋b7＋b6 通り、
b10＝b9＋b8＋b7＋b6 です。
同様に、n≧4 のとき、bn＝bn-1＋bn-2＋bn-3＋bn-4 です。
n≦3 のときは ×，－を任意に並べられるので bn＝2n 、b1＝2 ，b2＝4 ，b3＝8 、
n＝4 のときは －－－－ 以外ですので、b4＝24－1＝15 、
b5＝b4＋b3＋b2＋b1＝29 ，b6＝b5＋b4＋b3＋b2＝56 ，
b7＝b6＋b5＋b4＋b3＝108 ，b8＝b7＋b6＋b5＋b4＝208 ，
b9＝b8＋b7＋b6＋b5＝401 ，b10＝b9＋b8＋b7＋b6＝773 、
先頭は●，◯の両方が考えられるので、2b10＝1546 通りです。
.
