ひたすら受験問題を解説していくブログ
東京大学2014年後期総合科目II第1問B
todai_2014_sogo2_2q-1.png
todai_2014_sogo2_2q-2.png
todai_2014_sogo2_2q-3.png

解説


やっていることは本年度で一番高度ですが,問題を解く上での補題的なものが問題文に書かれているため,難易度は並以下になっています。ここでは補題部分も証明しつつ解説します。満点狙いの方は,補題自体をどう導いているのか(証明ではなく何故この補題を考えたか)も考えてみると面白いかもしれません。

(B-1)
”Σ振り分け回数×確率”なので,ある振り分け装置の骨格(振り分け先は違うがコンベアの形は同じ)があった場合,振り分け回数の少ないところから1/2,1/4,3/16,1/16と埋めていくことがその骨格の最小の行き先割り当てです。また,異なる骨格では,1/2の回数が1少なくなることは,他の振り分け回数が1増えること以上に時間を短縮します。よって,1/2をまず振り分け,1/4とそれ以外で同じことを考えると,1/4だけ振り分けるものが最小だと分かります。よって,以下のような振り分け装置の組み合わせが最小で,計算すると,
1/2+2×1/4+3×(3/16+1/16)=7/4
todai_2014_sogo2_2a-1.png
ちなみに,他の骨格は次のものしかないので,総当り余裕です。
todai_2014_sogo2_2a-2.png

【参考】
ずるいといわれそうですが,証明は必要ないとのことなので,(B-2)とF1の内容を使ってしまいます(B-1下に記載の前提はB-1でも満たしています)。1/16と3/16が最長かつ隣になるものでOKだと分かります。

(B-2)
同じ骨格においてD1と振り分け時間の異なる任意のDkを交換してやることを考えます。交換前から交換後を引くと,
todai_2014_sogo2_2a-4.png
となります。初めのものが最適な組み合わせならば,右辺≦0になりますが,P1<Pkかつt1≠tkなので,t1>tkとなります。つまり,D1の振り分け時間t1は最大となります。

次に,振り分けの終点では必ず2個の同一時間のものが生じるので,t1と同じtkが存在しますが,t2<tkならば,先ほどと同様にD2とDkを交換してやると,時間が短縮できてしまい,最短であるという仮定に矛盾してしまいます。

【参考】F1
もし最適かつD1とD2がとなりあっていない組み合わせがあるとしても,D1とD2は最長の時間であり,D1には同時間のペアDiが存在します。このDiとD2を交換しても振り分け時間に変化はなく,交換後も最適な組み合わせであり,D1とD2は隣り合っています。

(B-3)
D1,D2はともに一回の振り分けが免除されているので,それぞれ1単位ずつかかる時間が小さくなっています。D1,D2以外の振り分け時間は変わらないので,平均振り分け時間はP1+P2だけ小さくなり,
T'=T-P1-P2

【参考】F2
Sが最適ではないとすると,Sとは異なり,かつ,(B-3)を満たす最適な組み合わせS''が存在します。Sとこの最適な組み合わせのいずれの場合にもD1とD2を一緒にしてしまえば,(B-3)より,ともにP1+P2だけ小さくなるので,S'の平均振り分け時間はS''由来のものより大きくなるので最適にはなりません。
よって,S'が最適ならばSも最適になります。

(B-4)
順にF2を使っていくだけです。つまり小さいもの同士を次々に隣り合うようにして合併していくことになります。すると,最終的にできたものが最適な組み合わせならば,F2によって順次最適だと判定が下せるということです。"81分の"を省略して書いていくと,
todai_2014_sogo2_2a-3.png

となります。枝分かれ部分の数字を足して81で割れば平均振り分け時間になります。
(81+48+21+9+33+15)/81=23/9

東京大学2014年後期総合科目II解説に戻る

スポンサーサイト

テーマ:大学受験 - ジャンル:学校・教育

コメント
コメント
コメントの投稿
URL:
本文:
パスワード:
非公開コメント: 管理者にだけ表示を許可する
 
トラックバック
トラックバック URL
http://jukenkaisetsu.blog.fc2.com/tb.php/428-31f84ac4
この記事にトラックバックする(FC2ブログユーザー)
トラックバック