Question

Use the principle of inclusion and exclusion to find the number of positive integers less than 1,000,000 that are not divisable by 6 or 4

Answer 1

This is a simple problem based on combinatorics which can be easily tackled by using inclusion-exclusion principle.
We are asked to find number of positive integers less than 1,000,000 that are not divisible by 6 or 4.
let n be the number of positive integers.
∴ 1≤n≤999,999
Let c₁ be the set of numbers divisible by 6 and c₂ be the set of numbers divisible by 4.
Let N(c₁) be the number of elements in set c₁ and N(c₂) be the number of elements in set c₂.

∴N(c₁) = $\frac{999,999}{6} = 166666$
N(c₂) = $\frac{999,999}{4} = 250000$
∴N(c₁c₂) = $\frac{999,999}{24} = 41667$
∴ Number of positive integers that are not divisible by 4 or 6,

N(c₁`c₂`) = 999,999 - (166666+250000) + 41667 = 625000
Therefore, 625000 integers are not divisible by 6 or 4