|
uchinyan |
|
はい，こんにちは。さて，今回の問題は．．．
この問題は一目見てフィボナッチと気付きました。 10 点を斜めにして段差を設けて階段とみなし，結んだ個所を１段とばしとみなせば，答えがフィボナッチのよく知られた階段上りになるからです。 算チャレとしては標準的かやや易，どちらかといえば易しい方かな，という気がします。 解答としては，こんな感じで。 (解法1) 説明に少し不備があったので修正しました。 10 点の隙間 9 箇所のうち ○ 個所に線を引くとします。○ = 0, 1, 2, 3, 4, 5，です。 ○ = 1 〜 5 の場合は，線の間に少なくとも１つ線のない隙間が必要で，これが ○ - 1 個所になり， 結局，9 - (○ - 1) = 10 - ○ 個所から線を引く ○ 個所を選ぶことになり，(10 - ○)C○ 通り，です。 ○ = 0，つまり線を全く引かない場合は，明らかに 1 通りですが，10C0 = 1 なので上記に含めることができます。 そこで，○ = 0 〜 5 として，， 10C0 + 9C1 + 8C2 + 7C3 + 6C4 + 5C5 = 1 + 9 + 28 + 35 + 15 + 1 = 89 通り， になります。 (解法2) 10 点の場合の数を A10 通りとします。これは， 9 点目と 10 点目の間に線を引かない場合，9 点目より左の線の引き方に等しく，A9 通り， 9 点目と 10 点目の間に線を引く場合，8 点目と 9 点目の間には線を引けないので，8 点目より左の線の引き方に等しく，A8 通り， となって，A10 = A9 + A8，です。そして，A9，A8，．．．も同様の式がいえ，A3 = 3，A2 = 2，なので， A4 = A3 + A2 = 5，A5 = A4 + A3 = 8，A6 = A5 + A4 = 13，A7 = A6 + A5 = 21，A8 = A7 + A6 = 34，A9 = A8 + A7 = 55，A10 = A9 + A8 = 89， そこで，A10 が求める場合の数なので，89 通り，になります。 フィボナッチは様々なところに現れますが，それぞれそれなりの条件の下での，階段上り，畳敷き，星取表，伝言ゲーム，など， 典型例を覚えておくと，一目で解ける場合もあると思います。 |
|
ネコの住む家
12月11日（金） 11:28:09
43970 |