第261問の解答


1.問題 場合の数

60分の録画が可能なビデオテープがあります。
このビデオテープに、30分番組と15分番組を録画するなら、
  • 30分番組→30分番組
  • 30分番組→15分番組→15分番組
  • 15分番組→30分番組→15分番組
  • 15分番組→15分番組→30分番組
  • 15分番組→15分番組→15分番組→15分番組

5通りの録り方が考えられますね。

では、180分の録画が可能なビデオテープ30分番組と15分番組を録画するとしたら、何通り録り方が考えられますか。


2.解答例1(長野美光さん、ヒデー王子さん、トトロ@Nさん、Taroさん、CRYING DOLPHINさん、AЯOTさん、中村明海さん、鉄老さん、ぶるぼんさん、絵鞠さん、ゆんななこさん、他多数)

15分1単位で考えると30分2単位180分12単位となります。
そこでn単位を録画できる場合の数をFnとし、Fn漸化式を考えましょう。

参考図1

まず、F1=1、F2=2となります。

また、n≧3のときは、
 ・最後が1単位のとき・・・Fn-1通り
 ・最後が2単位のとき・・・Fn-2通り
より、 FnFn-1Fn-2 が成り立ちます。

そこで、順次計算していくと、F12233を得ます。

参考図2

 

答:233通り

以上


3.解答例2(C_GUMさん、sodoさん、ちーくんミミズクはくず耳さん、まるケンさん、DrKさん、M.Hossieさん、ZIMBAさん、有無相生さん、他多数)

2単位の個数で場合分けしてみます。

参考図3

  • 0個のとき:全て1単位なので1通り

  • 1個のとき:1単位10個、2単位1個なので、合計11個ステップから
      2単位の位置を選ぶ11C111通り

  • 2個のとき:1単位8個、2単位2個なので、合計10個ステップから
      2単位の位置を選ぶ10C245通り
         
    ・・・

  • 6個のとき:全て2単位なので1通り

合計=12C011C110C29C38C47C56C6
   =1+11+45+84+70+21+1
   =233通り


4.解答例3(H.Takaiさん)

下図のような12×12の経路図で考えます。

参考図4

 へ1区間進む:本問題の1単位録画する
 へ1区間進む:  〃  2単位録画する
と対応させることができます。

最初の格子点には1とおき、各格子点では左と下の格子点数字の和を順次計算することで最短経路数を計算することができます。

12単位録画する場合の数は、上図7個所格子点経路数合計と考えることができるので、1+21+84+45+11+1=233通りとなります。

なお、この7個所格子点上経路数は、解答例2で2単位の数ごとに場合分けした数字と一致しています。