第３問の解答
１．問題
| １０個の碁石が１列に並んでいます。 （１）このうち、連続した碁石を選ぶ選び方は何通りでしょう。 （２）どの碁石も隣り合わないように選ぶ選び方は何通りでしょう。 |
２．設問（１）：解答例１（ありさのお父さん、他）
選ぶ碁石の個数が増えるに従って、選び方が減ってきます。
答：５５通り
以上
３．設問（２）：解答例１（三好知之さん他）
下表のように数えると合計１４３通りとなります。
以上
４．設問（２）：解答例１（kuri他）
碁石がｎ個あって、そのうちｒ個を選ぶ選び方をf(n,r)通りとします。
f(n,1)=n,f(n1,r)=1は明らか。ただし、n1=2*r-1。
また、図１よりf(n+1,r)=f(n,r)+f(n-1,r-1)となるので、これから順に求めていくと表１のごとく求まり、碁石が１０個のときの選び方総数は１４３通りとなる。
図１
表１
なお、碁石がｎ個の時の選び方総数をg(n)とすると、g(n+1)=g(n)+g(n-1)+1となっていることに注意。
これより、ｈ(n)=g(n)+1とおくと、h(n+1)=h(n)+h(n-1)となり、h(n)がフィボナッチ数列として一般式を求めることが出来る。
５．設問（２）：解答例２
下図のように、選んだ碁石（最後の碁石を除く）の右側には必ず選ばない碁石があるので、これをペアで考えると、結局n-r+1の碁石からr個選ぶ選び方f(n,r)=n-r+1Crに等しいことが分かる。
これより求めたf(n,r)は、表１と合致する。
６．設問（２）：解答例３（ありさのお父さん、中村明海さん）
碁石がｎ個の時の選び方総数をg(n)とする。 碁石を全く選ばない場合の１通りを含めて考えることとし、h(n)=g(n)+1とすれば、左図より、h(n+1)=h(n-1)+h(n)を得るので、h(n)はフィボナッチ数列となる。
h(1)=2、h(2)=3より順次計算していけば、h(10)=１４４となるので、g(10)=h(10)-1=143通りとなる。
以上
