第７９問の解答

問題　［規則性］

問題図

マサル研究所では、自己増殖型ロボットの研究をしています。

このロボットは、自分と同じタイプのロボットを１時間に１個作ることができます。また、作られたばかりのロボットは始めの１時間は動作テストのためにロボットの生産をしませんが、その後はやはり同じように１時間に１個のロボットを作ります。

いま、作られたばかりのロボットを１個用意しました。そして、１時間ごとにロボットの個数を調べたところ、左図のようになっていました。

さて、このようにして１時間ごとに５００時間後までを調査するとき、ロボットの個数が３の倍数になっていることは何回あるでしょうか。

解答例１

マサルさん

算チャレでもおなじみのフィボナッチ数列に関する問題です。

フィボナッチ数列（一般項をFnとします）は、Fn＝Fn-1＋Fn-2となるような数列で、例えば、
　１、２、３、５、８、１３、２１、３４、５５、・・・
のように、本問のロボット個数もフィボナッチ数列になります。

なぜなら、作られたばかりのロボットは働くことはできませんね。
この子供ロボットを○とし、n時間後の個数をrnとします。

また、１時間経過したロボットは働く（生産する）ことができます。
この大人ロボットを◎とし、n時間後の個数をRnとします。

大人、子供合わせたロボット数をFnとして、時間ごとの様子を以下の表に表してみます。

参考図１

すると、
　Fn＝Rn＋rn　　　・・・　（１）
　Rn＝Rn-1＋rn-1　・・・　（２）
　rn＝Rn-1　　　　　・・・　（３）
が成り立ちます。

（２）、（３）より、
　　Rn＝Rn-1＋rn-1＝Rn-1＋Rn-2　　・・・　（４）

また、（３）、（４）より、
　　rn＝Rn-1＝Rn-2＋Rn-3＝rn-1＋rn-2　・・・　（５）

（１）、（４）、（５）より、
　Fn＝Rn＋rn＝（Rn-1＋Rn-2）＋（rn-1＋rn-2）
　　　＝（Rn-1＋rn-1）＋（Rn-2＋rn-2）
　　　＝Fn-1＋Fn-2　・・・　（６）

（６）より、ロボット数がフィボナッチ数列の性質を持っていることが分かりました。

あとは３の倍数がどの頻度で表れるかを調べるだけです。

実は、結論から言うと３の倍数は４回に１回現れます。これは少し調べてみれば分かります。
これは、３で割った余りを考えると分かりやすいはずです。

参考図２

式で考えると、（６）より、
　Fn+1＝Fn＋Fn-1＝(Fn＋Fn-1)＋Fn-1＝Fn＋2Fn-1
　Fn+2＝Fn+1＋Fn＝(Fn＋2Fn-1)＋(Fn＋Fn-1)＝2Fn＋3Fn-1
　Fn+3＝Fn+2＋Fn+1＝(2Fn＋3Fn-1)＋(Fn＋2Fn-1)＝3Fn＋5Fn-1
よって、
　Fn+4＝3Fn+1＋5Fn＝3(Fn+1＋Fn)＋2Fn・・・　（７）

（７）より、Fnが３の倍数だと、Fn+4も３の倍数となります。
逆に、Fnが３の倍数でないと（３で割った余りが１または２）、2Fnを３で割った余りは２または１となって、３の倍数でありません。

上図より、１〜４時間後では、３時間後のみ余りが０なので、その後も４時間ごとに余りが０（３の倍数）が現れることになります。

従って、１〜５００時間後までだと、３の倍数は、
　５００÷４＝１２５回となることが分かります。　

答：　１２５回

以上