【問題解説】最短経路の確率問題の罠 - 数学が好きなサラリーマンのブログ

f:id:mathbanker:20180926233228j:plain

今回は、【問題解説】編で、最短経路の確率問題について。

おいおいセンターの問題解説どうしたよ、と言われそうだが、別にやめたわけではなくて番外編的な位置付けで読んでいただきたい。かつ、センター解説は「です・ます」調で寄稿しているが、実は途中で書きにくいなと思っていたため、センター解説以外はもともとのスタイルの口調に戻させていただきたい。

なぜ今回最短経路の問題解説なのかというと、きっかけは些細なもので、数学とは全く別の観点で最短経路について検索をしていたところ、某質問サイトに数学の最短経路の問題がでてきていて（しかも同じようなのが複数）、回答者がことごとく間違った解答で説明していたので、僕なりに正しい説明をしたいと思ったゆえである。なぜその質問サイトの場で直接回答ではないのかという点については、~~更新頻度を上げる為~~このサイトを見てくれている人の中で、これがわからない人の方を救いたいが為に他ならない。

で、具体的にどんな問題かというと、下の図を見てほしい。

f:id:mathbanker:20171109195150j:plain

見たことある人が多いと思うが、問題としては

A地点からB地点へ最短経路で向かうとき、Cを通る確率を求めよ。ただし、上と右の両方に進める場合、同じ確率で進むものとする。

というものだ。

簡単じゃないかと、$ \frac{12}{35}$と答えた人。あなたの問題点は、確率を正しく理解できていないということ以上に、この流れでその結論の話をするわけがないのに、自分の答えを疑わなかったことだ。

多くの人がきっと、$ A \rightarrow B $の行き方が全部で ${}_7 \mathrm{C} _3=35$ 通りで、$C$を通るのが ${}_4\mathrm{C}_1 \times {}_3\mathrm{C}_1 =12$ 通りだから、 $ \frac{12}{35}$ と計算したに違いない。

確率では前提としている分母のそれぞれが同程度に期待できる必要がある（数学的表現で言えば同様に確からしくある必要がある）。例えば、格闘技の素人である僕とボクシングチャンピオンが本気のボクシング対決をするとき、勝つか負けるかだから$ \frac{1}{2}$と考えるのは間違っている。実際の確率は当然圧倒的に僕が負ける確率が高くなる。

・・・と言われても、この問題においては$35$通りは同様に確からしいんじゃないの？と思っている人もきっといるだろうから、こう考えてみてほしい。スタート地点$A$から上に進むか右に進むかは、コインを投げて決めていく。裏が出たら上、表が出たら右とする。このとき重要なのは、コインを投げられないような点があるということだ。

例えば3連続裏が出たとしよう。そうすると左上の角に到達する。するとここからはコインを投げられず（裏がでても行き場がない）、Bというゴールに向かって右にまっすぐ進むしかない。ゆえに、この経路を進む確率は $ \left( \frac{1}{2} \right)^{3} =\frac{1}{8}$となる。
次に、4連続表が出たとする。すると$A$からまず右にまっすぐ進んで、上に進むことになる。先程と同様右下の角まできたら、コインを放棄し$B$に向かって確率1で上がっていくしかない。するとこの経路の確率は $ \left( \frac{1}{2} \right)^{4} =\frac{1}{16}$となり、先ほどと異なる。つまり、経路によって確率は異なることがわかったので、分母を$35$とすることは同様に確からしくない。

では、どうやって解くのか。解法は幾つか存在するが、今回はそのうちの一つを紹介したい。

確率では先程述べたように同様に確からしいことを前提に分母を置くが、この問題の落とし穴は$A \rightarrow B$の最短経路のパターン$35$通りが同様に確からしくないということだった。であれば、同様に確からしくなるようにとればいい。

そもそものところから始めると、先程は例を挙げて同様に確からしくないことを説明したが、もっと一般になぜ$35$通りは同様に確からしくないのだろうか。

問題文の但し書きに、上と右の両方に進める場合、同じ確率で進むものとする、とある。これは同時に、上と右の両方に進めないときは同じ確率にはならないということも意味している。先ほどの例でいうところのコインが投げられないような場所、一番上の辺についたときと一番右の辺についたときだ。前者は右に行くしかないし、後者では上に行くしかない。これらの場所では確率1で移動が起きてしまうため、他の確率$\frac{1}{2}$で移動するような場所と状況が異なる。では同様に確からしく移動させるためにはどう考えればいいかというと、この問題の四角形の外側へ飛び出すことを許してしまえばいい。

え？そんなことしていいの？と思うかもしれない。こう考えてもらいたい。同様に確からしくするために外側へ飛び出すことを許す代わりに、この問題の目的が保たれるようにするためにはどうすればいいかを考えるのである。飛び出すようにしたいけれども、問題は飛び出すことなく$B$にたどり着かなくてはいけない。この二律背反な状況を打開するためには、どちらかをどちらかに寄せて考える必要がある。といっても、飛び出した分を飛び出さない場合に寄せるのは元の検討に戻ってしまうから、飛び出さない場合を飛び出す場合に寄せて考えるのだ。具体的に何を考えるのかというと、最短経路で$B$にたどり着くということが、外に飛び出す場合にどういう状況と同じなのかということを考えるのである。

外に飛び出して自由に上へ右へ行ける場合、まず最短経路が何を意味するのか考えてみる。そもそも最短経路って何だっけである。これは言わずもがな、移動回数が一番少ないことを意味している。具体的に言うと、7回移動すると$B$にたどり着く。そうすると、外に飛び出る場合も移動回数は7回だ。そして外にでて自由に動き回った分の確率は、実際は$35$通りのなかに溶け込んでいる（だからこそ同様に確からしくないのである）。

ということで、7回移動した場合の経路全体というのが同様に確からしいものである。7回移動した場合の経路全体の場合の数は、7回それぞれ上か右に進めるのだから$2^{7}$通りである。この中で$C$を通る場合の数は、$C$にたどり着くまでは${}_4\mathrm{C}_1$通り、Cに着くまでに4回移動しているので残り3回は自由に移動ができて$2^{3}$通りとなる。

ゆえに求める確率は $$ \frac{{}_4\mathrm{C}_1 \times 2^{3}}{2^{7}}=\frac{1}{4} $$ となる。

なんとなくいつもの感じで解くのではなくて、しっかりと仕組みを理解しロジカルに考えないと足元を救われることがある。それを体感できるいい問題だなと思うけど、逆にこんな問題があるから数学嫌いが量産されるのかな。でもこのブログを読んで、こんなことをじっくり考えることが楽しいと思えた人が一人でも増えれば本望だ。

で、最後に宣伝。よろしく。