【場合の数】フィボナッチ数列で階段の上り方が何通りかがわかるの?

【場合の数】フィボナッチ数列で階段の上り方が何通りかがわかるの? 場合の数

問題演習コーナー

【問題】太郎君は、荷物を部屋から物置まで運びます。このとき、太郎君が1回で運ぶことのできる荷物は1個か2個です。たとえば、3個の荷物を運ぶ場合、次の3通りあります。

  • 1回に1個ずつ、3回運ぶ。
  • 1回目に1個、2回目に2個運ぶ。
  • 1回目に2個、2回目に1個運ぶ。

全部で7個の荷物を運ぶ場合について、次の問いに答えなさい。

(1) もっとも少ない回数で運び終えたとすると、運び方は何通りありますか。

(2) (1)もふくめて、運び方は全部で何通りありますか。

【問題】では荷物を運びますが、階段上りの問題と同じ考え方をします。

(1)の解答

「もっとも少ない回数で運び終えた」とあるので、「1回で2個運ぶことがもっとも多い」と考えます。そこで、回数と荷物の個数だけに注目すると、次のようになります。

(2個、2個、2個、1個)…4回

1個が1回目から4回目のどこかに来ればいいので4通りが答えです。

(2)の解答

(1)で求めた組合せの「2個」を「1個、1個」に交換していきます。

ア (2個、2個、2個、1個)…4回

イ (2個、2個、1個、1個、1個)…5回

ウ (2個、1個、1個、1個、1個、1個)…6回

エ (1個、1個、1個、1個、1個、1個、1個)…7回

次に、アからエのそれぞれが何通りかを考えます。

  • アは(1)から4通りです。
  • イは、5回のうちから2回を2個にすればいいので、5C2=10通りです。
  • ウは、(1)と同じように考えて、2個が1回目から6歩目のどこかに来ればいいので6通りです。
  • エは見るからに1通りしかありません。

したがって、アからエまでを足して4+10+6+1=21(通り)が答えです。

シイタケくん
シイタケくん

イの5C2=10がわかりません。

イで地道にすべての場合を書き上げるなら、次のようになります。

(1回目、2回目、3回目、4回目、5回目)とすると、

(2個、2個、1個、1個、1個)

(2個、1個、2個、1個、1個)

(2個、1個、1個、2個、1個)

(2個、1個、1個、1個、2個)

(1個、2個、2個、1個、1個)

(1個、2個、1個、2個、1個)

(1個、2個、1個、1個、2個)

(1個、1個、2個、2個、1個)

(1個、1個、2個、1個、2個)

(1個、1個、1個、2個、2個)

したがって、10通りです。

この書き上げ作業では、「2個」の位置を次のように決めていきました。

【場合の数】フィボナッチ数列で階段の上り方が何通りかがわかるの?

このように、規則的に「2個」の位置を決めていくと、数え間違いを防げます。

(2)の別解(フィボナッチ数列を利用する)

(2)は、フィボナッチ数列を利用すると、1、2、3、5、8、13、21なので21通りが答えです。

トップ画像=写真AC

コメント

タイトルとURLをコピーしました