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

Solutions cover all nine questions, including the examination choices. The printed date is 23 June 2022; the released archive places this paper in a directory labelled 2021. The printed title and section order are retained.^[ref]

Public source: Released question-paper archive, member 2021/T/a10100w1.pdf.

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:

The second-derivative criterion for convexity isThe non-strict inequality is necessary and sufficient; the stronger condition $f^{\prime \prime }>0$ is sufficient for strict convexity.

Expand before taking the second derivative:The second-derivative criterion for convexity proves that $f$ is strictly convex, hence convex.

The Hessian criterion for convexity, in the usual twice-differentiable multivariate setting, isThus the Hessian matrix must be a positive semidefinite matrix everywhere. The criterion follows by applying the second-derivative criterion for convexity to each line restriction $t\mapsto g(x+tv)$, whose second derivative is $v^{\mathsf{T}}H(g)(x+tv)v$. Continuous second partials are a sufficient regularity hypothesis for this line-restriction argument.

Writing $g=e^{x^{\mathsf{T}}x}$, the gradient and Hessian matrix areConsequently, for any nonzero $v$,In particular the Hessian matrix is a positive semidefinite matrix everywhere, so the Hessian criterion for convexity proves $g$ is convex. The strict inequality along every nonconstant line also proves strict convexity.

The map $u\mapsto u^2$ is strictly increasing on $[0,\infty )$: for $u,v\ge 0$, $u\le v$ if and only if $u^2\le v^2$. Therefore a point has the smallest $f$-value if and only if it has the smallest $f^2$-value, and the same applies to $g$. By minimizers under strictly increasing transformations, both asserted argmin equalities hold, including when the argmin sets are empty. The differentiability assumptions are unnecessary for this order argument.

Minimize the square of the Euclidean distance, using minimizers under strictly increasing transformations. For $s=x+y>0$,For fixed $s$ the unique minimum has $x=y=s/2$. Put $x=y=\alpha >0$ and $J(\alpha )=2{\alpha }^2+{\ln }^2(2\alpha )$. Its derivative isLet $h(\alpha )=2{\alpha }^2+\ln (2\alpha )$. Since $h^{\prime }(\alpha )=4\alpha +1/\alpha >0$, it is strictly increasing, with limits $-\infty$ and $+\infty$ at the two ends of $(0,\infty )$. It therefore has exactly one zero. The sign of $J^{\prime }$ changes there from negative to positive, proving the unique global minimum. The nearest point is $P=(\alpha ,\alpha ,\ln (2\alpha ))$ at that zero.^[ref]

The Newton root-finding iteration isStarting at $0.4$ gives $0.376376476$, $0.376544572$, and $0.376544582$. Moreover $h(0.3765)<0<h(0.3766)$ certifies the rounding. Thus $\alpha =0.377$ to three significant figures; more accurately $P\approx (0.3765445825,0.3765445825,-0.2835716452)$.

Use Simpson's rule: the cubic exactness of Simpson's rule includes every quadratic integrand, so three function evaluations already give the exact answer. Thus the error is zero. For a general smooth integrand the corresponding composite Simpson's rule has error $O(N^{-4})$ in big O notation, but that bound is unnecessarily weak here.

Use composite Simpson's rule on this smooth, bounded one-dimensional interval. Its fourth derivative is bounded on the interval, so the error bound for composite Simpson's rule gives $O(N^{-4})$ in big O notation as the number of function evaluations increases.

Use tensor-product quadrature with composite Simpson's rule in each coordinate. If there are $m$ subintervals in each direction, then $N=(m+1{)}^2$ and the quadrature rule error is $O(m^{-4})$: apply the one-dimensional error bound for composite Simpson's rule successively, using bounded fourth partial derivatives. Hence the error is $O(N^{-2})$ in big O notation. The rectangular domain makes the product grid convenient.

A convenient choice for this irregular region is Monte Carlo integration. The region is contained in $[-1,1{]}^2$. For independent uniform points $U_j$ in that square, letThe indicator random variable incorporates the curved boundary directly. This estimator is unbiased; the integrand is bounded on the square, so its variance is finite. The variance of a sum of independent terms gives root mean square error $O(N^{-1/2})$ in big O notation. This is a stochastic error rate. Applying a rectangular Simpson's rule to the indicator-weighted integrand would lose the smoothness required for its fourth-order error bound.

For a generic integrand in 20 dimensions, Monte Carlo integration gives root mean square error $O(N^{-1/2})$, whereas tensor-product quadrature with composite Simpson's rule gives only $O(N^{-4/20})=O(N^{-1/5})$. One can sample uniformly in the Euclidean unit ball, for example by an independent uniform direction and radius $U^{1/20}$ with $U$ uniform on $[0,1]$.

For this particular integrand, the most efficient elementary choice uses radial integration over a ball first. The area of the unit 19-sphere is $2{\pi }^{10}/9!$, as follows from the volume of an n-ball. HenceThe reduced integrand is smooth. Apply composite Simpson's rule to obtain $O(N^{-4})$ deterministic error in big O notation, with one original radial integrand evaluation per node. If the selection is restricted to direct multidimensional methods, Monte Carlo integration with $O(N^{-1/2})$ root mean square error is the appropriate choice.

By Taylor's theorem with Lagrange remainder, for an increment $t$,where ${\xi }_t$ lies between $x$ and $x+t$. The given third derivative bound implies $|R_x(t)|\le |t{|}^3/6$.

Apply the preceding Taylor's theorem at $t=h$ and $t=-h$, with $h>0$. The even-order terms cancel in the central finite difference, givingBoth Lagrange remainders have magnitude at most $h^3/6$, so the triangle inequality gives the sharp central-secant derivative error

Write the computed function values as $f(x\pm h)+e_{\pm }$, where $|e_{\pm }|\le \delta$. The computed central finite difference $\tilde{d}$ satisfiesThe two contributions are respectively evaluation absolute error and truncation error. For $\delta >0$, step-size choice for a noisy central derivative minimizes their sum: its derivative is $h/3-\delta /h^2$, negative before and positive afterIf $\delta =0$, the bound tends to zero as $h\downarrow 0$ and has no positive minimizing step.

The derivative is represented by the gradient, and the Hessian matrix contains the second partial derivatives:Equivalently the derivative as a linear map is $Df(x,y)(u,v)=(4x^3-4y)u+(4y-4x)v$.

The stationary point equations give $y=x$ and $x^3=x$, hence $(0,0),(1,1),(-1,-1)$. At $(0,0)$ the Hessian matrix has negative determinant $-16$, so $(0,0)$ is a saddle point. At each of $(1,1)$ and $(-1,-1)$, the Hessian matrix has positive leading minors $12$ and $32$, proving a strict local minimum. More strongly,Thus $(1,1)$ and $(-1,-1)$ are exactly the global minima, with value $3$. There are no local maxima, since any differentiable interior local maximum would be a stationary point, and all three have been classified.

For the equality-constrained minimization problem, $y=8/x$ and $x\ne 0$. Put $t=x^2>0$. The restricted objective isThe only zero has $t^3=64$, so $t=4$. Since $F^{\prime \prime }(t)=2+256/t^3>0$, the second-derivative criterion for convexity proves a unique minimizing $t$. Consequently the equality constraint has minimizers $(2,4)$ and $(-2,-4)$, with minimum $20$.

For the inequality-constrained minimization problem, the identity $f=(x^2-1{)}^2+2(y-x{)}^2+3$ supplies the universal lower bound $3$. Both equality points for that bound, $(1,1)$ and $(-1,-1)$, satisfy $xy=1\le 8$. Hence the inequality constraint has exactly these two minimizers, with minimum $3$.

For Newton's method in optimization, let $\Delta =H(f{)}^{-1}\nabla f$. Its second row equation is $-4{\Delta }_x+4{\Delta }_y=4y-4x$, so ${\Delta }_y={\Delta }_x+y-x$. Therefore $y_{n+1}=y_n-{\Delta }_y=x_n-{\Delta }_x=x_{n+1}$. The given first coordinate yieldsThe Newton step is defined where $\det H(f)=16(3x^2-1)\ne 0$; both coordinates after any defined step are equal.

By the diagonal reduction in a two-variable Newton iteration, $y_n=x_n$ for $n\ge 1$. Put $e_n=x_n-1$. Direct factorization gives the exact Newton map in optimization error identityThe assumed convergence $x_n\to 1$ makes the final factor tend to $3/2$, so it is bounded for all sufficiently large $n$. Hence $|e_{n+1}|\le C|e_n{|}^2$. For the Euclidean norm error $E_n=\Vert (x_n,y_n)-(1,1)\Vert =\sqrt{2}|e_n|$, this becomes $E_{n+1}\le (C/\sqrt{2})E_n^2$, proving quadratic convergence. Unless the exact limit is reached in finitely many steps, $E_{n+1}/E_n^2\to 3/(2\sqrt{2})$.