数学A 場合の数 問題 27 解説

方針・初手

最短経路では遠回りできないので、右方向と上方向にだけ進む。したがって、必要な右移動と上移動の並べ方を数えればよい。

図より、1区画を1として

$$ A=(0,0),\quad P=(1,2),\quad Q=(3,3),\quad B=(4,5) $$

とおく。

解法1

まず、$A$ から $B$ までは右へ $4$ 回、上へ $5$ 回進む必要がある。合計 $9$ 回の移動のうち、右へ進む $4$ 回の位置を選べばよいので、すべての最短経路の数は

$$ {}_{9}\mathrm{C}_{4}=126 $$

である。

次に、点 $P$ を通る道順を数える。

$A$ から $P$ までは右へ $1$ 回、上へ $2$ 回なので

$$ {}_{3}\mathrm{C}_{1}=3 $$

通りである。

また、$P$ から $B$ までは右へ $3$ 回、上へ $3$ 回なので

$$ {}_{6}\mathrm{C}_{3}=20 $$

通りである。

よって、点 $P$ を通る道順は

$$ 3\cdot 20=60 $$

通りである。

次に、点 $P$ と点 $Q$ の両方を通る道順を数える。最短経路で両方を通る場合は、必ず

$$ A\to P\to Q\to B $$

の順に通る。

すでに $A$ から $P$ までは $3$ 通りである。

$P$ から $Q$ までは右へ $2$ 回、上へ $1$ 回なので

$$ {}_{3}\mathrm{C}_{1}=3 $$

通りである。

$Q$ から $B$ までは右へ $1$ 回、上へ $2$ 回なので

$$ {}_{3}\mathrm{C}_{1}=3 $$

通りである。

したがって、点 $P$ と点 $Q$ の両方を通る道順は

$$ 3\cdot 3\cdot 3=27 $$

通りである。

点 $P$ を通って点 $Q$ を通らない道順は、点 $P$ を通る道順から、点 $P$ と点 $Q$ の両方を通る道順を引けばよい。よって

$$ 60-27=33 $$

通りである。

最後に、点 $P$ も点 $Q$ も通らない道順を数える。

点 $Q$ を通る道順を数える。$A$ から $Q$ までは右へ $3$ 回、上へ $3$ 回なので

$$ {}_{6}\mathrm{C}_{3}=20 $$

通りである。

$Q$ から $B$ までは右へ $1$ 回、上へ $2$ 回なので

$$ {}_{3}\mathrm{C}_{1}=3 $$

通りである。

したがって、点 $Q$ を通る道順は

$$ 20\cdot 3=60 $$

通りである。

ここで、点 $P$ を通る道順と点 $Q$ を通る道順を単純に引くと、両方を通る道順を二重に引いてしまう。そのため、包除原理より

$$ 126-60-60+27=33 $$

である。

よって、点 $P$ も点 $Q$ も通らない道順は $33$ 通りである。

解説

この問題は、最短経路を「右」と「上」の並べ方として数えるのが基本である。

特定の点を通る場合は、その点で経路を分割して、それぞれの区間の最短経路数を掛ける。複数の条件を含む場合は、重複して数えたり引いたりしないように包除原理を使う。

特に「$P$ も $Q$ も通らない」は、直接数えるよりも、全体から $P$ を通るものと $Q$ を通るものを除く方が自然である。ただし、両方を通る道順は二重に除かれるため、最後に足し戻す必要がある。

答え

$$ \boxed{[カ]=126} $$

$$ \boxed{[キ]=60} $$

$$ \boxed{[ク]=27} $$

$$ \boxed{[ケ]=33} $$

$$ \boxed{[コ]=33} $$