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 / a

Table of contents
- i a
  - Solution i
- ii a
  - Solution ii
- iii a
  - Solution iii
- iv a
  - Solution iv

i

Solution

For pairwise disjoint finite sets, the rule of sum gives

∣ ⋃_{i = 1}^{n} A_{i} ∣ = \sum_{i = 1}^{n} ∣ A_{i} ∣.

The password sets of different lengths are disjoint, so the required number is $P_{4} + P_{6} + P_{8}$ .

ii

Solution

The rule of subtraction is

∣ A ∖ B ∣ = ∣ A ∣ - ∣ A \cap B ∣.

In particular, if

B \subseteq A

are finite sets, the set difference has cardinality

∣ A ∣ - ∣ B ∣

.

iii

Solution

The rule of product says that a sequence of

k

choices, with

n_{i}

possibilities at stage

i

regardless of earlier choices, has $\prod_{i = 1}^{k} n_{i}$ possible outcomes. Applied to the Cartesian product of finite sets, it gives

∣ A \times B ∣ = ∣ A ∣∣ B ∣

. Here independence means that the available choices do not restrict one another; no probability assumption is needed.

iv

Solution

The rule of product counts

7^{4}

unrestricted passwords and

6^{4}

passwords containing no A. By the rule of subtraction, the answer is

7^{4} - 6^{4} = 2401 - 1296 = 1105.

 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