日本数学オリンピックの簡単な問題（１４３）

こんにちは。東久留米市の学習塾塾長です。

今回は、２０１８年日本数学オリンピック予選に出題された場合の数の問題を取り上げます。

問題は、
「１１個のオセロの石が１列に（ａ）のように並んでいる。次のように裏返すことを何回か行う：

　　　表の色が同じで隣りあわない２つの石であって、その間にはもう一方の色の石しかないものを選ぶ。
　　　そしてその間の石をすべて同時に裏返す。

このとき、（ｂ）のようになるまでの裏返し方は何通りあるか。

ただし、オセロの石は片面が●、もう片面が○である。」
です。

早速、取り掛かりましょう。

下図の左側ように、（ａ）の状態から黒石に挟まれた白石を裏返して黒石にする場合（図の左側）と、白石に挟まれた黒石を裏返して白石にする場合（図の右側）を考えると、新たにできた３個並んだ黒石または白石は一つのかたまり、つまり、これらが挟まれて裏返されるとき、これらのすべてが白石または黒石になるので、これらを１個の黒石または白石とみなすことができます。

▲図．（ａ）から１つの石を裏返した場合、３個並んだ同じ色の石を１個の石とみなすことができます

そこで、２ｎ＋１個の石が黒石を両端にして並んでいる場合の石の裏返し方を Ｆ（2n+1） とすると、２ｎ＋１個の石の並びの両端以外の２ｎ－１個の石を裏返すと、２ｎ－１個の石が黒石を両端にして並ぶ状態と同じになるので、
Ｆ（2n+1)＝（２ｎ－１）Ｆ（2n-1)　　　　　（★）
が成り立ちます。

３個の石が ●○● と並んでいる場合、●●● にする裏返し方は１通りなので、
Ｆ（３）＝１
です。

これと（★）を使って順番に Ｆ（５）、Ｆ（７）、Ｆ（９）、Ｆ（１１）を計算していくと、
Ｆ（５）　＝（２×２－１）Ｆ（３）＝３
Ｆ（７）　＝（２×３－１）Ｆ（５）＝１５
Ｆ（９）　＝（２×４－１）Ｆ（７）＝１０５
Ｆ（１１）＝（２×５－１）Ｆ（９）＝９４５
になります。

したがって、（ａ）から（ｂ）にする裏返し方は ９４５通り で、これが答えです。


簡単な問題です。