【確率】ジャングルジム（三次元格子）の道順

【PS09】ジャングルジムの道順

下の図のような $3$ 次元格子（ジャングルジム）において、原点 $O$ から点 $X(1,\;1,\;1)$ を通らずに点 $A(2,\;2,\;2)$ へ最短距離で行く道順は何通りありますか。



【ヒント】道順の典型問題です。点 $X$ が通行止めになっています。余事象を考えると簡単です。

中学入試 算数図形問題完全マスター 中古価格 ￥928から (2021/9/6 16:57時点)

【解答】まず原点 $O$ から点 $A$ まで行く道順の総数を求めます。上 ($z$ 方向) への移動を $a$ , 右 ($x$ 方向) への移動を $b$ , 奥 ($y$ 方向) への移動を $c$ で表すと、$A$ までの道順の個数は
\[a\,a\,b\,b\,c\,c\]
を並び替える方法の数に等しくなります。その数は全部で
\[\frac{6!}{2!2!2!}=90\;通り\]
となります。また、$O$ から $X$ まで行く道順は $a\,b\,c$ の並び替え方に等しいので $3!=6$ 通り、$X$ から $A$ まで行く道順も同様に $6$ 通りです。すなわち「$O$ から $X$ を通って $A$ へ行く方法」は
\[6\times 6=36\;通り\]
あります。「$X$ を通らずに $A$ へ行く方法」は、「$O$ から $A$ まで行く道順の総数」から「$O$ から $X$ を経由して $A$ へ行く方法の数」を引けばよいので、答えは
\[90-36=54\;通り\]
となります。

【PS10】不定方程式の整数解と自然数解の個数

次の不定方程式の整数解の個数はそれぞれいくつありますか。
\[\begin{align*}&(1)\,x+y+z=7\quad (x\geq 0,\;y\geq 0,\;z\geq 0)\\[6pt]
&(2)\,x+y+z=7\quad (x\geq 1,\;y\geq 1,\;z\geq 1)\end{align*}\]
【ヒント】重複組合せ の定番の問題です。(2) は変数変換で簡単に解くことができます。

1冊でマスター 大学の統計学 新品価格 ￥2,728から (2022/7/15 14:37時点)

【解答】(1) 方程式の解を $7$ 個の ○ と $2$ 個の | を使って、たとえば

○○|○○○|○○

のように表します。左端にある ○ の数が $x$ , 真ん中が $y$ , 右端が $z$ です。上の例では $x=2,\;y=3,\;z=2$ に対応しています。

|○○○○|○○○

であれば、$x=0,\;y=4,\;z=3$ です。いずれにしても、$9$ 個の中から同じものを $7$ 個と $3$ 個含む順列なので、解の個数は
\[\frac{9!}{7!\,2!}=36\:個\]
となります。

(2) $X=x-1$ と変数変換すると $X\geq 0$ となります。同様に $Y=y-1,\;Z=z-1$ とおくと、与えられた方程式は
\[X+Y+Z=4\]
となります。$(X,\;Y,\;Z)$ は $(x,\;y,\;z)$ と $1$ 対 $1$ に対応しているので、その組合せの個数も一致します。(1) と同じように ○ と | で

○|○|○○

のように表せば、| で区切られた部分がそれぞれ $X,\;Y,\;Z$ に対応するので、解の個数は
\[\frac{6!}{4!\,2!}=15\:個\]
となります。

【別解】$n$ 種類のものから $r$ 個選ぶときの重複組合せの公式
\[{}_n\mathrm{H}_r=\:{}_{n+r-1}\mathrm{C}_r\]
を使って解くこともできます。

(1) $(x,\;y,\;z)$ の $3$ 種類から重複を許して $7$ 個を選ぶと考えて、
\[{}_3\mathrm{H}_7=\:{}_{9}\mathrm{C}_7=36\:個\]
となります。

(2) $X=x-1,\;Y=y-1,\;Z=z-1$ とおくと
\[X+Y+Z=4\]
$(X,\;Y,\;Z)$ の $3$ 種類から重複を許して $4$ 個を選ぶと考えて、
\[{}_3\mathrm{H}_4=\:{}_{6}\mathrm{C}_4=15\:個\]
となります。

【PS11】合計金額が 100 円になるように切手を買います

$5$ 円、$10$ 円、$20$ 円の $3$ 種類の切手を合わせて $100$ 円買うには、何通りの買い方がありますか。ただし切手は必ず $3$ 種類とも含むものとします。（日本大）

【ヒント】不定方程式の整数解の個数を求める問題ですが、合計金額を考えると、$5$ 円切手の枚数には制約があります。

テンソル解析 (基礎数学選書 23) 中古価格 ￥1,898から (2019/8/8 06:54時点)

【解答】$5$ 円切手の枚数を $x$ , $10$ 円切手の枚数を $y$ , $20$ 円切手の枚数を $z$ とすると、$5x+10y+20z=100$ より
\[x+2y+4z=20\]
という方程式が立てられます。ただし合計金額が $100$ 円なので、$x$ は偶数であるはずです。そこで $x=2x’$ とおくと、
\[x’+y+2z=10\]
となります。どの切手も少なくとも $1$ 枚は買うので、$z\lt 5$ です。すなわち、$z$ のとりうる値は $z=1,\;2,\;3,\;4$ のいずれかです。$z=1$ のときは
\[x’+y=8\]
$x’$ と $y$ はともに $1\sim 7$ の数字をとれるので、この方程式を満たす $(x’,\:y)$ の組合せは $7$ 通り存在します。同様に考えて

 $z=2$ のとき、$x’+y=6$ を満たす解は $5$ 通り
 $z=3$ のとき、$x’+y=4$ を満たす解は $3$ 通り
 $z=4$ のとき、$x’+y=2$ を満たす解は $1$ 通り

となるので、答えは合わせて $16$ 通りとなります。