JJMO予選2019問6

答え\(\cdots 89\)

【分析】

なかなか手ごたえのある問題。少し実験してみるとなかなか枝分かれが多くて大変だなーという感じ。そういうときはだいたい全く別の方法でやるとうまく数えられるわけですが今回は試験時間内で僕自身いい方法が思いつかなかったので工夫して樹形図を描くことにします。キーワードは「総和に注目」です。

【略解】

条件が総和で与えられているので樹形図も総和を使って書くことにしましょう。つまり、左を一番目のカードとするとき右側のように樹形図を描くことにします。そして、毎回、総和というのもめんどうなのでi番目までの総和をi番目の数ということにしてしまいます。

このようにみるとある奇数番目の数が1だとその次の奇数番目の数が1となるのは2通り、0となるのは1通りと分かります。また、ある奇数番目の数が0のときはその次の奇数番目の数が1となるのは1通り、0となるのも1通りと分かります。(次図参照)

よってこれらより、奇数番目の数に注目して樹形図を描くと次のようになります。

ここで黒字で奇数番目の数、赤字でそのルートの場合の数を表しています。これより、

9番目の数が1となるのは

$$1+17+16=34通り$$

9番目の数が0となるのは

$$6+15=21通り$$

と分かり、9番目の数が1のときは10番目の数が0または-1の2通りがあるから

$$34\times 2+21=89通り$$

【別解】
【分析】


答えを見て、フィボナッチ数じゃん!となった人もまぁまぁいるのではないでしょうか。実はいきなり12個とは言わず、この問題の設定が1個,2個,3個…と変わったら答えはどうなるだろうといったように、樹形図でも書いて実験すると、1,2,3,5,8,13,…となっており、フィボナッチ数が現れることが予想できてしまいます!
この予想は正しいので、答えのみしか問われない予選ですから、予想のまま「89」と書き、当たってしまう人も多いという観点から、落とせない問題ですね。
ここでは、(樹形図を書いたときの経験を生かしながら、)答えがフィボナッチ数になることを示すべく、漸化式を立てにいきます。
また、イメージとしては、「奇数回目は前に何マスか、偶数回目は後ろに何マスか進む。\(n\)回の操作後、スタート時点からの差が前後1マスまでとなる歩き方は何通り?」というのを想像しておくと、なんとなく考えやすいかもしれません。(上の解法とは異なり、カードの数に注目して書いていきます。)

【略解】


条件を満たす\(n\)個の数の並べ方を\(a_n\)通りとする。
初めて1番目からの総和が0(つまり、初めてスタート地点に戻ってくる!)となるときで場合分けして考える。
(条件より、最初の数は1なので始めの数字が)

\((i)1,-1,…\)のとき
3番目以降の場合の数は\(a_{n-2}\)通り

(逆にこうでないとき、2番目は-2で確定するので)
\( (ii)1,-2,1,…\)のとき
4番目以降の場合の数は、(負,正,負,正…の順で条件を満たすように並べる場合の数も対称性により元の問題と変わらないことを加味して、)\(a_{n-3}\)通り

(逆に、これらでないとき、1,-2,2,…という場合しかなく…)
\((iii)1,-2,2,-1…\)のとき
5番目以降の場合の数は\(a_{n-4}\)通り

このように、場合分けしていくと、
$$ a_n=a_{n-2}+a_{n-3}+\cdots+a_1+1$$
という漸化式がたち、(この式を直接用いて\(a_{12}\)を求めてもよいが、)
番号をずらした式
$$ a_{n+1}=a_{n-1}+a_{n-2}+\cdots+a_1+1$$
との差を考えて、
$$a_{n+1}-a_n=a_{n-1}$$
\(∴\ a_1=1,\ a_2=2\)から、この漸化式を用いて順々に求めれば、\(a_{12}\)は11番目のフィボナッチ数89となる。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です