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

Source paper: released examination archive, member 2018/T/a10100w1.pdf. The cover identifies the regular Preliminary Examination in Computer Science, Trinity Term 2019, Thursday 27 June, 14:30–17:30. The archive directory does not determine the sitting. All nine questions are covered, including every printed Roman subpart.

Questions 1–3 form Discrete Mathematics, 4–6 Continuous Maths, and 7–9 Probability. The printed relation in 3(c)(ii) fails to be a partial order; that issue is treated explicitly rather than silently changing the source.

For the first set inclusion, take $x\in (A\cap B)\setminus C$. By the definitions of set intersection and set difference, $x\in A$, $x\in B$ and $x\notin C$. Consequently $x\in A\setminus C$ and $x\in B\setminus C$, so $x\in (A\setminus C)\cap (B\setminus C)$.

For the reverse set inclusion, take $x\in (A\setminus C)\cap (B\setminus C)$. Membership in the first set difference gives $x\in A$ and $x\notin C$, while membership in the second gives $x\in B$ and $x\notin C$. Thus $x\in A\cap B$ and $x\notin C$, proving $x\in (A\cap B)\setminus C$. The two inclusions establish the required equality.

The set difference $\varnothing \setminus \varnothing$ is the empty set. Its power set contains exactly one element, the empty set itself. Therefore the cardinality is $1$, not zero.

A binary relation on $A$ is any subset of the Cartesian product $A\times A$. There are $n^2$ ordered pairs, and each can independently be included or omitted. Hence the number of binary relations is $2^{n^2}$. This also gives one relation when $n=0$, namely the empty set.

The function is injective and surjective, with inverse function $f^{-1}(y)=1-y$. Equality $1-x=1-x^{\prime }$ forces $x=x^{\prime }$. For any $y\in (0,1)$, the input $x=1-y$ also lies in $(0,1)$ and satisfies $f(x)=y$. Applying the function twice returns the original input.

It is neither injective nor surjective onto $\mathbb{R}$, so it has no inverse function on the stated domain and codomain. The distinct inputs $0$ and $\pi /3$ both lie in the domain and both give zero. All values lie in $[-1,1]$, so, for example, the real number $2$ has no preimage.

It is surjective but not injective; there is no global inverse function. Noninjectivity follows fromFor surjectivity, restrict to $x<1$, whereThis restriction is a continuous function, tends to $-\infty$ as $x\to -\infty$ and to $+\infty$ as $x\to 1^{-}$. The intermediate value theorem therefore supplies a preimage for every real number. The additional branch $x>1$ destroys global injectivity but cannot destroy surjectivity.

The iterated function is $f^{(n)}(x)=\sqrt{x^2+n}$ for every positive integer $n$. The exponent here denotes repeated function composition, not an ordinary power or a derivative.

For the base case $n=1$, the formula is the definition. If it holds at $n$, thenThis proves the claim by mathematical induction, for every real input $x$.

There are six functions: the four power maps $x\mapsto x^k$ for $k=1,2,3,4$, and the two constant maps $0,1$. All calculations in this part are in the finite field ${\mathbb{Z}}_5$.

Put $e=f(1)$. Multiplicativity gives $e^2=e$, so the absence of zero divisors forces $e=0$ or $e=1$. If $e=0$, then $f(x)=f(x)f(1)=0$ for every $x$, giving only the constant-zero map.

Suppose $e=1$. For nonzero $x$, the equality $f(x)f(x^{-1})=1$ shows $f(x)\ne 0$. The nonzero elements form a cyclic group generated by $2$, in the order $1,2,4,3$. Choosing $a=f(2)$ determines every value on this group by $f(2^j)=a^j$. Each $a\in \{1,2,3,4\}$ satisfies $a^4=1$, so all four choices give consistent group homomorphisms.

Finally, $z=f(0)$ satisfies $z^2=z$ and $z=zf(x)$ for every $x$. The choice $z=0$ works for all four group maps. The choice $z=1$ forces every nonzero value to be $1$, giving one extra map, the constant-one map. Thus the count is $1+4+1=6$. The four zero-preserving possibilities are exactly the four displayed power maps. This is the special case with five elements of multiplicative self-maps of a finite field.

Use the inclusion-exclusion principle on the multiples of $6,8,11$ in $\{1,\dots ,527\}$. The pairwise least common multiples are $24,66,88$, and the triple least common multiple is $264$. Therefore the count isThe endpoint $528$ is excluded, which is why the numerators are $527$ rather than $528$.

The Fibonacci recurrence, with the supplied initial values, is $F_{n+2}=F_{n+1}+F_n$ for $n\ge 0$, with $F_0=0,F_1=1$. Two initial values are needed for this second-order linear recurrence relation.

Use $G_1=0$ and $G_{n+1}=n{G}_n+n-1$ for $n\ge 1$. Indeed,The initial value is $0!-1=0$, so the recurrence relation produces the specified factorial sequence.

Adding the Fibonacci recurrence and the identical recurrence relation for the Lucas numbers givesLinearity preserves this linear recurrence relation; the initial values come from $0+2$ and $1+1$.

Let $\varphi =(1+\sqrt{5})/2$, the golden ratio. Since ${\varphi }^2=\varphi +1$, multiplication by ${\varphi }^n$ gives ${\varphi }^{n+2}={\varphi }^{n+1}+{\varphi }^n$. Adding this recurrence relation to the one for $A_n$ yieldsThus the extra exponential term changes the initial values, but not the linear recurrence relation.

For $n=0$, the difference is $F_1^2-F_0{F}_2=1=(-1{)}^0$. Define $D_n=F_{n+1}^2-F_n{F}_{n+2}$. The Fibonacci recurrence givesThe inductive step therefore changes $(-1{)}^n$ into $(-1{)}^{n+1}$. By mathematical induction, $D_n=(-1{)}^n$ for all $n\ge 0$, the requested form of Cassini's identity.

Induct on $n$, with the claim quantified over every $m\ge n$. At $n=0$,Suppose the identity holds for a fixed $n$ and every $m\ge n$. For $m\ge n+1$, the Fibonacci recurrence givesApplying the induction hypothesis with $m-1\ge n$ is legitimate. This proves $F_m{F}_{n+1}-F_n{F}_{m+1}=(-1{)}^n{F}_{m-n}$ throughout its domain, a case of the Fibonacci determinant identity.

A derangement of a finite set $A$ is a permutation $\sigma :A\to A$ with no fixed point: $\sigma (a)\ne a$ for every $a\in A$. Thus every element is moved, although the permutation remains a bijection.

The initial values are $d_1=0$ and $d_2=1$: one element cannot move, while two elements must be swapped.

For $n\ge 3$, fix one distinguished element, called $n$, and choose its image $j\ne n$, in $n-1$ ways. If $n,j$ form a two-cycle, deleting them leaves an arbitrary derangement on the other $n-2$ elements, giving $d_{n-2}$ choices.

Otherwise the permutation cycle containing $n$ has length at least three. Remove $n$ from that cycle, joining its predecessor directly to $j$. No fixed point is created because the predecessor is not $j$. This gives a derangement on $n-1$ elements. Conversely, any such derangement uniquely recovers the original one by inserting $n$ immediately before $j$ in its cycle. This case contributes $d_{n-1}$ choices for each $j$.

The two cases are disjoint and exhaustive, so the derangement recurrence is

An upper bound of $S$ is an element $u\in A$ with $s⪯u$ for every $s\in S$. It need not belong to $S$. A maximum, or greatest element, is an $m\in S$ with that same property. A least upper bound is an upper bound $\ell \in A$ satisfying $\ell ⪯u$ for every upper bound $u$.

A maximum belongs to $S$; a least upper bound need not. In a partially ordered set, an existing maximum is automatically the least upper bound, and the antisymmetric relation condition makes each unique.

Put $J=\{k\in \mathbb{N}:k\le 100\}$, avoiding any dependence on whether the convention includes $0$ among the natural numbers. Under set inclusion, the results are

The set union of all three-element subsets of $\mathbb{N}$ is $\mathbb{N}$. An upper bound for $S_1$ under set inclusion would have to contain this entire infinite set, whereas members of $A$ are finite. Thus $S_1$ has no upper bound and hence no maximum or least upper bound.

For $S_2$, every member is a subset of the finite set $J$, and $J$ itself belongs to $S_2$, making it both maximum and least upper bound. The union of the three-element subsets of $J$ is again $J$, so $J$ is the least upper bound of $S_1\cap S_2$. It is not a member of that family, and no three-element member contains all the others, so there is no maximum.

The displayed relation is not a partial order on the printed $A$. Since the empty set belongs to $A$, vacuous truth makeshold for every finite $T$, including nonempty $T$. This violates the defining condition of an antisymmetric relation. It also violates transitivity: $\{2\}{⪯}_2\varnothing {⪯}_2\{1\}$ holds, but $\{2\}{⋠}_2\{1\}$. Consequently the usual unique-maximum and unique-least upper bound terminology for a partially ordered set does not apply as claimed.

The available inputs still determine what happens if one applies the formulas in (b) literally to this relation:

For $S_1$, no nonempty finite set can lie above all triples of arbitrarily large numbers, while $\varnothing$ does so vacuously. Thus $\varnothing$ is its sole literal upper bound, but is not a member of $S_1$. For each of the two bounded families, the literal upper bounds are $\varnothing$ and all nonempty finite sets whose elements are at least $100$. Among these, exactly $\varnothing$ and $\{100\}$ lie below every such upper bound. Both belong to $S_2$, but neither belongs to its three-element subfamily.

For comparison, a natural correction is to retain the given rule for nonempty sets and declare $\varnothing$ to be a bottom element: no nonempty set is then below $\varnothing$. Under this explicitly corrected partial order, $S_1$ has neither a maximum nor a least upper bound; $S_2$ has maximum and least upper bound $\{100\}$; and $S_1\cap S_2$ has no maximum but has least upper bound $\{100\}$. A nonempty upper bound must have every element at least as large as every element of the bounded family. These corrected answers are conditional on the stated repair, not answers obtained by silently excluding the empty set from the source.

False. For $n\ge 3$, every factor from $3$ through $n$ is at least $3$, soNo fixed multiple of $2^n$ eventually bounds the factorial, contradicting the definition of Big O notation. No use of Stirling's approximation is required.

True. For every $n\ge 4$, $2\le \sqrt{n}$, and raising both nonnegative sides to the $n$th power givesThus the Big O notation condition holds with constant $C=1$ and threshold $n_0=4$.

False. It suffices to find a subsequence along which the ratio is unbounded. Set $n=4m$. The last $3m$ factors of $(4m)!$ are at least $m$, while the first $m$ factors have product at least one. HenceThis contradicts the eventual uniform bound required by Big O notation. The proof is an elementary factorial comparison, independent of Stirling's approximation.

Let $h=(b-a)/n$, $x_j=a+jh$, and $m_j=a+(j+\frac{1}{2})h$. The composite midpoint rule and composite trapezoidal rule areFor composite Simpson's rule with $2n$ strips, the spacing is $h/2$. Its odd-indexed nodes are the $m_j$ and its even interior nodes are the $x_j$. ConsequentlyThis is an identity between the quadrature rules, not an approximation involving an omitted quadrature error.

Four differentiations giveFor $0<x<1$, the fifth derivative is negative, so the fourth derivative is strictly decreasing. Since $f^{(4)}(1)=0$, strict decrease towards that endpoint implies $f^{(4)}(x)>0$ for $x<1$. On the closed interval, $0\le f^{(4)}(x)\le 1$, with the maximum at $0$ and minimum at $1$.

Take $n$ to be a positive even integer, as required by composite Simpson's rule. There are $n/2$ two-strip panels, each of width $2/n$. Applying the supplied panel bound with the global fourth-derivative minimum $0$ and maximum $1$, and summing, givesHere $E_n$ is the nonnegative absolute error. In this example Simpson's rule overestimates the integral, so $E_n=S_n-I$. Each panel has that same sign because its fourth derivative is nonnegative; cancellation is not being assumed.^[ref]

On the panel $[2j/n,2(j+1)/n]$, the maximum fourth derivative is at the left endpoint because it is decreasing. ThusThe geometric series and the sum of consecutive integers giveSubstitution provesFor $n>2$, at least one panel's maximum is smaller than the global maximum $1$, so this bound is strictly tighter than the global bound. For $n=2$, the two bounds coincide.

The global bound requiresSince the strip count must be even, the smallest count certified by this bound is $n=88$.

For the tighter bound, use the bisection method on the continuous extension $B(x)-10^{-10}$ for $x\ge 2$. The initial root bracket $[2,88]$ is valid: $B(2)=1/2880>10^{-10}$, while $B(88)$ is below the global bound and hence below $10^{-10}$. To identify the smallest admissible even count, the monotonicity of $B$ can also be justified.

Put $h=2/x$ andFor $h>0$, differentiation showsThe numerator is nonnegative because $e^h-e^{-h}\ge 2h$: its difference from $2h$ starts at zero and has nonnegative derivative $e^h+e^{-h}-2$, by the arithmetic-geometric mean inequality. Thus $C^{\prime }(h)\ge 1/2$, and $C(0^{+})=e/2-1>0$. Therefore $h^{4}C(h)$ increases with $h$, so $B(x)$ is strictly decreasing with $x$. Bisection locates its unique threshold crossing; then check the neighboring even integers, retaining the strict error inequality.

For example, $B(66)\approx 1.09626\times 10^{-10}$ and $B(68)\approx 9.71694\times 10^{-11}$, so the tighter bound certifies $68$ strips. These are evaluations of the bound, not an assumption that it equals the actual quadrature error.

No: Monte Carlo integration is poorly suited to this smooth one-dimensional problem at such a tight tolerance. A sample-average Monte Carlo estimator has a standard error proportional to $N^{-1/2}$, whereas the deterministic composite Simpson's rule bound decreases as $n^{-4}$ here and already certifies the target with tens of strips. Random sampling would require vastly more function evaluations and supplies a probabilistic error statement rather than the displayed deterministic guarantee.

The first three derivatives factor asLet $a=\sqrt{10/3}$. Sign analysis of the factors givesAll displayed endpoints are excluded because a factor vanishes there; the extra zero of $f^{\prime \prime }$ at $0$ does not create a positive interval.

The extreme value theorem guarantees extrema on the closed interval. Compare its endpoints and the stationary points $0,\pm \sqrt{10/3}$:ThusThe two-point answer in each case also follows from the even function symmetry.

The Newton root-finding iteration isIt is defined when $x_k\notin \{0,\pm \sqrt{10/3}\}$. Finding an exact zero of a function is a stopping condition, rather than a reason to continue dividing.

On $I=[1,7/5]$, $f^{\prime }<0$ and $f^{\prime \prime }<0$, since $x^2<2$. Hence $|f^{\prime }|$ increases and has minimum $|f^{\prime }(1)|=14$. Alsowith equality at $x=1$. Therefore

There is a unique root $r$ in $I$: $f(1)=2>0$, $f(7/5)=-5.678464<0$, and the function is strictly decreasing. Moreover $f(6/5)=-1.382016<0$, so $r<6/5=x_0$.

It remains to justify that the iteration stays where the error estimate applies. Because $f$ is a concave function, its graph lies below each tangent line. At any $x\in [r,6/5]$, the tangent has nonpositive value $f(x)$ at $x$, negative slope, and nonnegative value at $r$. Its zero $N(x)=x-f(x)/f^{\prime }(x)$ therefore satisfiesBy mathematical induction, the Newton root-finding iteration stays in $[r,6/5]$ and decreases to some limit $L\ge r$. Continuity in $x_{k+1}-x_k=-f(x_k)/f^{\prime }(x_k)$ implies $f(L)=0$, so uniqueness gives $L=r$.

Now the supplied error bound applies at every step:This proves at least quadratic convergence, with an invariant interval and a nonvanishing derivative explicitly established.

About five steps are certified by the uniform worst-case estimate; the actual iteration reaches double-precision accuracy in about four. Put $K=15/14$. The initial enclosure gives $e_0=|x_0-r|<1/5$, and repeated squaring yieldsFor $k=4$ this is about $1.84\times 10^{-11}$, while for $k=5$ it is below $4\times 10^{-22}$. Thus five ideal-arithmetic steps push this bound well below the approximately $10^{-16}$ relative resolution of double-precision floating-point format.

The bound is conservative. Factoring $f(x)=(x^2+1)(x^4-6x^2+6)$ identifiesHigh-precision evaluation of the actual successive errors gives approximately $7.40\times 10^{-2}$, $3.56\times 10^{-3}$, $9.91\times 10^{-6}$, $7.73\times 10^{-11}$ and $4.70\times 10^{-21}$. Thus the fourth step would already exceed double-precision accuracy in exact arithmetic. In floating-point evaluation, cancellation in the residual and other roundoff errors prevent the subsequent theoretical digits from being realized.

For the vector equation, the Jacobian matrix isWrite the updated coordinates as $(X,Y)$. The second equation of the multivariable Newton iteration gives $X-Y=0$. Substituting $X=Y$ into its first linearized equation givesHence $h(x,y)=6x^5-20y^3$, and, whenever $h\ne 0$,

Starting from $(0,1)$ gives $(x_1,y_1)=(21/20,21/20)$. Every subsequent iterate remains on the diagonal, where this is exactly the scalar Newton root-finding iteration from (b). The value $f(21/20)>0$, so $21/20<r$.

For $1\le x<r$, concavity again puts the tangent's zero at or above $r$. Alsoso $r\le N(21/20)\le N(1)=8/7<6/5$. After one scalar step the sequence therefore enters the invariant interval proved in (b). It converges to $(r,r)$ at least quadratically. If the vector error is measured in the Euclidean norm, then $\Vert (x_k,y_k)-(r,r)\Vert =\sqrt{2}|x_k-r|$, so the scalar quadratic estimate also gives a quadratic vector estimate. The initial off-diagonal step causes no difficulty because its Jacobian matrix is invertible and lands exactly on the diagonal.

Use the LagrangianThe Lagrange multiplier equations areFeasibility makes $x\ne 0$, so $\lambda =2x^2>0$. The second equation becomes $2y(8y^2+\lambda )=0$, forcing $y=0$ and then $x=\pm 1$. The constraint gradient $(2x,-2y)$ is nonzero on the feasible set, so the multiplier calculation has no missing singular feasible point.

To verify the global minimum rather than just stationarity, eliminate $x^2=1+y^2$:Equality holds exactly at $(x,y)=(1,0)$ or $(-1,0)$, with minimum value $1$.

If $\mathbf{b}=0$, the objective is zero at every feasible point, so every point of the ellipsoid is a minimizer. Suppose now $\mathbf{b}\ne 0$. A minimum cannot be interior: a sufficiently small step in direction $-\mathbf{b}$ would remain feasible and decrease the objective. The boundary is active.

Forstationarity gives $\mathbf{b}+2\lambda A\mathbf{x}=0$. A positive-definite symmetric matrix is invertible, and the minimizing sign has $\lambda >0$. Enforcing the boundary gives

For global optimality, use the inner product $⟨u,v{⟩}_A=u^{\mathsf{T}}Av$. The Cauchy-Schwarz inequality givesThe proposed point attains the negative of this bound. Thus the minimum is $-\sqrt{{\mathbf{b}}^{\mathsf{T}}{A}^{-1}\mathbf{b}}$, and equality in the Cauchy-Schwarz inequality, together with the sign and boundary conditions, makes this minimizer unique when $\mathbf{b}\ne 0$.

Use a column gradient. By the multivariable chain rule,The scalar coefficients multiply the constant vectors ${\mathbf{a}}_i$. In particular $f^{\prime }(t)=-t{e}^{-t^2/2}$, although explicit differentiation of $f$ is not required.