Evolton

京都大学 2015年度 前期日程 第2次学力試験文系数学 第3問

6個の点A, B, C, D, E, Fが下図のように長さ1の線分で結ばれているとする.
各線分をそれぞれ独立に確率12で赤または黒で塗る.
赤く塗られた線分だけを通って点Aから点Eに至る経路がある場合はそのうちで最短のものの長さをXとする.
そのような経路がない場合はXを0とする.
このとき,n=0, 2, 4について,X=nとなる確率を求めよ.

問題の図

難易度5/ 10計算量4/ 10目安15分

確率、場合の数 数え上げ、余事象、場合分け

方針

図の辺を確認すると、A から E への長さ2の経路は A−F−E と A−B−E の2本であり、長さ2が存在しない場合に残る長さ4の経路は A−B−C−D−E である。全7辺の赤黒の塗り方は等確率なので、塗り方の個数を数える。まず長さ2の赤経路がある場合を包除原理で数え、次に長さ2がなく長さ4だけがある場合を必要十分条件で数える。最後に余事象で X=0 を出す。

解答

図の辺は AF,FE,EB,AB,ED,DC,BC の7本である。各辺は独立に赤または黒に塗られるので、全ての塗り方は 27=128 通りであり、すべて等確率である。

まず X=2 の場合を数える。A から E への長さ2の経路は A−F−E,A−B−E の2本である。経路 A−F−E が赤だけで通れるためには AF,FE の2本が赤であればよく、残り5本は任意であるから 25=32 通りである。同様に、経路 A−B−E が赤だけで通れる塗り方も32通りである。

ただし、両方の長さ2経路が赤で通れる場合は重複して数えている。この重複は AF,FE,AB,BE の4本が赤で、残り3本が任意の場合なので 23=8 通りである。よって #{X=2}=32+32−8=56 であり P(X=2)=56128=716 である。

次に X=4 の場合を数える。長さ2の赤経路が存在せず、かつ赤だけで A から E に行けるには、図から長さ4の経路 A−B−C−D−E が赤で通れることが必要である。このためには AB,BC,CD,DE の4本が赤でなければならない。

さらに、長さ2の経路 A−B−E が赤にならないためには、すでに AB は赤なので BE は黒 でなければならない。また、長さ2の経路 A−F−E が赤にならないためには、AF,FE の少なくとも一方が黒であればよい。したがって AF,FE の塗り方は (赤,黒),(黒,赤),(黒,黒) の3通りである。よって #{X=4}=3 であり P(X=4)=3128 である。

最後に、赤だけで A から E へ行く経路がない場合は X=0 である。A から E へ行ける場合の最短長は、上で数えたように2または4であるから P(X=0)=1−P(X=2)−P(X=4) である。したがって P(X=0)=1−56128−3128=69128 であり P(X=0)=69128 である。

別解

解法2(到達不能を先に直接数える)

方針

点 A から出る2辺 AF,AB の色で場合分けし、まず到達不能な69通りを直接数える。X=4 の3通りも必要条件から直接確定し、残りを X=2 とする。主解法とは補集合を取る順序を逆にした、全設問を完結する数え上げである。

解答

X=0 は、赤線だけでは A から E に到達できない場合を直接数えても求められる。点 A から出る辺は AF,AB の2本であるから、この2本の色で分ける。

AF,AB がともに黒のとき、A からどこにも進めないので、残り5本は任意で 25=32 通りである。

AF が赤、AB が黒のとき、F までは到達できる。E に到達しないためには FE が黒であることが必要十分であり、残り4本は任意で 24=16 通りである。

AF が黒、AB が赤のとき、B までは到達できる。E に到達しないためには BE が黒で、さらに下側の経路 B−C−D−E がすべて赤ではないことが必要十分である。辺 BC,CD,DE の塗り方は、全部赤の1通りを除いた 23−1=7 通りであり、FE は任意なので 7⋅2=14 通りである。

最後に AF,AB がともに赤のときは、F と B まで到達できる。したがって FE と BE はともに黒でなければならず、さらに B−C−D−E がすべて赤ではない必要がある。よって 7 通りである。

以上より到達不能な塗り方は 32+16+14+7=69 通りであり、P(X=0)=69128 を得る。これは余事象で求めた値と一致する。

次に X=4 を直接数える。長さ4の経路 A−B−C−D−E の4辺はすべて赤であり、長さ2の経路 A−B−E を作らないため BE は黒である。また A−F−E を作らないため、AF,FE の少なくとも一方が黒である。したがって AF,FE の選び方は3通りであり#{X=4}=3である。

全128通りは X=0,2,4 のいずれかに分かれるので#{X=2}=128−69−3=56である。よってP(X=0)=69128,P(X=2)=716,P(X=4)=3128となる。

総評

難度5、計算量4。目安時間は15分。原図の7辺を正確に読み取ることが最重要である。第1解法は長さ2の2経路を包除原理で数え、X=4 を直接、X=0 を余事象で求める。第2解法は点 A から出る2辺で到達不能を直接69通りと数え、X=4 の3通りを除いてX=2 を求める。異なる順序の数え上げが相互検算になる。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る京大の確率の問題で問題集を作る

出典: 京都大学 2015年度 第2次学力試験 数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。