Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Discrete mathematics, probability and continuous mathematics (4223)

Solutions to the nine questions in the original paper.^[ref]

Write each set difference as an intersection with a complement of a set. Applying De Morgan's laws and then the distributive property givesThe complements turn the inner union into an intersection and vice versa. Thus

Apply the distributive property to the intersection with $\overline{C}$:In the first line the repeated factor $\overline{C}$ changes nothing. Rewriting in terms of set differences yields

Use De Morgan's laws to remove the complement of a set, then distribute the two unions:The first and last intersections in the middle line are the empty set. The remaining union is precisely the collection of elements belonging to exactly one of the original sets. Therefore both expressions define the same symmetric difference:

An algebraic way to prove the set identity is to show that $D=\overline{A}\cup \overline{B}$ is a complement of a set for $A\cap B$. By the distributive property,andA complement of a set is unique: if $D,E$ both complement $S$, then $D=D\cap (S\cup E)=D\cap E$, and similarly $E=D\cap E$. Consequently

Write the set difference as an intersection and use the fact that taking the complement of a set twice returns that set. The commutativity of intersection gives the reversible calculation

Use the symmetric difference formula from part (b), followed by the set difference identity from part (c)(ii):Taking both complements swaps the two ways to belong to exactly one set, leaving their union unchanged:

The image of a function is the set of values actually attained as its argument ranges over its domain of a function:It is a subset of the codomain $B$, and need not equal $B$.

The function is surjective, also called onto, when every element of its codomain has at least one preimage:The condition concerns the specified codomain, not just the formula defining the function.

The function is injective, also called one-to-one, when equal outputs force equal inputs:Equivalently, different elements of the domain of a function always have different images.

A bijection is a function that is both injective and surjective. Each element of the codomain then has exactly one preimage:This unique-preimage property allows the inverse function $f^{-1}:B\to A$ to be defined on all of $B$.

If $n$ is positive and odd, $n^2$ is odd. The function $x\mapsto x^{n^2}$ is a strictly increasing function on the real numbers, so it is injective. Every real $y$ has the real odd root $\mathrm{sgn}(y)|y{|}^{1/n^2}$, so the function is also surjective.

If $n$ is positive and even, the exponent is positive and even. Then $f(1)=f(-1)$, while $f(x)\ge 0$ for all real $x$. These facts disprove injectivity and surjectivity, respectively. ThereforeIf the convention $0\in \mathbb{N}$ is used, $n=0$ gives exponent zero. Interpreting $x^0$ as the constant polynomial $1$ makes the function neither injective nor surjective. If $0^0$ is left undefined, that case does not define the stated function on all the real numbers. Neither convention adds a qualifying value of $n$.

The function composition of two bijections is a bijection. Its inverse function is two-sided, soThis is exactly the defining cancellation property of an inverse function, with the whole function composition regarded as one function.

The inverse factors are generally in the wrong order. For a counterexample, take the bijections $f(x)=x+1$ and $g(x)=2x$, with inverse functions $f^{-1}(x)=x-1$ and $g^{-1}(x)=x/2$. ThenThusFor particular bijections that commute the equality can hold; the claim fails as a universal assertion.

Use the associativity of function composition to cancel adjacent inverse functions in the right order:Therefore

For the bijections $f(x)=x+1$ and $g(x)=2x$ used above, $f\circ g$ sends $x$ to $2x+1$. Its inverse function sends $x$ to $(x-1)/2$, whereas $f^{-1}\circ g^{-1}$ sends $x$ to $x/2-1$. Hence

The proposed inverse function cancels on both sides:The uniqueness of an inverse function therefore givesThe operation applied last must be undone first.

The Big O notation asserts an eventual uniform bound on the size of $f$ by a constant multiple of the size of $g$:The constants $C,n_0$ may depend on the two functions but cannot depend on $n$. Absolute values matter because the stated functions can be real-valued with either sign.

The logarithm identity $a^{{\log }_{b}n}=n^{{\log }_{b}a}$ rewrites the expression as $n^{{\log }_{2}3}$. Since $3<4=2^2$, we have ${\log }_{2}3<2$, and for $n\ge 1$,Thus the Big O notation bound holds with $C=1$:

The logarithm laws giveFor $n\ge 2$, both $n\le n{\log }_{2}n$ and ${\log }_{2}n\le n{\log }_{2}n$. The expression is therefore at most $(3+{\log }_{2}5)n{\log }_{2}n$. ConsequentlyThe Big O notation concerns eventual behaviour; the zero value of $n{\log }_{2}n$ at $n=1$ is irrelevant.

Divide by the proposed comparison function $2^n$:The ratio is unbounded, so no constant in the definition of Big O notation can work:

The exponential function eventually grows faster than the fixed polynomial. A direct justification uses the ratio $r_n=4^n/n^4$:For all sufficiently large $n$, this ratio exceeds $2$, so $r_n$ grows without bound. The proposed Big O notation bound is therefore impossible:

Treat $a,b$ as fixed positive integers. For $n\ge 1$, $n^2+a\le (1+a)n^2$. Raising this inequality to the positive power $b$ givesThe factor $(1+a{)}^b$ is independent of $n$, as required by Big O notation. HenceA bound uniform over varying $a,b$ is not what the notation here asserts.

By Big O notation, there are $C_1,C_2>0$ and thresholds after which $f_1(n)\le C_1{g}_1(n)$ and $f_2(n)\le C_2{g}_2(n)$. Choose a common threshold and set $C=\max (C_1,C_2)$. The positivity assumption givesSquaring preserves this inequality, so

First consider powers of four, with a fixed finite base value. For a mathematical induction hypothesis $x_{n/4}\le C(n/4{)}^2$, the recurrence relation givesprovided $C\ge 4/3$ and $C$ also covers the base value.

The allowed integer rounding needs a little more care. Suppose the recurrence relation is applied above fixed base cases, as usual; applying $x_1=4x_1+1$ with a ceiling would not define a positive sequence. For either rounding write $m=\lceil n/4\rceil$ or $m=\lfloor n/4\rfloor$. For $n\ge 6$,Choose $C\ge 16/7$ large enough to bound all finitely many positive-index base values below $6$. By strong induction,This argument starts at $n=6$, so the floor convention's index zero, if used in an earlier base calculation, is absorbed into those fixed initial values. Thus, for either convention with a well-defined finite base,

In modular arithmetic, calculations may be performed after replacing each input by its remainder. For a positive modulus $m$, write $[a{]}_m$ for the remainder in $\{0,\dots ,m-1\}$. ThenEquivalently, if $a\equiv a^{\prime }(\mathrm{mod}m)$ and $b\equiv b^{\prime }(\mathrm{mod}m)$, addition and multiplication give $a+b\equiv a^{\prime }+b^{\prime }$ and $ab\equiv a^{\prime }{b}^{\prime }$, and a fixed nonnegative integer exponent gives $a^k\equiv (a^{\prime }{)}^k$. One cannot in general reduce the exponent modulo $m$ by this rule.

Use modular arithmetic to keep all intermediate numbers small:Thus $34\cdot 45\cdot 55+89\equiv 2\cdot 5\cdot 7+1=71\equiv 7\equiv -1(\mathrm{mod}8)$. Cubing gives

Repeated squaring computes $a,a^2,a^4,a^8,\dots$ by successively squaring. The binary representation of the exponent specifies which of these values to multiply. For modular exponentiation, reduce after every multiplication; only a number of steps proportional to the logarithm of the exponent is needed.

Here $13\equiv 2(\mathrm{mod}11)$ and $17=16+1$. Successive squares giveTherefore

Mathematical induction has two obligations. Establish the base case $S(0)$ if the natural numbers start at zero, or $S(1)$ if they start at one. Then prove the induction step: for an arbitrary natural $k$ in the relevant range, assume $S(k)$ and deduce $S(k+1)$.

The base case starts the chain, and the step propagates truth to every subsequent natural number:

The base case is $F_5=5$, so $5\mid F_5$. To relate successive blocks of five, use the Fibonacci addition formula:This identity can also be obtained simply by applying the Fibonacci recurrence five times. If the mathematical induction hypothesis is $5\mid F_{5n}$, thenis a sum of two multiples of five. HenceThe generalisation is Fibonacci multiple-index divisibility:Indeed, $F_{mn+m}=F_m{F}_{mn+1}+F_{m-1}{F}_{mn}$, so precisely the same mathematical induction works with $5$ replaced by $m$.

For finite sets, the inclusion-exclusion principle statesAn element present in $r$ of the sets is counted ${\sum }_{k=1}^r(-1{)}^{k+1}(\genfrac{}{}{0ex}{}{r}{k})=1$ times, which explains the alternating corrections.

There are $\lfloor 999/d\rfloor$ 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$, giving $99,71,28$. The triple intersection has $\lfloor 999/70\rfloor =14$ elements. Therefore

A binary relation $R$ on $A$ is a subset of $A\times A$. Its properties are quantified over elements of $A$:

Thus an equivalence relation is a binary relation that is simultaneously reflexive, symmetric and transitive. The equivalence class of $a$ is the set of all elements related to it:Antisymmetry permits diagonal pairs and does not mean that a binary relation fails to be a symmetric relation.

The binary relation $\le$ is reflexive and transitive but is not a symmetric relation. For example, $1\le 2$ while $2\nleqq 1$. ThereforeThere are consequently no equivalence classes for this binary relation in the requested sense.

This is equality of remainders in modular arithmetic. It is reflexive because $3\mid (n-n)=0$, symmetric because $3\mid (n-m)$ implies $3\mid (m-n)$, and transitive because $3\mid (n-m)$ and $3\mid (k-n)$ imply $3\mid (k-m)$ by addition. ThusIts three equivalence classes areIf zero is included in $\mathbb{N}$, it belongs to $C_0$; otherwise that class starts at three.

In a symmetric relation, each of the $n$ diagonal pairs $(a,a)$ can be chosen independently. For each of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ unordered pairs of distinct elements, either both ordered pairs $(a,b),(b,a)$ occur or neither occurs. Every such choice is free and produces a distinct symmetric relation. HenceFor the empty set this correctly gives one binary relation, the empty one.

Take each partial derivative while holding the other coordinate fixed. Differentiating the polynomial term by term givesSince the function is a polynomial, both orders of the mixed partial derivative agree everywhere.

The multivariable chain rule follows the change of both coordinates along the parametric curve:Substituting the partial derivatives from part (a), with $x=1+s^2$ and $y=e^s$, yieldsThe first term comes from changing $x$, and the remaining terms from changing $y$.

At the origin the needed partial derivatives areThe Taylor series through total degree two is thereforewhich givesHere total degree is what matters: $x^2{y}^2$ is quartic, not quadratic. The exact omitted polynomial is $y^3+x^2{y}^2+x^2{y}^4$, which verifies the stated Big O notation remainder directly.

A critical point requires $f_x=f_y=0$. Since $y^4+y^2+1>0$ for every real $y$, the first partial derivative forces $x=0$. The second then reduces to $3y^2-3=0$, so the only critical points are $(0,1)$ and $(0,-1)$.

At these points the Hessian matrix is diagonal:The first is a positive-definite matrix, giving a strict local minimum; the second is an indefinite matrix, giving a saddle point. Their values are $f(0,1)=-1$ and $f(0,-1)=3$. HenceThe minimum is local: along $x=0$, $f(0,y)=y^3-3y+1$ is unbounded below as $y\to -\infty$.

Differentiate the product $4(x-1{)}^{-2}(x+1{)}^{-1}$ using the product rule and chain rule:Combining terms over a common denominator gives

For a partial fraction decomposition, writeMultiplying by $(x-1{)}^2(x+1)$ gives $4=A(x^2-1)+B(x+1)+C(x-1{)}^2$. Setting $x=1,-1$ gives $B=2,C=1$, and comparing the coefficient of $x^2$ gives $A=-1$. ThusIntegrating each term gives the antiderivativeThe constant of integration can be chosen independently on each interval separated by $-1$ and $1$.

The power rule for a definite integral gives