平成30年度青森県教員採用試験別解について

平成30年度青森県教員採用試験解答解説

3.図1のように,東西方向,南北方向にそれぞれ６本ずつ等間隔に並んだ道路をもつ町Xがある。次の(1)〜(3)に答えなさい。

(1)次の①,②の場合について,町\(X\)の地点\(A\)から地点\(B\)まで最短経路で行く方法は何通りあるか求めなさい。
sample
\(①\)地点\(C\)を通っていく場合

解.
まず\(A→C\)の行き方は
(右に\(２\)マス,上に\(１\)マス,合計\(３\)マス)
\begin{align*} 　　　\frac{3!}{2!1!}&=\frac{3×2×1}{(2×1)×1}\\ &=3(通り)\\ \end{align*}
次に\(C→B\)の行き方は
(右に\(３\)マス,上に\(４\)マス,合計\(７\)マス) \begin{align*} 　　　\frac{7!}{3!4!}&=\frac{7×6×5×4×3×2×1}{(3×2×1)×(4×3×2×1)}\\ &=35(通り)\\ \end{align*}
よって\(A→C→B\)の行き方は
\begin{align*} 　　　3×35&=105(通り)\\ \end{align*}

\(②\)地点\(C\)または地点\(D\)の少なくても一方を通っていく場合。
解. \begin{align*} A→C→Bは①より105(通り)・・・(Ⅰ)\\ 同様にA→D→Bを求める。\\ A→D→Bの行き方は\\ \end{align*}
\begin{align*} (右に3マス、上に3マス、合計6マス)\\ 　　×　　　　　　　\\ (右に2マス、上に2マス、合計4マス)\\ \end{align*}
\begin{align*} \small{\frac{6!}{3!3!}×\frac{4!}{2!2!}}&=\small{\frac{6×5×4×3×2×1}{(3×2×1)×(3×2×1)}×\frac{4×3×2×1}{(2×1)×(2×1)}}\\ &=20×6=120(通り)・・・(Ⅱ)\\ \end{align*}
\(※少なくとも一方を通っていく場合なのでCとD\)
\(両方とも通る場合を引かなければならない。\)
\( A→C→D→Bの行き方は\)
\begin{align*} (右に２マス、上に１マス、合計３マス)\\ ×　　　　　　　\\ (右に１マス、上に２マス、合計３マス)\\ ×　　　　　　　\\ (右に２マス、上に２マス、合計４マス)\\ \end{align*}
\begin{align*} \small{\frac{3!}{2!1!}×\frac{3!}{1!2!}×\frac{4!}{2!2!}}&=\small{\frac{3×2×1}{(2×1)×1}×\frac{3×2×1}{1×(2×1)}×\frac{4×3×2×1}{(2×1)×(2×1)}}\\ &=3×3×6=54(通り)・・・(Ⅲ)\\ \end{align*} よって最終的な答えは(Ⅰ)+(Ⅱ)-(Ⅲ)になるので
\begin{align*} 　　　105+120-54=171\\ 　　　　　\underline{\large∴171(通り)}\\ \end{align*}
(2)図\(2\)のように,町\(X\)の斜線で示された部分を通ることができないとき,地点\(A\)から地点\(B\)まで 最短経路で行く方法は何通りあるか求めなさい。（説明に図\(2\)を用いてもよい。）
sample

解. \begin{align*} \small{斜線部分を通らないAからBまで最短経路は,　　　　　　　}\\ \small{図2で示した4地点E,F,G,Hのうちいずれか1つは必ず通る。}\\ \end{align*}
sample
※\(G\)を通った後,必ず\(G'\)を通る。

(1)同様に求めていく。\(A→E→B\)の行き方は
\begin{align*} 　　　1×\frac{6!}{5!1!}&=1×\frac{6×5×4×3×2×1}{(5×4×3×2×1)×1}\\ &=6(通り)・・・(Ⅰ)\\ \end{align*} \(A→F→B\)の行き方は
\begin{align*} 　　　\frac{4!}{1!3!}×\frac{6!}{4!2!}&=\frac{4×3×2×1}{(1×(3×2×1)}×\frac{6×5×4×3×2×1}{(4×3×2×1)×(2×1)}\\ &=4×5=60(通り)・・・(Ⅱ)\\ \end{align*} \(A→G→G'→B\)の行き方は
\begin{align*} 　　　\frac{4!}{3!1!}×1×\frac{5!}{1!4!}&=\frac{4×3×2×1}{((3×2×1)×1}×1×\frac{5×4×3×2×1}{1×(4×3×2×1)}\\ &=4×5=20(通り)・・・(Ⅲ)\\ \end{align*} \(A→H→B\)の行き方は
\begin{align*} 　　　1×\frac{6!}{1!5!}&=1×\frac{6×5×4×3×2×1}{1×(5×4×3×2×1)}\\ &=6(通り)・・・(Ⅳ)\\ \end{align*} よって最終的な答えは(Ⅰ)+(Ⅱ)+(Ⅲ)+(Ⅳ)になるので
\begin{align*} 　　　6+60+20+6=92\\ 　　　　　\underline{\large∴92(通り)}\\ \end{align*}

(3)図３のように,町Xにおいて地点Pと地点Qを結ぶ直線ℓ上にある地点を通ることなく, 太線で示された道路のみを通って地点Aから地点Bまで最短経路で行く 方法が何通りあるか求めたい。次の□で囲まれた内容を踏まえ, 下の①,②に答えなさい。

　図４のように,図３を直線ℓについて対称移動し, 地点Aと直線ℓについて対称な地点をA'とすると, 図３において地点Aから地点Bまで行くすべての最短経路のうち, 直線ℓ上にある地点を少なくても１回通る経路の数は, 図４において地点A'から地点Bまで行く最短経路の数と一致する。
sample sample

①上の□で囲まれた内容が正しい理由を説明しなさい。 （説明に図４を用いてもよい。）

解.
sample
\begin{align*} \small{ \bf{ ℓ上の地点をRとする。地点A→Rの経路をℓについて\\ 対称移動すると地点A'→Rの最短経路と一致する。\\ } } \end{align*} \begin{align*} \small{ \bf{ つまり地点AからRを通って地点Bに行く最短経路の1つは,\\ 地点A'からRを通って地点Bに行く最短経路の1つと対応する。\\ } } \end{align*} \begin{align*} \small{ \bf{ これはRがℓ上にあるどの地点にあっても成り立つので、\\ 地点A→R→Bの最短経路の数は,\\ 地点A'→R→Bの最短経路の数と一致する。\\ 地点A'→Bの最短経路は,ℓ上にある地点を必ず通る。\\ } } \end{align*} \begin{align*} \small{ \bf{ よって図3において地点Aから地点Bまで行く最短経路のうち,\\ ℓ上にある地点を少なくとも1回通る経路の数は図4において\\ 地点A'から地点Bまで行く最短経路の数と一致するといえる。\\ } } \end{align*}

②図\(3\)において,直線ℓ上にある地点を通ることなく, 太線で示された道路のみを通って地点\(A\)から地点\(B\)まで 最短経路で行く方法は何通りあるか求めなさい。

sample
解.
（太線で示された道路のみを通って地点Aから地点Bまで最短経路の数）= （すべての最短経路の数）-（\(ℓ\)上にある地点を少なくても\(1\)回通る最短経路の数）
すべての最短経路の数は
\begin{align*} \frac{10!}{5!5!}&=\frac{10×9×8×7×6×5×4×3×2×1}{(5×4×3×2×1)×(5×4×3×2×1)}\\ &=252(通り)\\ \end{align*} ある地点を少なくとも１回通る最短経路の数は①から図４において 地点A'から地点Bまで行く最短経路の数と一致するので
\begin{align*} \frac{10!}{3!7!}&=\frac{10×9×8×7×6×5×4×3×2×1}{(3×2×1)×(7×6×5×4×3×2×1)}\\ &=120(通り)\\ \end{align*} \begin{align*} よって求める最短経路の数は\\ 　252-120=132\\ 　　　　　\underline{\large∴132(通り)}\\ \end{align*}