【数IA確率・整数】最大公約数と最小公倍数の話を小学校までさかのぼる(北海道大2020文系第3問)

$n$ を 2 以上の自然数とする。1 個のさいころを続けて $n$ 回投げる試行を行い，出た目を順に $X_1,X_2,\cdots,X_n$ とする。(北海道大2020)

(1) $X_1,X_2,\cdots,X_n$ の最大公約数が 3 となる確率を $n$ の式で表せ。

(2) $X_1,X_2,\cdots,X_n$ の最大公約数が 1 となる確率を $n$ の式で表せ。

(3) $X_1,X_2,\cdots,X_n$ の最大公約数が 20 となる確率を $n$ の式で表せ。

最大公約数の考え方

(1)から始めます。

今回はさいころの話なので 1 から 6 の数字でおさらいしてみましょう。

まず，約数から。

1 の約数は，1
2 の約数は，1, 2
3 の約数は，1, 3
4 の約数は，1, 2, 4
5 の約数は，1, 5
6 の約数は，1, 2, 3, 6

次に最大公約数を考えます。たとえば

2 と 4 の最大公約数は 2
3 と 4 の最大公約数は 1
3 と 6 の最大公約数は 3

こうして組み合わせを考えると，最大公約数が 3 となるのは 3 と 6 の組み合わせです。

ちなみに，3 と 5 と 6 の組み合わせだと，最大公約数は 1 です。

つまり，最大公約数が 3 となる場合とは，さいころのすべての数が 3 または 6 である場合のことです。

ただし，すべて 6 だと最大公約数は 6 になってしまうので，すべて 6 の場合を除くことを忘れずに。

さいころを振って 3 または 6 が出る確率は，$\cfrac{2}{6}$

6 が出る確率は $\cfrac{1}{6}$

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

$\Big(\cfrac{2}{6}\Big)^n-\Big(\cfrac{1}{6}\Big)^n=\cfrac{2^n-1^n}{6^n}$
$=\cfrac{2^n-1}{6^n}$ (答え)

余事象を用いる

(2) に進みます。

最大公約数が 1 になる場合を考えると，多くの組み合わせが考えられます。反対に言えば，最大公約数が 1 以外になる場合の方が少ないということです。

そこで，余事象を使って，最大公約数が 1 以外の場合を考えてみます。

(i) 最大公約数が 2 のとき

さいころの目はすべて 2，4，6 のいずれかである。ただし，すべて 4 の場合とすべて 6 の場合を除く。

したがって

$\Big(\cfrac{3}{6}\Big)^n-\Big(\cfrac{1}{6}\Big)^n\times2=\cfrac{3^n-2}{6^n}$

(ii) 最大公約数が 3 のとき

これは(1)で求めた。

(iii) 最大公約数が 4 のとき

さいころの目がすべて 4 のとき，最大公約数は 4 になる。よって，確率は

$\cfrac{1}{6^n}$

(iv) 最大公約数が 5 のとき

(iii)と同様に $\cfrac{1}{6^n}$

(v) 最大公約数が 6 のとき

(iii)と同様に $\cfrac{1}{6^n}$

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

$1-\cfrac{3^n-2}{6^n}-\cfrac{2^n-1}{6^n}-\cfrac{1}{6^n}\times3$
$=\cfrac{6^n-3^n+2-2^n+1-3}{6^n}$
$=\cfrac{6^n-3^n-2^n}{6^n}$ (答え)

最小公倍数の考え方

(3)に進みます。

最小公倍数が 20 ということは，それぞれの数の倍数に 20 が含まれるということです。

たとえば

2 の倍数は $2,4,6,8,10,\cdots,20,\cdots$
5 の倍数は $5,10,15,20,\cdots$

となり，2 と 5 の公倍数に 20 が含まれます。ただし，この場合，最小公倍数は 20 ではなく 10 であることに注意してください。

反対に，倍数に 20 を含まないもの，と言われたら 3 と 6 です。

数をいくつも並べていくとき，その中に 1 つでも 3 か 6 があると，最小公倍数は 20 になりません。つまり，すべての数は 1, 2, 4, 5 のいずれかでなければなりません。

その確率は $\Big(\cfrac{4}{6}\Big)^n$ です。

この中には，すべて 1 の場合や，1, 2 だけで 4, 5 を含まない場合なども含まれていることに注意してください。

つまり，この中には最小公倍数が 20 にならない場合が含まれます。

たとえば，数が 5 個あったとして

1, 2, 2, 5, 5

のとき，最小公倍数は 10 です。

このようにして考えていくと，数の中に 4 と 5 が 1 個以上必要であることが分かります。これは $\Big(\cfrac{4}{6}\Big)^n$ に含まれます。

反対に言えば，$\Big(\cfrac{4}{6}\Big)^n$ の中にある不要なものを取り除けばよい，ということになります。

(i) すべて 1, 2, 4 のとき

$\Big(\cfrac{3}{6}\Big)^n$

ただし，この中には 1, 2 だけの場合も含まれることに注意してください。

(ii) すべて 1, 2, 5 のとき

$\Big(\cfrac{3}{6}\Big)^n$

同様に，この中には 1, 2 だけの場合が含まれます。

このまま引き算すると，1, 2 だけの場合を 2 度引くことになるので，最後にこれを足しましょう。

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

$\Big(\cfrac{4}{6}\Big)^n-\Big(\cfrac{3}{6}\Big)^n-\Big(\cfrac{3}{6}\Big)^n+\Big(\cfrac{2}{6}\Big)^n$
$=\cfrac{4^n-2\cdot3^n+2^n}{6^n}$ (答え)