理系男子の独り善がり

仕事や生活に役立ちそうな(実際に役立つかは別として)数学・物理ネタをつらつらと書いていこうと思ってます.

東大の総合科目(後期試験)は,ややこしや~ややこしや~ 2014第1問B

懲りずに問題を解いてみました.第1問Bは,空港のベルトコンベアをモデル化しています.「平均振り分け時間」をどのような量であると解釈するかがキーなのかな?と思いました.

※2014/3/30 一部追記ならびに記述の修正をおこないました.

 

(B-1)とりあえず,簡単な具体例で感じをつかむ

平均振り分け時間は,荷物の割合を確率ととらえ、それぞれの荷物の振り分け時間を確率変数とした「期待値」であると解釈できれば,しめたもんです.ただし,通常であれば確率変数は事象ごとに確定したものとして与えられますが*1,いまの場合は組合せ(何段目で振り分けられるか)によって変わるという特徴があります.

f:id:miwotukusi:20140326000030p:plain

 

そのイメージをつかませようとしているのが,この1つ目の問いだと思います.(B-2)以降の問いにも繋がってくるので,そちらを見てから回答を出すという手もアリといえばアリです.大きな確率を持っている荷物をなるだけ早く振り分けてしまえばよいという結論に至ります.(B-2)では,そのことを具体的に示すことになります.

 

(B-2) 「量の多い行き先には早く振り分ければよいこと」を証明する

ここは純粋に数式の扱いで証明することを考えます.ただ,単なる式変形だけでは導くことはできません.まず,期待値であるということから,平均振り分け時間がどのような式で表されるかを考えます.

f:id:miwotukusi:20140326002001j:plain
 
「最適な装置の組合せ」になったとき,このTが最小値をとることになります.
組合せが変わって,ti(iは1~nの数)の値が変われば値は大きくなってしまうわけです.ただ,この考え方だけではうまく証明はできません.Pi<Pj(i<j)という式をうまく組み合わせる必要があります.
そこで,最適な装置の組合せからDiとDjを入れ替えることを考えます.これは上の式で言えば,tiとtjを入れ替えることに対応します.これらを入れ替えても,Tが変わらないこともある(最適な装置の組合せは一通りとは限らない)ことを考慮すれば
f:id:miwotukusi:20140412104346j:plain
 
という不等式が導かれます.ここまでくれば,tiとtj(i<j)の大小関係が導かれます.そして,これは「大きな確率を持っている荷物をなるだけ早く振り分けてしまえばよい」ということを教えてくれます.式の上でいえば「大きなPiに対しては,小さいtiを乗じるようにする」ということです.
さらに,「D2の振り分け時間もD1と同じ値になることを示せ.」については,上の不等式の関係から「D1とD2は最後に末端で振り分けられる」こと.つまり,後から出てくる「隣接する」関係であることを言えればいいということになります.

 

(B-3) 「隣接する」部分を簡略化する手続き

ちょっとタイトルが変な言い回しになっていますが,「隣接する」部分をDというものに置き換えてしまうという話です.図にした方がわかりやすいですね.

f:id:miwotukusi:20140326213515p:plain

 

ここの問題では「最適な」ことは考えていません.ただ,グラフの末端でD1とD2が隣接しているという条件があるだけです.ですから,上の図のように,グラフの最下段にD1とD2がない場合もあるわけです.

 

(B-4) 簡略化の手続きを使って,最適なグラフを作り上げてしまう

(B-3)はD1とD2だけを簡略化することを考えていましたが,当然S’に対してS’’を,S’’に対してS’’’を考えることができるはずです.そうやって「遡っていく」ことを考えるわけです.

まず,(B-3)でおこなった簡略化を割合(確率)の小さい2つについておこないます.簡略化された部分を一つの行先として,再度割合(確率)の順に並び替え,その中で小さい2つに対して簡略化を再度おこないます.これを繰り返すと,下のように簡略化されて行先がどんどんと集約されていきます.

f:id:miwotukusi:20140326221923p:plain

f:id:miwotukusi:20140326221939p:plain

 
グラフが完成すれば,あとは期待値を計算するだけですね.
 
この第2問はきちんと文章を読めれば,先の経済の問題よりはやさしいように思います.図形的なイメージが使えるところも,考えやすさのポイントだと思います.

*1:たとえば,宝くじの当選金の期待値を考えるとき,当選確率に対して当選金が確率変数になります