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

Source paper: released examination archive, member 2017/T/a10100w1.pdf. The printed cover dates the examination to 19 June 2018. All nine questions and every printed subpart are answered below. The original scan contains a reversed inequality in part 6(d); its solution states and proves the corrected direction.

We prove both set inclusions. If $x\in A\setminus (A\setminus B)$, then $x\in A$ and $x\notin A\setminus B$. Since $x\in A$, the latter condition forces $x\in B$, giving $x\in A\cap B$. Conversely, if $x\in A\cap B$, then $x\in A$ and $x\notin A\setminus B$, so $x\in A\setminus (A\setminus B)$. By set extensionality, the two sets are equal. This is a double inclusion proof; the implication involving the set difference uses membership in $A$ explicitly.

False. Take the sets $A=\{1\}$, $B=\varnothing$ and $C=\varnothing$. Both intersections with $C$ are empty, although $A\ne B$. Intersecting with $C$ loses information about membership outside $C$.

False. Take the sets $A=\{1\}$, $B=\varnothing$ and $C=\{1\}$. Both unions with $C$ equal $\{1\}$, although $A\ne B$. Taking a union with $C$ conceals which of its elements belonged to the original set.

True. The two operations retain complementary membership information. For $x\in C$, equality of the intersections makes $x\in A$ equivalent to $x\in B$. For $x\notin C$, equality of the unions makes $x\in A$ equivalent to $x\in B$. These cases exhaust every possible element. Set extensionality therefore gives $A=B$. Equivalently, reconstruct either set fromSubstituting the two given equalities into this expression gives $B$.

False. With the sets $A=\{1\}$, $B=\varnothing$ and $C=\{1\}$, both set differences are empty but $A\ne B$. Removing $C$ loses the distinction between their memberships inside $C$.

True. Fix $a\in A$. Reflexivity supplies $a{R}_{1}a$ and $a{R}_{2}a$. In the definition of composition of relations, choose the intermediate element to be $a$ itself. Then $a(R_2\circ R_1)a$. This holds for every $a\in A$, so the composite binary relation is reflexive.

False, even for two equivalence relations. On $A=\{1,2,3\}$, let $R_1$ have equivalence classes $\{1,2\}$ and $\{3\}$, and let $R_2$ have equivalence classes $\{1\}$ and $\{2,3\}$. Both binary relations are transitive. For $S=R_2\circ R_1$, we have $3S2$, using the intermediate element $3$, and $2S1$, using the intermediate element $1$. However, $3S1$ fails: the only $R_1$-successor of $3$ is $3$, and $3R_{2}1$ is false. Thus the composite fails transitivity. The order of composition here means first $R_1$, then $R_2$.

False. Use the same two equivalence relations as in part (ii). They are both symmetric relations. The composite contains $1S3$, since $1R_{1}2$ and $2R_{2}3$. It does not contain $3S1$, as shown there. Hence composition of relations need not preserve symmetry of a relation, even when both factors are also reflexive and transitive.

Let $x_i$ be the number in box $i$ and put $y_i=x_i-1$. We count integer compositions satisfying $y_1+\cdots +y_4=6$ and $0\le y_i\le 4$. Without the upper bounds, stars and bars gives $\left(\genfrac{}{}{0ex}{}{9}{3}\right)=84$. If a specified $y_i\ge 5$, subtract five from it; the remaining nonnegative integer variables sum to one, giving $\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$ possibilities. Two violations cannot occur because they would require a sum at least ten. The inclusion-exclusion principle therefore givesThe boxes are distinguished by their positions in the composition; individual objects are not distinguished.

Use modular exponentiation by repeated squaring:Since $17=16+1$, multiply the indicated powers to obtain $27^{17}\equiv 6(\mathrm{mod}7)$. Only the binary expansion of the exponent determines which squared powers are multiplied.

Choose the representative $1\le a\le p-1$. Since $p$ is prime and does not divide $a$, their greatest common divisor is one. The extended Euclidean algorithm gives the Bezout identityfor some integers $x,y$. Reducing modulo $p$ gives $ax\equiv 1(\mathrm{mod}p)$, so the residue class of $x$ is a multiplicative inverse of $a$. The argument uses the nonzero condition to exclude the only residue with greatest common divisor $p$.

First prove $a^p\equiv a(\mathrm{mod}p)$ for every nonnegative integer $a$ by mathematical induction. The case $a=0$ is immediate. If it holds at $a$, the binomial theorem and the stated divisibility of the middle binomial coefficients giveThis establishes the induction. For an arbitrary integer $a$, take a nonnegative representative $r$ of its residue class; then $a^p\equiv r^p\equiv r\equiv a(\mathrm{mod}p)$. When $a\not\equiv 0(\mathrm{mod}p)$, part (b) supplies a multiplicative inverse modulo $p$. Multiplying the congruence by that inverse proves Fermat's little theorem:

Absorb the finitely many exceptional initial terms in the Big O notation assumption into a constant $C>0$, so that $|a_n|\le Cn$ for every $n\ge 1$. This is possible because each initial term is finite and each index is positive. We prove the stronger bound $|{}^k{b}_n|\le Cn$ for every $k,n\ge 1$.

The case $k=1$ is the chosen bound. If it holds at $k-1$, the triangle inequality givesMathematical induction completes the proof. Thus ${}^k{b}_n=O(n)$ for every fixed $k$; in fact the same constant works for all the iterated Cesàro means. This is the linear-growth bound for iterated Cesàro means.

For these real-valued functions, $f(n)=O(g(n))$ means that there exist constants $C>0$ and $N\in \mathbb{N}$ such thatThe absolute values matter because neither function is assumed nonnegative. The constants are independent of $n$; finitely many earlier values do not affect Big O notation.

True. For every integer $n\ge 1$, $n^{3/2}\le n^2$ and $1\le n^2$, soThus $C=14$ and $N=1$ witness the required Big O notation bound.

False. Set $r_n=n!/2^n$. The ratio of successive terms isConsequently $r_n\ge r_3{2}^{n-3}$ for $n\ge 3$, which is unbounded. No constant can bound $n!$ by that constant times $2^n$ for all sufficiently large $n$. The factorial therefore fails the proposed Big O notation bound, without needing Stirling's formula.

True. Every term has $k^2\le n^2$ when $1\le k\le n$. Adding these $n$ inequalities givesThe constants $C=1$ and $N=1$ suffice in the definition of Big O notation.

False. The sum of squares of the first n positive integers givesThis ratio is unbounded, so it cannot satisfy the constant bound required by Big O notation. In fact the sum has order $n^3$, as its leading term also shows.

An element $u\in A$ is a least upper bound of $S$ if it is an upper bound, meaning $s\le u$ for every $s\in S$, and $u\le v$ for every upper bound $v\in A$ of $S$. The candidate need not belong to $S$. Because a partial order is an antisymmetric relation, two least upper bounds must be equal. A least upper bound is also called the supremum.

An element $m$ is a maximum of $S$ if $m\in S$ and $s\le m$ for every $s\in S$. Thus it is an upper bound that is itself a member. Every maximum is the least upper bound: any upper bound must lie above $m$ because $m\in S$. A supremum outside $S$ need not be a maximum.

Under the product order, every point of the open unit disc has both coordinates below one, so $(1,1)$ is an upper bound. Any upper bound $(u,v)$ must have $u\ge 1$ and $v\ge 1$, since the two coordinate projections of the open unit disc are $(-1,1)$. Therefore $(1,1){\le }_P(u,v)$, proving ${\sup }_{{\le }_P}S=(1,1)$.

Under the lexicographic order, every point $(1,v)$, with arbitrary real $v$, is an upper bound, because every point of $S$ has first coordinate strictly below one. Conversely, an upper bound cannot have first coordinate $u<1$: a point $(x,0)\in S$ with $x>u$ would exceed it. If an upper bound has $u>1$, the upper bound $(1,0)$ is strictly smaller. If it is $(1,v)$, the upper bound $(1,v-1)$ is strictly smaller. Hence there is no least upper bound under the lexicographic order. This illustrates the supremum of an open disc under product and lexicographic orders.

The function is even, so every sine coefficient is zero. Its mean coefficient isFor $n\ge 1$, compute $a_n=(2/\pi ){\int }_0^{\pi }\sin x\cos (nx)\mathrm{d}x$. The product-to-sum identity makes this integral zero for odd $n$ and gives $-4/(\pi (n^2-1))$ for even $n$. Thus the missing Fourier coefficients are $a_n=0$ for odd $n$ and $b_n=0$ for every $n$, with $a_0=4/\pi$. Equivalently,The Fourier series converges to this continuous periodic function; there is no jump value to average.

For $x>0$, substitute $v=y/x$. Then $y^{\prime }=v+x{v}^{\prime }$, and cancellation reduces the differential equation to $v^{\prime }+2v=e^{-2x}$. Multiplication by the integrating factor $e^{2x}$ gives $(e^{2x}v{)}^{\prime }=1$. ThereforeDirect substitution gives $y^{\prime }+2y-y/x=x{e}^{-2x}$ and verifies the result. Dividing by $x$ is legitimate on the stated positive domain.

The integrating factor is $e^{2x}$, so the differential equation becomes $(e^{2x}y{)}^{\prime }=1$. Integration givesThe factor $x$ in the particular solution accounts for the forcing term being proportional to the homogeneous solution.

Here the integrating factor is $e^{2\sin x}$, since its logarithmic derivative is $2\cos x$. Multiplying the differential equation by it cancels the right-hand exponential and yields $(e^{2\sin x}y{)}^{\prime }=1$. HenceThis formula is actually defined for every real $x$.

Seek a periodic particular solution with Fourier coefficients $A_n,B_n$. Comparing constant terms gives $A_0=a_0/2$. Comparing the cosine and sine terms for $n\ge 1$ givesso $A_n=2a_n/(n^2+4)$ and $B_n=n{a}_n/(n^2+4)$. Insert the coefficients from part (a) and add the homogeneous solution:The differentiated series converges absolutely and uniformly, because its largest coefficient terms are $O(m^{-2})$. This justifies the term-by-term first derivative used in substituting into the differential equation. Any two solutions differ by $C{e}^{-2x}$, proving that the displayed family is the general solution. The computation is an instance of Fourier response of a first-order linear differential equation.

The coordinate sum is $2\sin t$, while the sum of their cubes is $6\sin t-4{\sin }^{3}t$. Along the parametrized curve, the composite function is therefore $-3\sin t/2-{\sin }^{3}t/3$. Differentiate, or apply the multivariable chain rule, to obtain

Apply Newton's method to $F(t)=1-3\sin t/2-{\sin }^{3}t/3$. The derivative in part (a) givesChoose a starting point near a desired root, such as $t_0=0.6$ for the root in $(0,\pi /2)$; do not divide when $\cos t_k=0$. On $(0,\pi /2)$, $F$ is strictly decreasing and changes sign between its endpoints, so the intermediate value theorem gives exactly one root there. Its derivative is nonzero, giving the usual local convergence of Newton's method. The periodic function has other roots; the iteration does not impose global uniqueness or convergence from every starting value.

The gradient vanishes exactly when $x^2/4-1=0$ and $y^2/4-1=0$, giving the four points $(\pm 2,\pm 2)$. The Hessian matrix is $\mathrm{diag}(x/2,y/2)$. It is positive definite at $(2,2)$, negative definite at $(-2,-2)$, and indefinite at the two mixed-sign points. Thus $(2,2)$ is a strict local minimum, $(-2,-2)$ a strict local maximum, and $(2,-2),(-2,2)$ are saddle points by the second-derivative test. Their respective function values are $-8/3$, $8/3$, and zero at both saddle points.

Substituting $y=-x$ cancels both the cubic and linear terms, leaving $f(x,-x)=0$ for every real $x$. Thus the constrained maximum and minimum are both zero, attained everywhere on the constraint line. The feasible set is unbounded, but the restricted function is constant; compactness is not needed here.

Write $f(x,y)=g(x)+g(y)$ with $g(s)=s^3/12-s$. On $[0,4]$, its derivative is $g^{\prime }(s)=s^2/4-1$, negative below two and positive above two. Compare the critical and endpoint values:Each coordinate can be chosen independently. Therefore the global minimum is $-8/3$ at $(2,2)$, and the global maximum is $8/3$ at $(4,4)$. This comparison includes the boundary of the rectangle, rather than classifying only interior stationary points.

The continuous function attains a global maximum and minimum on the closed disc by the extreme value theorem. All four unconstrained stationary points have squared distance eight, so none lies in its interior. The extrema must therefore lie on $x^2+y^2=6$.

The constraint gradient is nonzero on that circle, so Lagrange multipliers apply:Subtracting gives $(x-y)((x+y)/4-2\lambda )=0$. If $x=y$, the constraint gives $x=y=\pm \sqrt{3}$. Otherwise $2\lambda =(x+y)/4$; substitution into either equation gives $xy=-4$. This is impossible, since $|xy|\le (x^2+y^2)/2=3$ on the circle. Thus the diagonal points are the only candidates. Comparing their values gives

Repeated use of the product rule and chain rule givesThe denominators are strictly positive on the whole real line, making the signs in the next parts easy to read.

The critical points of $f^{\prime \prime }$ occur where $f^{\prime \prime \prime }=0$, namely $-1,0,1$. Its sign on the four intervals separated by these points is, in order, positive, negative, positive, negative. Thus $f^{\prime \prime }$ has local maxima at $\pm 1$ and a local minimum at zero. Their values areSince $f^{\prime \prime }(x)\to 0$ at both ends of the real line, these are also the global maximum $1/2$ and the global minimum $-2$. The sign analysis establishes extremality; merely solving $f^{\prime \prime \prime }=0$ would not.

The Taylor polynomial uses $f(1)=1/2$, $f^{\prime }(1)=-1/2$ and $f^{\prime \prime }(1)=1/2$. ThereforeThe quadratic coefficient is $f^{\prime \prime }(1)/2!$, not $f^{\prime \prime }(1)$.

The printed inequality has its sign reversed: $f(x)<f_2(x)$ for $x>1$. This is present in the original scan, rather than arising in transcription. For $x>1$, Taylor's theorem with Lagrange remainder givesPart (a) has $f^{\prime \prime \prime }(\xi )<0$, so the remainder is strictly negative. As an independent check, direct algebra gives the quadratic Taylor majorant of a reciprocal quadratic:For example, $f(2)=1/5<1/4=f_2(2)$ is already a counterexample to the requested direction. The exact identity also shows that this polynomial majorizes $f$ on the entire real line, with equality only at one.

With unit strip width, the composite trapezoidal rule givesFor Simpson's rule, the even integer arguments are the odd-numbered interior grid positions. ThereforeThe requested two-decimal answers are $T_{24}\approx 0.79$ and $S_{24}\approx 0.75$. The supplied component sums are individually rounded; they should not be treated as exact simultaneous identities. Computing from the original function gives approximately $0.786685$ and $0.748700$, respectively, with the same two-decimal results.

For $n$ equal strips and a uniform bound $|f^{\prime \prime }(x)|\le M$ on $[a,b]$, the composite trapezoidal error bound isOn $[1,25]$, part (b) gives $M=1/2$: $f^{\prime \prime }$ is positive and decreases from $1/2$ after $x=1$. HenceTo certify error at most $10^{-4}$, choose $n\ge 2400$; equality gives exactly $10^{-4}$ in this bound. This is a sufficient certificate, not a claim that every smaller $n$ fails in actual numerical error.

Strictly, the maximum specified over the open interval $(1,25)$ is not attained; its supremum is $1/2$. Using the maximum on the closed interval, or simply the uniform bound $M=1/2$, gives the valid error estimate above.

The probability measure $\mathbb{P}$ maps the sigma-algebra $\mathcal{F}$ of events into $[0,1]$. Its probability axioms are nonnegativity, normalization $\mathbb{P}(\Omega )=1$, and countable additivity: for every pairwise disjoint sequence of events $A_1,A_2,\dots$,The sample space is $\Omega$, and $\mathcal{F}$ specifies which subsets are events. Requiring countable additivity, rather than only its finite version, is part of the probability space definition.

The probability axioms first give $\mathbb{P}(\varnothing )=0$: apply countable additivity to $\Omega ,\varnothing ,\varnothing ,\dots$ and use normalization and nonnegativity. If $A\subseteq B$, then $B=A\dot{\cup }(B\setminus A)$ is a disjoint union of events. Finite additivity, as a special case of countable additivity, givesThus a probability measure is monotone with respect to set inclusion. The difference event is measurable because the events belong to a sigma-algebra.

By the even probability density of the standard normal distribution,The integral is finite. Equivalently, $|Z|$ has the half-normal distribution with unit scale.

A particular solution of the linear recurrence is $-n-1$, while its homogeneous solution is $C{2}^n$. The initial value gives $C-1=1$, soSubstitution verifies $u_{n+1}-2u_n=n$, and the recurrence plus $u_0$ determines all later terms uniquely.

The characteristic polynomial is $r^2-3r+2=(r-1)(r-2)$. Therefore $u_n=A+B{2}^n$. The initial values give $A+B=1$ and $A+2B=0$, yielding $A=2$, $B=-1$. HenceThe two constants are fixed by the two initial conditions of this second-order linear recurrence.