最短経路の総数(空間)

スポンサーリンク
左下図のように,\ 立方体ABCD-EFGHの表面と内部に等間隔の道を作る. \\[.2zh] \hspace{.5zw}\phantom{(1)}\ \ このとき,\ 頂点Aから頂点Gまでの最短経路は何通りあるか. \\[1zh] \hspace{.5zw}(2)\ \ 右下図のように,\ 立方体ABCD-EFGHの表面に等間隔の道を作る. \\[.2zh] \hspace{.5zw}\phantom{(1)}\ \ このとき,\ 頂点Aから頂点Gまでの最短経路は何通りあるか. \\\\[1zh] 最短経路の総数(空間)}}}} \\\\[.5zh]  (1)\ \ \textcolor{red}{→\ 2個,\ ↑2個,\ \rotatebox[origin=c]{45}{→}2個の並べ方の総数に等しい}から  (2)\ \ \textcolor{red}{立方体内部の点Iを通る経路}は\ \ $\textcolor{red}{3\kaizyou\times3\kaizyou}=36\ (通り)$   $\therefore\ \ 90-36=\bm{54\ (通り)}$ \\\\\\  \betu\ \ 頂点Aから頂点Gまでの最短経路には以下の6つの場合がある. \\[1zh] \phantom{ (1)}\ \ [1]\ \ 面ABFEと面BCGF上の道のみを通る. \\[.3zh] \phantom{ (1)}\ \ [2]\ \ 面ABFEと面EFGH上の道のみを通る. \\[.3zh] \phantom{ (1)}\ \ [3]\ \ 面ADHEと面DCGH上の道のみを通る. \\[.3zh] \phantom{ (1)}\ \ [4]\ \ 面ADHEと面EFGH上の道のみを通る. \\[.3zh] \phantom{ (1)}\ \ [5]\ \ 面ABCDと面BCGF上の道のみを通る. \\[.3zh] \phantom{ (1)}\ \ [6]\ \ 面ABCDと面DCGH上の道のみを通る. \\\\ ここで,\ [1]と[2]には,\ 頂点Fを通る経路$\textcolor{red}{\bunsuu{4\kaizyou}{2\kaizyou2\kaizyou}\times1=6}$通り分の重複がある. (1)\ \ 平面における最短経路と同様の発想で,\ \bm{同じものを含む順列に帰着}する. \\[1zh] (2)\ \ 本解は,\ 総数から\bm{立方体内部の交点を通る経路(\textbf{A\ →\ I\ →\ G})の数を引く}ものである. \\[.2zh] \phantom{(1)}\ \ \text{A\ →\ I,\ I\ →\ G}はいずれも,\ \text{→\ 1個,\ ↑1個,\ \rotatebox[origin=c]{45}{→}1個}の並べ方の総数に等しい. \\[1zh] \phantom{(1)}\ \ 本解は簡潔に済んでいるが,\ その\bm{汎用性は非常に低い.} \\[.2zh] \phantom{(1)}\ \ 仮に立体内部に2つの交点\text{I,\ J}があったとしよう. \\[.2zh] \phantom{(1)}\ \ (\text Iまたは\text Jを通る)=(\text Iを通る)+(\text Jを通る)-(\text Iも\text Jも通る)を総数から引くことになる. \\[.2zh] \phantom{(1)}\ \ \text Iを通ると\text Jを通るは排反ではないため,\ 重複分を考慮しなければならないのである. \\[.2zh] \phantom{(1)}\ \ このように,\ 総数から引く方法は,\ 立体内部の点が多い場合には現実的ではなくなる. \\[1zh] \phantom{(1)}\ \ そこで必要になるのが,\ 直接的に求める方法である(別解).\ 経験なしで正解するのは難しい. \\[.2zh] \phantom{(1)}\ \ まず,\ \bm{最短で行くならば必ず2つの面上の道を通る}ことになる. \\[.2zh] \phantom{(1)}\ \ 出発点\text Aを含む面は,\ \text{ABFE,\ ADHE,\ ABCD}の3面である. \\[.2zh] \phantom{(1)}\ \ 到着点\text Gを含む面は,\ \text{BCGF,\ EFGH,\ DCGH}の3面である. \\[.2zh] \phantom{(1)}\ \ それゆえ,\ どの2面を通るかで,\ [1]\,~\,[6]\,の6パターンに場合分けできる. \\[1zh] \phantom{(1)}\ \ [1]\,~\,[6]\,の各場合の最短経路は,\ \bm{展開図を考える}と平面における最短経路に帰着する. \\[.2zh] \phantom{(1)}\ \ 厄介なのは,\ [1]\,~\,[6]\,が\bm{互いに排反ではない}ことである. \\[1zh] \phantom{(1)}\ \ [1]\,と\,[2]\,は,\ 面\text{ABFE}が同じで,\ かつ残りの面\text{BCGFとEFGHは1辺FG}を共有する. \\[.2zh] \phantom{(1)}\ \ よって,\ 同じ経路\ \text{A\ →\ F\ →\ G}_1\ と\ \text{A\ →\ F\ →\ G}_2\ を重複して数えていることになる(上左図). \\[.2zh] \phantom{(1)}\ \ このように,\ \bm{1つの面が同じで,\ かつ残りの面が1辺を共有するとき,\ 重複が生じる.} \\[1zh] \phantom{(1)}\ \ 同様に,\,[1]\,と\,[5]\,は,\,面\text{BCGF}が同じで,\,かつ残りの面\text{ABFEとABCDは1辺AB}を共有する. \\[.2zh] \phantom{(1)}\ \ よって,\ 同じ経路\ \text{A}_1\ →\ \text{B\ →\ G}\ と\ \text{A}_2\ →\ \text{B\ →\ G}\ を重複して数えていることになる(上右図).
タイトルとURLをコピーしました