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

For pairwise disjoint finite sets, the rule of sum givesThe password sets of different lengths are disjoint, so the required number is $P_4+P_6+P_8$.

The rule of subtraction isIn particular, if $B\subseteq A$ are finite sets, the set difference has cardinality $|A|-|B|$.

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.

The rule of product counts $7^4$ unrestricted passwords and $6^4$ passwords containing no A. By the rule of subtraction, the answer is

The power set is $\mathcal{P}(A)=\{B:B\subseteq A\}$, the set of all subsets of $A$. In this case,

Each of the $n$ elements is either included or excluded, so the rule of product gives $|\mathcal{P}(\{1,\dots ,n\})|=2^n$. Alternatively, partition the power set into disjoint families according to cardinality. The family of $k$-element subsets has size equal to the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$. The rule of sum therefore gives

For finite sets, the inclusion-exclusion principle statesThus single-set cardinalities are added, pairwise-intersection cardinalities subtracted, triple-intersection cardinalities added, and so on.

Let $A_d$ contain the multiples of $d$ among $1,\dots ,999$. Its cardinality is $\lfloor 999/d\rfloor$, 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

The pigeonhole principle states that if $N$ objects are placed in $k$ boxes and $N>k$, at least one box contains at least two objects.

Set $m=\lceil N/k\rceil$, using the ceiling function. If no box contains at least $m$ objects, all boxes contain at most $m-1$, so the total number of objects is at most $k(m-1)$. Taking the contrapositive, a total greater than $k(m-1)$ forces some box to contain at least $m$ objects. But $m-1<N/k$, hence $k(m-1)<N$. This proves the generalized pigeonhole principle: some box contains at least $\lceil N/k\rceil$ objects.

By the generalized pigeonhole principle, 13 cards guarantee $\lceil 13/4\rceil =4$ cards in one suit. The guarantee is sharp: 12 cards can consist of three cards from each suit, with no four cards of a common suit.

Use mathematical induction on $n\ge 0$. For $n=0$, the sum is $0!0=0=1!-1$. Suppose it is $(n+1)!-1$ at $n$. ThenThe induction is complete, proving ${\sum }_{i=0}^{n}i!i=(n+1)!-1$. The factorial identity $i!i=(i+1)!-i!$ also explains the cancellation directly.

In big O notation, $f(n)=O(g(n))$ means that there exist $C>0$ and $n_0$ such that $|f(n)|\le C|g(n)|$ for every integer $n\ge n_0$. For the required polynomial versus exponential growth comparison, $3^3=3^3$. If $n^3\le 3^n$ and $n\ge 3$, thenBy mathematical induction, $n^3\le 3^n$ for all $n\ge 3$. Thus $n^3=O(3^n)$, with $C=1$ and $n_0=3$.

A binary relation $R$ on $A$ is a reflexive relation precisely when $aRa$ for every $a\in A$.

A binary relation $R$ on $A$ is a symmetric relation precisely when $aRb\Rightarrow bRa$ for all $a,b\in A$.

A binary relation $R$ on $A$ is an antisymmetric relation precisely when $(aRb\text{and}bRa)\Rightarrow a=b$ for all $a,b\in A$.

A binary relation $R$ on $A$ is a transitive relation precisely when $(aRb\text{and}bRc)\Rightarrow aRc$ for all $a,b,c\in A$.

A binary relation is an equivalence relation precisely when it is reflexive, symmetric, and transitive.

For a counterexample to closure under union of antisymmetric relations, take $A=\{0,1\}$, $R=\{(0,1)\}$, and $S=\{(1,0)\}$. Each is an antisymmetric relation: neither contains an off-diagonal pair together with its reverse. But $R\cup S$ contains both $(0,1)$ and $(1,0)$ while $0\ne 1$. Therefore $R\cup S$ is not an antisymmetric relation.

Write $q(x,y)=x^2+y^2$. Equality of $q$-values defines an equivalence relation induced by a function: equality is reflexive, symmetric, and transitive, so all three properties hold for $R$. The equivalence class of $(x,y)$ isFor $(x,y)\ne (0,0)$ this is the circle centred at the origin with radius $\sqrt{x^2+y^2}$; the remaining equivalence class is the singleton $\{(0,0)\}$.

This binary relation is not an equivalence relation, because it is not symmetric: $(0,0)R(0,1)$ since $0\le 1$, but $(0,1)R(0,0)$ is false. In fact the injective encoding $(a,b)\mapsto 10a+b$ gives a total order. There are no equivalence classes for this binary relation.

Every nonzero integer $a$ has $a^2>0$, proving reflexivity. Because $ab=ba$, the relation is symmetric. If $ab>0$ and $bc>0$, then $ac=(ab)(bc)/b^2>0$, proving transitivity. Thus this is an equivalence relation, whose two equivalence classes are the positive integers and the negative integers: