2007年8月11日(土曜日)
連絡網の計算
テレビを見ていたら、連絡網の問題が出ていました。詳しくは覚えていませんが、だいたいこんな感じだったような。
- クラスの連絡網がある。
- 最初に、先生が生徒の一人に電話連絡する。
- 電話を受けた生徒は、ただちに他の生徒2人に電話する。
- 一回の通話には一分かかるものとする。
- 一人の生徒が重複して連絡を受けることはないものとする。
これで、何分か経った時に連絡を受けている人の数を求めます。
答えの解説は特になかったので、私なりに考えてみました。考え方はこんな感じ。
- 連絡を受けた人には、3つのステータスがある。
- 電話を受けた直後 = 残ノルマ2
- 一人に電話をかけ終わった = 残ノルマ1
- 二人に電話をかけ終わった = 残ノルマ0
- 残ノルマ1 と 2 の人は電話をかける。電話をかけると、以下の効果が発生する。
- 自身の残ノルマが 1 減少する (残ノルマ2の人は残ノルマ1に、残ノルマ1の人は残ノルマ0になる)
- 残ノルマ2の人が増える
このことから、それぞれの人数はどうなるか考えると、
- 残ノルマ2 の人数 = 1分前の残ノルマ2の人数 + 1分前の残ノルマ1の人数
- 残ノルマ1 の人数 = 1分前の残ノルマ2の人数
- 残ノルマ0 の人数 = 1分前の残ノルマ0の人数 + 1分前の残ノルマ1の人数
となります。初期状態はどうかというと、先生を数に入れるなら、先生はノルマ1とみなすことができますから、
- 残ノルマ2 の数 = 0
- 残ノルマ1 の人数 = 1
- 残ノルマ0 の人数 = 0
ということになります。これをふまえて表にしてみると、こんな感じになります。
| 時間 | ノルマ2 | ノルマ1 | ノルマ0 | 合計 |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 2 |
| 2 | 1 | 1 | 1 | 3 |
| 3 | 2 | 1 | 2 | 5 |
| 4 | 3 | 2 | 3 | 8 |
| 5 | 5 | 3 | 5 | 13 |
| 6 | 8 | 5 | 8 | 21 |
| 7 | 13 | 8 | 13 | 34 |
| 8 | 21 | 13 | 21 | 55 |
| 9 | 34 | 21 | 34 | 89 |
| 10 | 55 | 34 | 55 | 144 |
見事にフィボナッチ数列になりますね。先生を数に入れない場合は、単純にここから 1 を引けば良いことになります。
- 「連絡網の計算」にコメントを書く
関連する話題: メモ
- 前(古い): 2007年8月10日(Friday)のえび日記
- 次(新しい): 2007年8月15日(Wednesday)のえび日記
