トップ› 北海道大学› 2020年› 理系第3問

北海道大学 2020年理系第3問解説

方針・初手

最大公約数や最小公倍数に関する確率は、出た目がどのような集合に属するかという事象に言い換えて考える。最大公約数が特定の数 $d$ になる事象は、「すべての目が $d$ の倍数である」事象から、最大公約数が $d$ の倍数（$2d$ など）になってしまう事象を排除することで求める。最小公倍数が特定の数 $m$ になる事象は、「すべての目が $m$ の約数である」事象の中で、必要な素因数（目）が不足する事象を排除して求める。いずれも包除原理や余事象の考え方が有効である。

解法1

(1)

$X_1, X_2, \cdots, X_n$ の最大公約数が $3$ となるのは、すべての目が $3$ の倍数（すなわち $3$ または $6$）であり、かつ、すべての目が $6$ ではないときである。

さいころを $n$ 回投げて、すべての目が $3$ の倍数となる確率は、

$$ \left( \frac{2}{6} \right)^n = \left( \frac{1}{3} \right)^n $$

である。このうち、すべての目が $6$ となる場合は最大公約数が $6$ となるため、これを除外する。すべての目が $6$ となる確率は、

$$ \left( \frac{1}{6} \right)^n $$

である。

したがって、求める確率は、

$$ \left( \frac{1}{3} \right)^n - \left( \frac{1}{6} \right)^n $$

(2)

$X_1, X_2, \cdots, X_n$ の最大公約数が $1$ となる確率を直接求めるのは複雑なため、余事象「最大公約数が $2$ 以上となる確率」を考える。さいころの目は $1$ から $6$ までなので、最大公約数が素数 $p$ の倍数になるとき、$p$ は $2, 3, 5$ のいずれかである。

すべての目が $2$ の倍数となる事象を $A$、すべての目が $3$ の倍数となる事象を $B$、すべての目が $5$ の倍数となる事象を $C$ とおく。

最大公約数が $2$ 以上となるのは事象 $A \cup B \cup C$ が起こるときであるから、包除原理よりその確率は、

$$ P(A \cup B \cup C) = P(A) + P(B) + P(C) - P(A \cap B) - P(B \cap C) - P(C \cap A) + P(A \cap B \cap C) $$

となる。各事象の確率は以下の通りである。

$P(A)$: 目の候補は $\{2, 4, 6\}$ の $3$ 通りより、 $P(A) = \left( \frac{3}{6} \right)^n = \left( \frac{1}{2} \right)^n$
$P(B)$: 目の候補は $\{3, 6\}$ の $2$ 通りより、 $P(B) = \left( \frac{2}{6} \right)^n = \left( \frac{1}{3} \right)^n$
$P(C)$: 目の候補は $\{5\}$ の $1$ 通りより、 $P(C) = \left( \frac{1}{6} \right)^n$
$P(A \cap B)$: すべての目が $2$ の倍数かつ $3$ の倍数（すなわち $6$ の倍数）。目の候補は $\{6\}$ の $1$ 通りより、 $P(A \cap B) = \left( \frac{1}{6} \right)^n$
$P(B \cap C)$: すべての目が $15$ の倍数となるが、該当する目はないため $0$
$P(C \cap A)$: すべての目が $10$ の倍数となるが、該当する目はないため $0$
$P(A \cap B \cap C)$: 該当する目はないため $0$

これらを代入すると、

$$ \begin{aligned} P(A \cup B \cup C) &= \left( \frac{1}{2} \right)^n + \left( \frac{1}{3} \right)^n + \left( \frac{1}{6} \right)^n - \left( \frac{1}{6} \right)^n - 0 - 0 + 0 \\ &= \left( \frac{1}{2} \right)^n + \left( \frac{1}{3} \right)^n \end{aligned} $$

求める確率は余事象の確率であるから、

$$ 1 - \left\{ \left( \frac{1}{2} \right)^n + \left( \frac{1}{3} \right)^n \right\} = 1 - \left( \frac{1}{2} \right)^n - \left( \frac{1}{3} \right)^n $$

(3)

$X_1, X_2, \cdots, X_n$ の最小公倍数が $20$ になるためには、出た目がすべて $20$ の約数でなければならない。さいころの目のうち、$20$ の約数であるものは $1, 2, 4, 5$ である。（$3, 6$ が一度でも出れば最小公倍数は $20$ にならない。）したがって、すべての目は $\{1, 2, 4, 5\}$ の中から出なければならない。この事象を $U$ とすると、

$$ P(U) = \left( \frac{4}{6} \right)^n = \left( \frac{2}{3} \right)^n $$

さらに、最小公倍数が $20 = 2^2 \times 5^1$ となるためには、

素因数 $2$ が最大で $2$ 個必要なので、「$4$」の目が少なくとも $1$ 回は出なければならない。
素因数 $5$ が最大で $1$ 個必要なので、「$5$」の目が少なくとも $1$ 回は出なければならない。

事象 $U$ のうち、$4$ の目が一度も出ない事象を $E$、$5$ の目が一度も出ない事象を $F$ とすると、求める確率は $P(U)$ から事象 $E \cup F$ が起こる確率を引いたものである。

$P(E)$: すべての目が $\{1, 2, 5\}$ から出る確率なので、 $\left( \frac{3}{6} \right)^n = \left( \frac{1}{2} \right)^n$
$P(F)$: すべての目が $\{1, 2, 4\}$ から出る確率なので、 $\left( \frac{3}{6} \right)^n = \left( \frac{1}{2} \right)^n$
$P(E \cap F)$: すべての目が $\{1, 2\}$ から出る確率なので、 $\left( \frac{2}{6} \right)^n = \left( \frac{1}{3} \right)^n$

包除原理より、

$$ \begin{aligned} P(E \cup F) &= P(E) + P(F) - P(E \cap F) \\ &= \left( \frac{1}{2} \right)^n + \left( \frac{1}{2} \right)^n - \left( \frac{1}{3} \right)^n \\ &= 2 \left( \frac{1}{2} \right)^n - \left( \frac{1}{3} \right)^n \\ &= \left( \frac{1}{2} \right)^{n-1} - \left( \frac{1}{3} \right)^n \end{aligned} $$

したがって、求める確率は、

$$ \begin{aligned} P(U) - P(E \cup F) &= \left( \frac{2}{3} \right)^n - \left\{ \left( \frac{1}{2} \right)^{n-1} - \left( \frac{1}{3} \right)^n \right\} \\ &= \left( \frac{2}{3} \right)^n - \left( \frac{1}{2} \right)^{n-1} + \left( \frac{1}{3} \right)^n \end{aligned} $$

解説

最大公約数・最小公倍数の確率に関する標準的な問題である。 (1) のように「最大公約数が $k$」という条件は、「すべてが $k$ の倍数」から「すべてが $2k, 3k, \cdots$ の倍数」などの不要な場合を引くことで求められる。 (2) は「互いに素」を問う確率問題として頻出である。直接求めるのではなく、「素数 $p$ の倍数」の集合を考え、その和集合の確率を包除原理を用いて計算し、余事象を考えるのが鉄則である。 (3) は「最小公倍数が $m$」という条件について、出てもよい目の集合を特定したうえで、不足してはいけない素因数（今回であれば $2^2$ を提供する $4$ と、$5^1$ を提供する $5$）を持つ目が必ず出るように包除原理を用いる典型処理である。