離散数学・組合せ論の問題

全体集合を $U=\{1,2,\dots ,2000\}$ とし、$A_3,A_5,A_7$ をそれぞれ $U$ のうち 3, 5, 7 で割り切れる整数の集合とする。3, 5, 7 はどの 2 つも互いに素なので、たとえば $A_3\cap A_5$ は 15 の倍数の集合である。$1$ 以上 $N$ 以下の $m$ の倍数の個数は $\lfloor \frac{N}{m}\rfloor$ なので
- $|A_3|=\lfloor 2000/3\rfloor =666$, $|A_5|=\lfloor 2000/5\rfloor =400$, $|A_7|=\lfloor 2000/7\rfloor =285$
- $|A_3\cap A_5|=\lfloor 2000/15\rfloor =133$, $|A_3\cap A_7|=\lfloor 2000/21\rfloor =95$, $|A_5\cap A_7|=\lfloor 2000/35\rfloor =57$
- $|A_3\cap A_5\cap A_7|=\lfloor 2000/105\rfloor =19$

包除原理より
$$|A_3\cup A_5\cup A_7|=(666+400+285)-(133+95+57)+19=1351-285+19=1085.$$
よって、3 でも 5 でも 7 でも割り切れない整数の個数は
$$2000-1085=915.$$

参考: 割り切れない数の割合はおよそ $\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)\left(1-\frac{1}{7}\right)=\frac{48}{105}$ で、$2000\cdot \frac{48}{105}\approx 914.3$ に近い値になっている。

包除原理。$3$ の倍数: $\lfloor 2000/3\rfloor =666$、$5$ の倍数: $400$、$7$ の倍数: $285$。$15$ の倍数: $133$、$21$ の倍数: $95$、$35$ の倍数: $57$。$105$ の倍数: $19$。求める個数は $2000-(666+400+285)+(133+95+57)-19=2000-1351+285-19=915$。検算: 1 から 105 までに 3,5,7 のいずれでも割り切れないものは $\phi$ 型の計算で $2\cdot 4\cdot 6=48$ 個。$2000=105\cdot 19+5$ より $48\cdot 19=912$、残り 1995 より後の $1996,\dots ,2000$ のうち条件を満たすのは $1996,1997,1999$ の 3 個（1998 は 3 の倍数、2000 は 5 の倍数）で、$912+3=915$。