 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2013/discrete-mathematics-probability-and-continuous-mathematics/3/c/solution

i = 1 ⋃ n A_{i} = \emptyset \neq = J \subseteq {1, \dots, n} \sum (- 1)^{∣ J ∣ + 1} j \in J ⋂ A_{j} .

An element present in

r

of the sets is counted

\sum_{k = 1}^{r} (- 1)^{k + 1} (k r) = 1

times, which explains the alternating corrections.

There are

⌊ 999/ d ⌋

positive integers strictly below

1000

divisible by

d

. For the divisors

2, 5, 7

, the single counts are

499, 199, 142

. Their pairwise intersections correspond to divisibility by

10, 14, 35

99, 71, 28

. The triple intersection has

⌊ 999/70 ⌋ = 14

elements. Therefore

499 + 199 + 142 - 99 - 71 - 28 + 14 = 656.

 New to topics? Read the docs here!