懲りずに問題を解いてみました.第1問Bは,空港のベルトコンベアをモデル化しています.「平均振り分け時間」をどのような量であると解釈するかがキーなのかな?と思いました.
※2014/3/30 一部追記ならびに記述の修正をおこないました.
(B-1)とりあえず,簡単な具体例で感じをつかむ
平均振り分け時間は,荷物の割合を確率ととらえ、それぞれの荷物の振り分け時間を確率変数とした「期待値」であると解釈できれば,しめたもんです.ただし,通常であれば確率変数は事象ごとに確定したものとして与えられますが*1,いまの場合は組合せ(何段目で振り分けられるか)によって変わるという特徴があります.
そのイメージをつかませようとしているのが,この1つ目の問いだと思います.(B-2)以降の問いにも繋がってくるので,そちらを見てから回答を出すという手もアリといえばアリです.大きな確率を持っている荷物をなるだけ早く振り分けてしまえばよいという結論に至ります.(B-2)では,そのことを具体的に示すことになります.
(B-2) 「量の多い行き先には早く振り分ければよいこと」を証明する
ここは純粋に数式の扱いで証明することを考えます.ただ,単なる式変形だけでは導くことはできません.まず,期待値であるということから,平均振り分け時間がどのような式で表されるかを考えます.
(B-3) 「隣接する」部分を簡略化する手続き
ここの問題では「最適な」ことは考えていません.ただ,グラフの末端で と が隣接しているという条件があるだけです.ですから,上の図のように,グラフの最下段に と がない場合もあるわけです.
(B-4) 簡略化の手続きを使って,最適なグラフを作り上げてしまう
(B-3)は と だけを簡略化することを考えていましたが,当然 に対して を,に対してを考えることができるはずです.そうやって「遡っていく」ことを考えるわけです.
まず,(B-3)でおこなった簡略化を割合(確率)の小さい2つについておこないます.簡略化された部分を一つの行先として,再度割合(確率)の順に並び替え,その中で小さい2つに対して簡略化を再度おこないます.これを繰り返すと,下のように簡略化されて行先がどんどんと集約されていきます.
*1:たとえば,宝くじの当選金の期待値を考えるとき,当選確率に対して当選金が確率変数になります