最短距離を、場合の数でするか確率でするかの違い。

質問

Cでおなじみの最短距離の問題。（＊長くてグダグダです）

縦に３区間、横に５区間ある格子状の道があり、その一番左下の端をP、一番右上の端をQとする。
AはPからQへ、BはQからPへ共に最短距離を等しい速さで進む。各分岐点での進む方向を等確率で選ぶとき、AとBの出会う確立を求めよ。

PからQ（またはQからP）を最短距離で進むなら、全体で８区間（縦３、横５）選ぶことになるので、８÷２＝４区間進んだ所でAとBは会うことになる。

出会う場所をPから
横：１　縦：３　をa
横：２　縦：２　をb
横：３　縦：１　をc
横：４　縦：０　をd
と置く。

模範解答
Aは縦、または横をそれぞれ１/２の確率で選んで進むので、
a,b,c,dを通る確率は、
d=（１/２）の四乗=１/１６
c=（１/２）の四乗×[４]C[１]=１/４
b=（１/２）の四乗×[４]C[２]=３/８
Aはabcdのいずれか１点を必ず通り、かつ２点以上を通ることはないので、
a=１－{（１/１６）＋（１/４）＋（３/８）}
=５/１６

同様にBも考え、
a=（１/２）の四乗=１/１６
b=（１/２）の四乗×[４]C[１]=１/４
c=（１/２）の四乗×[４]C[２]=３/８
d=５/１６

以上より
（１/１６）×（５/１６）+（１/４）×（３/８）+（３/８）×（１/４）+（１/１６）×（５/１６）＝２９/１２８　・・・答　　　　終

私の考え方は、
Aには
aを[４]C[１]×[４]ｃ[０]＝４通り
bを[４]C[２]×[４]ｃ[１]＝２４通り
cを[４]C[１]×[４]ｃ[２]＝２４通り
dを[４]C[０]×[４]ｃ[１]＝４通り
の進み方があり、

同様にBには
dを[４]C[１]×[４]ｃ[０]＝４通り
cを[４]C[２]×[４]ｃ[１]＝２４通り
bを[４]C[１]×[４]ｃ[２]＝２４通り
aを[４]C[０]×[４]ｃ[１]＝４通り
ある。

全体は５６の二乗＝３１３６通り
４の二乗×２＋２４の二乗×２/３１３６
回答の分母の１２８に何をかけても３１３６にはなりませんので間違ってますね。

知りたいことは、

私の考え方の誤りと、
模範解答のAはaを１－{（１/１６）＋（１/４）＋（３/８）}
=５/１６で進むとなっているが、（１/２）の４乗×[４]C[１]＝１/４ではないのか、
・・・私はAがBと出会い、その後Qに行く進み方も考えてますが、
AとBは出会えさえすれば、そこからQに行く場合の数は関係なかったり・・・？（PからQまでではなく、Pから出会う場所までの場合の数ではないか）

以上です。お願いします。

回答No.3

felicior · ベストアンサー

根本的な話ですが、場合の数で考えるときは同じ確率のものを一通りと考える必要があります。

たとえばAがaに来る経路はaの左から来る場合が一通りと
下から来る場合が三通りありますが、これらは同じ確率ではないです。
左から来る場合、aのすぐ左の角に来さえすれば、
そこは分岐ではなく一方通行でaまで来れるので確率は(1/2)^3、
下から来る場合は四区間ともすべて分岐の片方を選んで来るので、
一通りあたりの確率は(1/2)^4です。
よって5/16は(1/2)^3＋(1/2)^4×3とやっても出すことができますが
模範解答は余事象を使っているので、かえって以上のことが分かりにくくなっていますね。
b、c、dまでの確率は１通りあたり(1/2)^4なので、結局違うのはaに左から来る場合だけです。

出会った後の経路を区別しなくてよいかどうかですが、
区別しても正しく考えれば結局同じになります。
（PからQまでの確率）＝（Pからbまでの確率の和）×（bからQまでの確率の和）
ですが、このbからQまでの確率の和は１になるからです。
bから上右右右：1/2
bから右上右右：(1/2)^2
bから右右上右：(1/2)^3
bから右右右上：(1/2)^3
上の辺に出てしまえばあとは右向き一方通行なので上のような結果になります。
bを通ればどの経路を通っても最終的には皆ゴールまで行かなければいけないので
合計が１になるのは当然ですね。

お礼

ありがとうございます。やっとわかりました。

Aがそのまま真っ直ぐに上に行けば、角に着いたところで残りの経路は決まってしまう。
なので(1/2)^3。

そして角を通らないaへの行き方は
(1/2)^4×[4]C[1]ではなく、
真っ直ぐ上に行く１通りを引いた
(1/2)^4×（[4]C[1]-1）となり、
(1/2)^3＋(1/2)^4×（[4]C[1]-1）=５/１６となるんですよね！

わざわざbからQまでの経路を書いて下さってありがとうございます。
bまで行ったらQに行く確率は当然１ですよね。
・・・何故か確率でなく何通りあるのか考えてました。すみません。

feliciorさんの「場合の数で考えるときは同じ確率のものを一通りと考える必要がある」、というのが分かるようで結局分からない感じです。
気が向いたら教えて下さると嬉しいです。

回答No.5

felicior

NO.3の者です。疑問点が分かりました。

>何故分母は答えと違ってくるのか、
>場合の数を使う方法ではどうやっても解けないのか、
これについてお答えします。

高校の参考書などでは、「同様に確からしい」場合（根元事象）が全部でＮ通りあるとき
そのうちａ通りが起きる確率をa/Nと定義していると思います。
「同様に確からしい」とは何とも妙な言葉ですが、要は確率が同じということです。
つまり、同じ確率のものがN個あれば1個あたり1/Nになるという、
全く当然ではありますが、かなり特殊なケースのことを言っています。

どういうことかというと・・・
サイコロで1つの目が出る確率はと聞かれたらふつう1/6と答えますが、
これは単にサイコロに目が6つあるというだけでは出てきません。
6つの目の確率がみな同じと仮定して（与えられて）初めて言えることですよね。

そこで、もし１の目が他の目よりも２倍出やすいサイコロがあるとしたら、
単純には上の公式を適用できないことになります。
この場合１～６の目が出る確率の比はそれぞれ2:1:1:1:1:1ですから、
１の目は2/7、他の目は1/7の確率です。確率の分母はサイコロの目の数とは
本来全然関係ないことがこれで分かっていただけたと思います。

今回の道路の問題の場合に与えられているのは、それぞれの分岐に対して上に行くのと
右に行くのとが同様に確からしい(確率1/2ずつ)ということだけです。
PからQに行く経路が8C3＝56通りあることは間違いないですが、これら56通りがすべて
互いに「同様に確からしい」かどうかは何もいってないわけです。
質問者様はここで１経路あたりの確率が単純に56等分されている
と考えてしまったのが間違いの原因です。

どの経路もゴールに着く前に上辺か右辺のどちらかの道路に出るわけですが、
上辺や右辺に早々と出てしまう経路はその後は一方通行（分岐ではない）なのに対し、
内部の道をくねくねと進む経路はそれだけ二者択一を迫られる回数が増え１経路当りの確率は減ります。
分岐１回で1/2ですから、ｎ回なら(1/2)^nです。
分母はそれぞれ異なるため共通な分母56でくくることはできないわけです。
分岐5回以下の経路では1/56より大きく、6回以上では1/56より小さい確率になることも分かりますね。

上辺に出る経路は35通りありますが、
それまでに通ってきた分岐数ごとにわけて確率を計算すると、
３回・・・(1/2)^3×2C2＝1/8
４回・・・(1/2)^4×3C2＝3/16
５回・・・(1/2)^5×4C2＝3/16
６回・・・(1/2)^6×5C2＝5/32
７回・・・(1/2)^7×6C2＝15/128

右辺に出る経路21通りも同様に、
５回・・・(1/2)^5×4C4＝1/32
６回・・・(1/2)^6×5C4＝5/64
７回・・・(1/2)^7×6C4＝15/128

これらを合計するともちろん１になります。
場合の数の合計は依然56でありながら、確率の分母がそれぞれ異なることを確認してください。
以上、ご理解いただけたでしょうか。

ちなみに・・・
もし問題の設定で「全ての経路は等確率（同様に確からしい）とする」と書いてあったならば、
むしろ質問者様の最初の考え方が正解になります。
ただしその場合逆に、それぞれの分岐で上と右に分かれる確率は1/2ではなくバラバラになります。

お礼

はい、今度こそ理解できました。
最短経路の確率を、場合の数で解ける問題が特殊だったんですね。
これから最短経路の問題を見る目が変わりそうです。
解説ありがとうございました。

回答No.4

chie65535

経路を単純にして
ａ－・－Ｑ
|　　|　　|
・－ｂ－・
|　　|　　|
Ｐ－・－ｃ
で考えて見ましょう。

ＰからＱに至るルートは４Ｃ２で６です。
上・上・(右)・(右)　ａを通る
上・右・上・(右)　ｂを通る
上・右・右・(上)　ｂを通る
右・上・右・(上)　ｂを通る
右・上・上・(右)　ｂを通る
右・右・(上)・(上)　ｃを通る
しかありません。

このうち「()」が付いた方向は「そっちに行くしかない」ので、確率は１００％です。

「()」が付かない場合は「1/2」の確率で選びます。

なので
上・上・(右)・(右)　ａを通る　確率は1/4
上・右・上・(右)　ｂを通る　確率は1/8
上・右・右・(上)　ｂを通る　確率は1/8
右・上・右・(上)　ｂを通る　確率は1/8
右・上・上・(右)　ｂを通る　確率は1/8
右・右・(上)・(上)　ｃを通る　確率は1/4
です。

つまり、ａを通る確率は1/4、ｂは4/8＝1/2、ｃは1/4です。

ＱからＰに至るルートは４Ｃ２で６です。
（対称なので説明は略）

よって、出会う確率は
(1/4)*(1/4)+(1/2)*(1/2)+(1/4)*(1/4)=6/16=3/8
です。

さて、ここで「６の２乗」は何を意味するでしょうか？

それは「Ａ、Ｂが取りうるルートの総数」です。

出会う確率の分母を「Ａ、Ｂが取りうるルートの総数」つまり「３６」にして良いのは「Ａ、Ｂが通る６つのルートの確率がすべて等しく、どのルートの確率も1/6で起きる時のみ」です。

しかし６つのルートのそれぞれの確率は等しくなく
上・上・(右)・(右)　ａを通る　確率は1/4
上・右・上・(右)　ｂを通る　確率は1/8
上・右・右・(上)　ｂを通る　確率は1/8
右・上・右・(上)　ｂを通る　確率は1/8
右・上・上・(右)　ｂを通る　確率は1/8
右・右・(上)・(上)　ｃを通る　確率は1/4
です。

もし、上記の確率を無視し、すべてのルートの確率が同じなら
Ａがａを通る確率が1/6（ａを通るのは６つのルートのうち１つ）
Ａがｂを通る確率が4/6（ｂを通るのは６つのルートのうち４つ）
Ａがｃを通る確率が1/6（ｃを通るのは６つのルートのうち１つ）
Ｂがａを通る確率が1/6（ａを通るのは６つのルートのうち１つ）
Ｂがｂを通る確率が4/6（ｂを通るのは６つのルートのうち４つ）
Ｂがｃを通る確率が1/6（ｃを通るのは６つのルートのうち１つ）
になるので、ａ～ｃの各地点で出会う確率は
ａで出会う確率＝(1/6)*(1/6)
ｂで出会う確率＝(4/6)*(4/6)
ｃで出会う確率＝(4/6)*(4/6)
となり「ａまたはｂまたはｃ」で出会う確率は上記を足した
(1/6)*(1/6)+(4/6)*(4/6)+(1/6)*(1/6)=1/36+16/36+1/36=18/36
なので「分母が４Ｃ２の２乗の３６」となり「質問者さんの思った通り」になります。

しかし、これは「それぞれのルートで、通る確率が異なるという事実を完全に無視」しています。

つまり、質問者さんが、元の問題で「求める確率はX／[８]C[３]^２となるはず」と考えるのは「それぞれのルートで、通る確率が異なるという事実を完全に無視している事に他ならない」のです。

なので「それぞれのルートで、通る確率が異なるという事実」に気付けない限り、永久に「分母が合わない」と悩む事になります。

そういう訳で「場合の数を確率の分母に出来るのは、すべての『場合』が等確率で起きる時」のみです。

逆に言うと「それぞれの『場合』が起きる確率が異なる時には、場合の数『ｎＣｍ』は使えない」と言う事です。

極端な例ですが、以下のような確率を求める時「場合の数」は使えません。

「１が出やすいように細工してあるサイコロがあり、１が出るのは４／５の確率、２～６が出るのは、それぞれ１／２５の確率である。このサイコロを２回振って、１が連続して出る確率はいくらか？」

当然、答えは１６／２５です。

「出る目は１から６までの６通りだから、確率の分母は６の２乗の３６のはずだ」と考えると間違いです。「１が多く出る細工」を無視してはいけません。

これに気付けば
＞場合の数で考えるときは同じ確率のものを一通りと考える必要があります
との説明も「なんとなくピンと来る」でしょう。

お礼

ありがとうございます、ようやく納得できました。
場合の数は確率が等しい時にしか使えないのですね・・・。
本当に分かりやすいように説明して下さってありがとうございます。
このことを教科書に載せてほしかったです。

回答No.2

sanori

こんばんは。

Ｐの座標を（０，０）、Ｑの座標を（５，３）と書くことにしますね。

＞＞＞模範解答のAはaを１－{（１/１６）＋（１/４）＋（３/８）}
=５/１６で進むとなっているが、（１/２）の４乗×[４]C[１]＝１/４ではないのか、

つまり、Ａが（０，０）をスタートして、点ａ（１，３）を踏む確率ですよね？

Ａが点ａ（１，３）に進むまでの経路は、あなたがおっしゃる　4Ｃ1　通り、
すなわち、
＜あ＞（０，０）→（１，０）→（１，１）→（１，２）→（１，３）
＜い＞（０，０）→（０，１）→（１，１）→（１，２）→（１，３）
＜う＞（０，０）→（０，１）→（０，２）→（１，２）→（１，３）
＜え＞（０，０）→（０，１）→（０，２）→（０，３）→（１，３）
の４通りあります・・・

・・・が、しかし、それをそのまま確率計算に使ってはいけません。

＜え＞の経路の、最後のステップを考えましょう。
すなわち、
（０，３）→点ａ（１，３）
です。

このステップの確率は、１／２　ではなく　１　です！！！！！
（つまり、１００％）

なぜならば、（０，３）は地図の隅にあるため、最短距離を進むためには、（０，３）から進む方向は、点ａ（１，３）に進むという１種類の方向しかないからです。

ですから、
＜あ＞、＜い＞、＜う＞　の確率は、それぞれ　１／１６。
＜え＞の確率は、その２倍の　２／１６　です。
よって、Ａが点ａを踏む確率は、
１／１６　＋　１／１６　＋　１／１６　＋　２／１６　＝　５／１６
となります。

質問者様は、数学の素養があるようですので、
この先は、たぶん大丈夫だと思います。

以上、ご参考になりましたら。

お礼

こんばんは。回答ありがとうございます。

やはり解答が正しかったのですね。aの経路を全部書いて下さったので、すごく理解できました。
自分もそこまで考え付けばよかったのですが・・・。

とても参考になりました。

回答No.1

chie65535

＞模範解答のAはaを１－{（１/１６）＋（１/４）＋（３/８）}
＞=５/１６で進むとなっているが、（１/２）の４乗×[４]C[１]＝１/４ではないのか

違います。
Ａがａに至る道は
右→上→上→上
上→右→上→上
上→上→右→上
上→上→上
と分岐した場合の４通りで、それぞれの確率は
右→上→上→上＝1/16
上→右→上→上＝1/16
上→上→右→上＝1/16
上→上→上＝1/8
です。拠って、1/16+1/16+1/16+1/8=5/16です。

ここで注意しないとならないのは「上→上→上と分岐して左上隅に至った場合は、無条件に右に行くしかない」と言う事です。

Ｂがｄに至るのも「下→下→下と分岐して右下隅に至って無条件に左に行く」と言う場合です。

「隅を通った場合は分岐が１回減る」のを忘れないように。

＞AとBは出会えさえすれば、そこからQに行く場合の数は関係なかったり・・・？
ですね。関係ありません。

お礼

皆さんの回答で模範解答の意味が分かりました。
・・・・のですが、それが何故Cで出来ないのでしょうか。
何が納得できないのかと言うと、
移動するAのとる経路：PからQの最短距離は[８]C[３]通り。
その各々に対してQからPへ移動するBのとる経路も[８]C[３]通り。
よって、起こりうる全ての場合は[８]C[３]^２通り。
その内、a,b,c,dでそれぞれ合う確率をXとします。

すると求める確率はX／[８]C[３]^２となるはず。
ですが[８]C[３]^２＝３１３６
素因数分解すると３１３６＝２^６・７^２
解答の答えの分母は１２８。
１２８＝２^７
３１３６＝２^６・７^２はどんなXの値が分子にきても１２８＝２^７にはなりません。

何故分母は答えと違ってくるのか、
場合の数を使う方法ではどうやっても解けないのか、
どなたか回答よろしくお願いします。

あとfeliciorさんの「場合の数で考えるときは同じ確率のものを一通りと考える必要がある」を私に分かるように・・・かなり簡単に説明して頂けないでしょうか。