場合の数・確率系 実践演習

蛇経路【経路問題の難問】【1994年度 千葉大学ほか】

例題はこちら(画像をクリックするとPDFファイルで開きます。)

定番の経路問題をベースとして、プラスアルファの思考要素が入った問題です。

(1) は落としたくないレベルですが、(2) は難問です。

東大に現役で合格するような受験生でも、このタイプは初見だと四苦八苦します。

逆に、割合は少ないですが、あっさりと解決してしまう人もいるので見える人には見えるのでしょう。

なお、(2) のモデルケースを考えてみると、蛇みたいな経路に見えるので、蛇経路と呼んでいます。

(私が勝手に呼んでいるだけで市民権はありません。)

(以下ネタバレ注意)

 

+ クリック(タップ)して続きを読む

(1) について

\(A_{1}\) → \(B_{k}\) → \(C\) という行き方が \(x_{k}\) 通りとして

\(\displaystyle \sum_{k=1}^n x_{k}\)

を求めればよいでしょう。

\(x_{k}\) については、→ \(k-1\) 個と、↓ 2 個の並べ方を考えて、\({}_{k+1} \mathrm{ C }_2=\displaystyle \frac{k(k+1)}{2}\) 通りあります。

あとはシグマ計算です。

(2) について

真上にも動けるという設定が厄介です。

例えば \(A_{1}\) から \(B_{5}\) まで行く経路の総数を考えてみます。

閃き一発に近いのですが、

の ○ を選択すると

という経路に対応します。

こうしてみると、隣りの列に移る際に

上段、中段、下段

の \(3\) 通りの選択肢があるわけです。

したがって、\(A_{1}\) から \(B_{5}\) への経路の総数は \(3^{4}=81\) 通りということになります。

これは \(A_{1}\) から \(B_{k}\) までの行き方を考える際でも通用する態度です。

類題

類題はこちら(画像をクリックするとPDFファイルで開きます。)

(1) は例題の経験値で倒せます。

(2) ,  (3)  は「その場力」が必要な難問です。

あ~でもないこ~でもないと頭を鍛える良い機会となる問題です。

最短経路の思考系問題

併せて解きたい

最短経路と直進距離に関する考察【隣り合わないように並べる方法】【2012年度 高知大学】

問題はこちら(画像をクリックするとPDFファイルで開きます。)   (1),(2)までは典型的な教科書レベルの問題です。 頭を使うのは(3),(4)からで、5m以上の直進があるような最短距離 ...

続きを見る

経験値が必要な最短経路の難問

こちらもCHECK

カタラン数【最短経路の応用問題】【2008年度 九州大学】

問題はこちら(画像をクリックするとPDFファイルで開きます。) (1) ,  (2) について 最短経路の問題として (1) ,  (2)  についてはきっちりと確保したいレベルの基本問題です。 (3 ...

続きを見る

例題の解答はコチラ

類題の解答はコチラ

-場合の数・確率系, 実践演習
-

© 2022 MathClinic