10-01最短経路を問う組み合わせ(難易度2)

図のような碁盤の目の通路があるとき、点$A$から点$B$へ最短距離で移動をします。

(1)すべての道順は何種類あるでしょうか。
(2)点$C$を通る道順は何種類あるでしょうか。
(3)点$D$を通らない道順は何種類あるでしょうか。

(1)(2)移動することを→↓で表してみよう
(3)点$D$を通らないとは、「通る」ではないです。

(1)移動を→↓と表すと
 $A$から$B$への移動は、→$5$個、↓$5$個の順列で表すことできるため、
  $\cfrac{10!}{5!5!}=\cfrac{10\cdot9\cdot8\cdot7\cdot6}{5\cdot4\cdot3\cdot2\cdot1}$
  $=252$通りとなる。
(2)点$A$から点$C$までは→$3$個↓$2$個の順列、点Cから点Bまでは、→2個↓3個の順列になるため
  $\cfrac{5!}{3!2!}\cdot\cfrac{5!}{3!2!}=\cfrac{5\cdot4}{2\cdot1}\cdot\cfrac{5\cdot4}{2\cdot1}$
   $=100通り$
(3)$D$を通る道順は、点$A$から点$D$の上の交差点に移動し、点$D$の下の交差点から点$B$に移動するときである。
  つまり、→$4$個↓$2$個の順列と→$1$個↓$2$個の順列になるため
  $\cfrac{6!}{4!2!}\cdot\cfrac{3!}{2!1!}=\cfrac{6\cdot5}{2\cdot1}\cdot3$
   $=45$通り・・・①
  すなわち、$D$を通らない道順は(1)の解と①より
  $252-45=207$通り

(1)碁盤の目の問題は、組み合わせを問う問題での定番で、
 移動を→↓と表すことで「→→↓↓→↓→↓」、「→↓↓↓→→→↓」と表せ
 組み合わせの場合の数とわかります。
(2)経過地点が指定される場合は、出発点から経過地点、経由地点から終点と2つに分けて考えます。
 そうすることで個々に考えることができ、積の法則で求めることができます。
(3)通らない道順を考えるのは難しいので、通る道順の余事象と考えます。
 点$D$を通るためには、数の点$E$と点$F$を経由すると考えましょう。
 
 

シェアする

  • このエントリーをはてなブックマークに追加

フォローする