Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics, and probability / Discrete mathematics / 1 / c

Table of contents
- i c
  - Solution i
- ii c
  - Solution ii

i

Solution

For finite sets, the inclusion-exclusion principle states

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

Thus single-set cardinalities are added, pairwise-intersection cardinalities subtracted, triple-intersection cardinalities added, and so on.

ii

Solution

Let

A_{d}

contain the multiples of

d

among

1, \dots, 999

. Its cardinality is

⌊ 999/ d ⌋

, using the floor function. Because

3, 7, 11

are pairwise coprime, their pairwise intersections correspond to divisibility by

21, 33, 77

, and their triple intersection to divisibility by

231

. The inclusion-exclusion principle gives

333 + 142 + 90 - 47 - 30 - 12 + 4 = 480.

 Ancestors (12)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version