一般化　第４講【分野の拡張】【2007年度 京都大学ほか】

ルールの複雑さが味方になる

２段上ることが連続しないというルールが厄介です。

そこで、漸化式を導入することを目論みます。

場合の数の分野の問題というより、数列の分野の問題として捌いていくことを目論むわけです。

複雑なルールや、厄介なルールも、漸化式の作成においてはかえってシチュエーションを限定し、立式しやすくする味方になり得るのです。

漸化式を導入するために、１５段ということに拘らず、

\(n\) 段の階段の上り方を \(a_{n}\) 通り

と設定することにします。

最初の一手で場合分け

\(n\) 段を上るにあたり、最初の一手で場合分けをするとスムーズです。

最初に１段上るとき

残りは \(n-1\) 段であり、２回目の歩数に制限はないため、残る \(n-1\) 段の上り方は素直に

\(a_{n-1}\) 通り

ということになります。

最初に２段上るとき

残りは \(n-2\) 段ですが、連続で２段上ることが許されないため、自動的に次は１段上ることになります。

つまり

というような状況となるわけです。

次の歩数の選択は自由ですから、残りの \(n-3\) 段の上り方は

\(a_{n-3}\) 通り

ということになります。

まとめると

以上から、\(n\) 段の上り方の総数 \(a_{n}\) は

\(a_{n}=a_{n-1}+a_{n-3}\)

ということになります。

番号を上げる

この漸化式の定義域を考えます。

もちろんこの数列 \(\{a_{n}\}\) に対しては

\(a_{1}\) ,  \(a_{2}\) ,  \(\cdots\)

と定義されるわけで、上で得た漸化式が意味するのは

$$\begin{eqnarray}
a_{4} &=& a_{3}+a_{1} \\
a_{5} &=& a_{4}+a_{2}\\
&\vdots&
\end{eqnarray}$$

ということです。

つまり、先ほど得た漸化式によって定まる数列 \(\{a_{n}\}\) は

\(a_{n+3}=a_{n+2}+a_{n}\)

に\(n=1 \ , \ 2 \ , \ \cdots\) を代入して得られる数列 \(\{a_{n}\}\) と同じです。

したがって、添え字的にこの漸化式で考えます。

【解答】は

\(n+3\) 段の階段の上り方

を最初の一手で場合分けして記述すればよいでしょう。

場合の数の分野の問題として考えると

もし、この問題を数列の問題ではなく、そのまま場合の数の分野の問題として考えるとどういうことになるかも一応考えてみます。

• １段上るという事象を \(\mathrm{S}\)
• ２段上るという事象を\(\mathrm{W}\)

と表すことにします。

ひとまず興味があるのは

• \(\mathrm{S}\) ,  \(\mathrm{W}\) をそれぞれ何回ずつ使うのか

ということです。

そこで、まずはこの \(\mathrm{S}\) と \(\mathrm{W}\) を使う回数をそれぞれ \(x\) 回、\(y\) 回とします。

すると

\(x+2y=15\)

ということになります。

もちろん、この \(x\) ,  \(y\) というのは非負整数で、\(y\) は最大でも \(y=7\) までしかとれないため

\((x \ , \ y)=(1 \ , \ 7) \ , \ (3 \ , \ 6) \ , \ (5 \ , \ 5) \ , \ \cdots \ , \ (15 \ , \ 0)\)

ということになります。

あとはそれぞれの場合について

• \(\mathrm{WW}\) という並びを許さない並べ方

を考えればよいことになります。

「隣り合わない」という並びを実現させるには

という考え方が鉄板です。

類題について

類題はこちら（再掲）（画像をクリックするとPDFファイルで開きます。）

例題と違い、歩数制限はありません。

なお、原題には誘導がありましたが、今回はカットしました。

類題２について

類題２はこちら（再掲）（画像をクリックするとPDFファイルで開きます。）

(2) が中々のクセモノです。

一般化するか、そのまま解ききるかの判断に迫られます。

例題の解答はコチラ

類題の解答はコチラ

類題２の解答はコチラ