2020年 北海道大学理系数学 第3問の解説をしてみます。
エレガントな解法の類はやりません。あくまで、試験場で自分が解くとしたらどう考えるかな〜という観点で見ていますのでよろしくです
$n$ を $2$ 以上の自然数とする。 $1$ 個のさいころを続けて $n$ 回投げる施行を行い、出た目を順に $X_1, X_2, …, X_n$ とする。
(1) $X_1, X_2, …, X_n$ の最大公約数が $3$ となる確率を $n$ の式で表せ。
(2) $X_1, X_2, …, X_n$ の最大公約数が $1$ となる確率を $n$ の式で表せ。
(3) $X_1, X_2, …, X_n$ の最小公倍数が $20$ となる確率を $n$ の式で表せ。
2020 北海道大学理系
解いてみた感想
標準的な確率の問題ですが、場合分けを丁寧にやらないとミスをしてしまいそうな出題です。混乱しないように丁寧に計算するよう意識する必要がありそうです。
以下、事象 $A$ が起こる確率を $\mathrm{P}(A)$ と表記します。
(1) 最大公約数の意味を考える
「 $n$ 個の数の最大公約数が $3$ となるのはどういう場合か」を考えてみます。最大公約数というのは共通の約数でありますから、そもそも $n$ 個の数 $X_1, X_2, …, X_n$ はすべて $3$ の倍数であることが必要です。
この時点で $X_1, X_2, …, X_n$ はすべて $3, 6$ のいずれかであることが確定しました。ではこれで十分でしょうか。
よく考えてみると、 $X_1 = X_2 = … = X_n = 6$ のときは最大公約数が $6$ になってしまい、題意を満たしません。逆に、 $X_1, X_2, …, X_n$ の中に一つでも $3$ があれば題意を満たすことも確認できます。
ということは結局、
& \mathrm{P}(\mathrm{GCD} = 3) \\
& = \mathrm{P}(X_1, X_2, …, X_n \in \{3, 6\}) – \mathrm{P}(X_1 = X_2 = … = X_n = 6) \\
& = \left( \frac{2}{6} \right) ^n – \left( \frac{1}{6} \right) ^n \\
& = \frac{2^n – 1}{6^n}
\end{align*}
となります。（ただし、 $\mathrm{GCD}$ は $X_1, X_2, …, X_n$ の最大公約数 $\mathrm{GCD}(X_1, X_2, …, X_n)$ を略記したものとします）
(2) 余事象の活用
最大公約数が 1 というケースはいくつも考えられ、規則性がすぐに見つからなさそうなので、(1) を活用して余事象の活用で考えてみます。
つまり、 $\mathrm{GCD}(X_1, X_2, …, X_n) \in \{1, 2, 3, 4, 5, 6\}$ ですから、
& \mathrm{P}(\mathrm{GCD} = 1) \\
& = 1 – \left( \mathrm{P}(\mathrm{GCD} = 2) + \mathrm{P}(\mathrm{GCD} = 3) + \mathrm{P}(\mathrm{GCD} = 4) + \mathrm{P}(\mathrm{GCD} = 5) + \mathrm{P}(\mathrm{GCD} = 6) \right)
\end{align*}
よって、以下、最大公約数が $2, 3, 4, 5, 6$ となるケースをそれぞれ考えていきます。簡単なものから。
最大公約数が 6 になるケース
& \mathrm{P}(\mathrm{GCD} = 6) \\
& = \mathrm{P}(X_1 = X_2 = … = X_n = 6) \\
& = \left( \frac{1}{6} \right) ^n
\end{align*}
最大公約数が 5 になるケース
& \mathrm{P}(\mathrm{GCD} = 5) \\
& = \mathrm{P}(X_1 = X_2 = … = X_n = 5) \\
& = \left( \frac{1}{6} \right) ^n
\end{align*}
最大公約数が 4 になるケース
& \mathrm{P}(\mathrm{GCD} = 4) \\
& = \mathrm{P}(X_1 = X_2 = … = X_n = 4) \\
& = \left( \frac{1}{6} \right) ^n
\end{align*}
最大公約数が 3 になるケース
(1) より、
\mathrm{P}(\mathrm{GCD} = 3) = \frac{2^n – 1}{6^n}
\end{align*}
最大公約数が 2 になるケース
(1) と同様に考えてみますと、最大公約数が $2$ となるのは、$X_1, X_2, …, X_n \in \{2, 4, 6\}$ で、 $X_1, X_2, …, X_n$ の中に一つでも $2$ があることだとわかります。よって、
& \mathrm{P}(\mathrm{GCD} = 2) \\
& = \mathrm{P}(X_1, X_2, …, X_n \in \{2, 4, 6\}) – \mathrm{P}(X_1 = X_2 = … = X_n = 4) – \mathrm{P}(X_1 = X_2 = … = X_n = 6)\\
& = \left( \frac{3}{6} \right) ^n – \left( \frac{1}{6} \right) ^n – \left( \frac{1}{6} \right) ^n \\
& = \frac{3^n – 2}{6^n}
\end{align*}
これですべて出揃いました。
では答えを計算します。
& \mathrm{P}(\mathrm{GCD} = 1) \\
& = 1 – \left( \mathrm{P}(\mathrm{GCD} = 2) + \mathrm{P}(\mathrm{GCD} = 3) + \mathrm{P}(\mathrm{GCD} = 4) + \mathrm{P}(\mathrm{GCD} = 5) + \mathrm{P}(\mathrm{GCD} = 6) \right) \\
& = 1 – \left( \frac{3^n – 2}{6^n} \right) – \left( \frac{2^n – 1}{6^n} \right) – \left( \frac{1}{6^n} \right) – \left( \frac{1}{6^n} \right) – \left( \frac{1}{6^n} \right) \\
& = 1 – \frac{1}{2^n} – \frac{1}{3^n}
\end{align*}
(3) 丁寧に場合分け
(3) も同様に丁寧に場合分けして考えてゆけば解けますが、少し複雑になるので注意が必要です。
まず、最小公倍数が $20 = 2^2 \cdot 5$ ということは、$X_1, X_2, …, X_n$ はすべて $1, 2, 4, 5$ のいずれかである必要があります。
このうち、最小公倍数が実際に $20$ にならないケースを考えてみると、 $4$ が一度も出ない場合、もしくは $5$ が一度も出ない場合であり、この場合を除けば良さそうです。
そこで、まずは $4$ が一度も出ないもしくは $5$ が一度も出ない確率を計算しておきます。（1, 2, 4, 5 のいずれかしか出ない前提で求めます）これを $p_1$ とすれば
p_1 & = \mathrm{P}(X_1, X_2, …, X_n \in \{1, 2, 5\}) + \mathrm{P}(X_1, X_2, …, X_n \in \{1, 2, 4\}) – \mathrm{P}(X_1, X_2, …, X_n \in \{1, 2\}) \\
& = \left( \frac{3}{6} \right) ^n + \left( \frac{3}{6} \right) ^n – \left( \frac{2}{6} \right) ^n \\
& = \frac{2 \cdot 3^n – 2^n}{6^n}
\end{align*}
となります。以上より求める確率は
& \mathrm{P}(X_1, X_2, …, X_n \in \{1, 2, 4, 5\}) – p_1 \\
& = \frac{4^n – 2 \cdot 3^n + 2^n}{6^n}
\end{align*}
となります。
blog.satoooh.com
