3つの集合の個数定理

方針

解答

⓪ 発想 — どう考え始めるか。 「2の倍数が何個か」は簡単だ。$100÷2=50$ 個。部品は全部この調子で数えられる。

問題は重なりだ。2の倍数と3の倍数を足すと、6の倍数を2回数えてしまう。だから引く。

(2)は集合が3つに増える。「1つずつ足す → 2つの重なりを引く → 3つ重なった分を足し戻す」。重なりが何の倍数か(最小公倍数)を確認しながら進める。

100以下で $k$ の倍数の個数は、100を $k$ で割った商(整数部分)で数えられる。記号 $\left[\right]$ はその整数部分を表す。

$$\left[\frac{100}{2}\right]=50,\left[\frac{100}{3}\right]=33,\left[\frac{100}{5}\right]=20,\left[\frac{100}{6}\right]=16,\left[\frac{100}{10}\right]=10,\left[\frac{100}{15}\right]=6,\left[\frac{100}{30}\right]=3$$

(1) 2の倍数の集合を $A$、3の倍数の集合を $B$ とする。「2かつ3の倍数」は6の倍数だから、その個数は16。足して重なりを引くと

$$n(A\cup B)=50+33-16=67(\text{個})$$

(2) 2, 3, 5の倍数の集合を $A,B,C$ とする。まず「2または3または5で割り切れる数」を数える。集合が3つのときは、次の式になる。

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

重なりは、6の倍数・15の倍数・10の倍数・30の倍数の個数だ。順に入れると

$$=50+33+20-16-6-10+3=74$$

符号が「足す→引く→足す」と交互になるのがポイントだ。求めたいのは「どれでも割り切れない数」なので、全体の100から引いて

$$100-74=26(\text{個})$$

発展 — 一歩先へ。 「足す→引く→足し戻す」のリズムは、集合が4つ以上になっても交互に続く(包除原理の一般形)。符号が交互に変わる理由は、「各要素が結局ちょうど1回ずつ数えられるように調整している」からだ。

別解で数えた「$30$ までで $8$ 個」は、$30$ と互いに素な数の個数でもある。この個数を与える関数(オイラー関数)は、整数論の主役の1人として応用問題で再登場する。

別解

(2)は「周期性」で数える方法もある。2でも3でも5でも割り切れないかどうかは、$30$(=$2\times 3\times 5$)ごとに同じパターンを繰り返すからだ。

$1$ から $30$ までで該当する数を書き出すと

$$1,7,11,13,17,19,23,29$$

の $8$ 個。$31$〜$60$、$61$〜$90$ も、それぞれ同じ配置で $8$ 個ずつある。

$90$ までで $8\times 3=24$ 個。残りの $91$〜$100$ は、奇数のうち $3$ でも $5$ でも割れない $91,97$ の $2$ 個。

合わせて $24+2=26$ 個。包除原理と同じ答えに着く。「割り切れるかどうかは周期的」という見方は、この先の整数の性質(余りによる分類)で本格的に活躍する。