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

Source paper: released examination archive, member a10100w1-3.pdf; original cover dated 2016-06-23.

We prove both set inclusions, as required by a double inclusion proof. If $x\in A\setminus (B\cup C)$, then $x\in A$ and $x\notin B\cup C$. Thus $x\notin B$ and $x\notin C$, so $x\in A\setminus B$ and $x\in A\setminus C$. This proves the forward set inclusion.

Conversely, if $x\in (A\setminus B)\cap (A\setminus C)$, then $x\in A$, $x\notin B$, and $x\notin C$. Hence $x\notin B\cup C$, giving $x\in A\setminus (B\cup C)$. Therefore

For the first set inclusion, take $x\in (A\cap B)\setminus C$. Membership in the intersection gives $x\in A$ and $x\in B$, while the set difference gives $x\notin C$. Consequently $x\in (A\setminus C)\cap (B\setminus C)$.

For the reverse set inclusion, an element of $(A\setminus C)\cap (B\setminus C)$ belongs to both $A$ and $B$ and does not belong to $C$. It therefore belongs to $(A\cap B)\setminus C$. By double inclusion proof,

Complements are relative to the same universal set $\mathcal{U}$. Suppose $A\subseteq B$ and $x\in \overline{B}$. Then $x\in \mathcal{U}$ and $x\notin B$. If $x$ belonged to $A$, the assumed set inclusion would imply $x\in B$, a contradiction. Thus $x\notin A$ and $x\in \overline{A}$, provingThere is only one set inclusion in this conclusion; a reverse inclusion is neither needed nor generally true. The request for double inclusion applies to the equalities in (i) and (ii).

Use the definition $A\oplus B=(A\setminus B)\cup (B\setminus A)$ of symmetric difference. The algebraic laws for set difference and the empty set giveand

Because $A\subseteq \mathcal{U}$, the set difference $A\setminus \mathcal{U}$ is empty and $\mathcal{U}\setminus A=\overline{A}$. Therefore the symmetric difference satisfiesThe disjoint sets $A$ and $\overline{A}$ have union $\mathcal{U}$, so

Apply symmetric difference with $C$ to both sides, then use its associativity and the identities in (b)(i):The final identity gives $A=B$. This is cancellation by applying the same operation twice.

Fix one distinguished element $a$ of the $n$-element set. Every partition of a set into $l$ blocks belongs to exactly one of two cases. If $\{a\}$ is a block, removing it leaves an $(l-1)$-block partition of a set of the other $n-1$ elements, giving $S(n-1,l-1)$ possibilities. Otherwise remove $a$ from its block; that block remains nonempty, so the result has $l$ blocks. Conversely choose any of the $S(n-1,l)$ such partitions and insert $a$ in any one of its $l$ blocks. This gives $lS(n-1,l)$ possibilities.

These cases are disjoint and exhaustive, proving the Stirling numbers of the second kind recurrenceUse $S(0,0)=1$, $S(n,0)=0$ for $n>0$, and $S(n,l)=0$ for $l>n$; these conventions include the boundary cases $n=1$ and $l=1$.

Starting from $n$ singleton blocks, a partition of a set into $n-1$ nonempty blocks has exactly one block of size two and all other blocks of size one: the sum of the block sizes exceeds the number of blocks by exactly one. Choosing that pair determines the partition uniquely. HenceThis fixed value of $k$ works for every $n\ge 2$. It is forced already by $n=2$: $S(2,1)=1$, whereas for positive $k$ the only $\left(\genfrac{}{}{0ex}{}{2}{k}\right)$ equal to one is $\left(\genfrac{}{}{0ex}{}{2}{2}\right)$.

Each of the $m$ elements of $A$ independently receives one of $n$ images in $B$. The multiplication principle therefore gives $n^m$ functions. In particular an empty set domain has exactly one function to any $B$, so here $0^0$ is interpreted as $1$; a nonempty domain has no function to an empty set codomain.

A bijection between finite sets requires equal cardinality. When $m=n$, list the elements of $A$ and choose their distinct images in $n,n-1,\dots ,1$ ways. ThusThe factorial convention $0!=1$ includes the unique bijection from the empty set to itself.

For a surjection, the nonempty fibres $f^{-1}(b)$ form a partition of a set $A$ into exactly $n$ blocks. Choose these unlabelled blocks in $S(m,n)$ ways, then assign the $n$ distinct elements of $B$ to them in $n!$ ways. ConsequentlyIt is zero when $m<n$. With $S(0,0)=1$ and $S(m,0)=0$ for $m>0$, the same formula also handles an empty set codomain.

Choose the image of a function as a $j$-element subset of $B$, then choose a surjection onto that selected image as in (iii). ThereforeThe answer is zero when $j>n$. If $j=0$, it is one for $m=0$ and zero for $m>0$, as the Stirling numbers of the second kind conventions require.

Count pairs $(M,K)$ of subsets of an $n$-element candidate set with $K\subseteq M$, $|M|=m$, and $|K|=k$. Choosing the whole team $M$ first and then the special-role players $K$ gives $\left(\genfrac{}{}{0ex}{}{n}{m}\right)\left(\genfrac{}{}{0ex}{}{m}{k}\right)$. Alternatively choose $K$ first, then choose the other $m-k$ players from the $n-k$ candidates outside $K$, giving $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\left(\genfrac{}{}{0ex}{}{n-k}{m-k}\right)$. Each construction specifies the same pair uniquely. Thus double counting proves

Using the wiki convention that paths follow the written order of the binary relations, composition of relations isSome treatments reverse the naming convention; stating it explicitly avoids ambiguity. The powers of the single relation $R$ below are the same under either convention.

A pair belongs to $R\circ R$ exactly when two successive $R$ steps connect its endpoints. The chain $a\to b\to c\to d$ has two such length-two paths, $a\to b\to c$ and $b\to c\to d$. HenceThis applies composition of relations directly; no other middle element gives a pair.

The relation powers are $R^2=\{(a,c),(b,d)\}$, $R^3=\{(a,d)\}$, and $R^i=\varnothing$ for $i\ge 4$. For $k=1$, $(a,b),(b,c)\in T$ but $(a,c)\notin T$, so transitivity fails. For $k=2$, $(a,c),(c,d)\in T$ but $(a,d)\notin T$, so it still fails.

For $k=3$, $T$ consists of every pair in which the first endpoint precedes the second in $a,b,c,d$. Composing any two such pairs again gives such a pair, so $T$ is transitive. Thus the smallest $k$ is $3$; this $T$ is the transitive closure of a relation $R$.

In the partially ordered set $(A,⪯)$, the assertion $m=\mathrm{lub}(S)$ means bothThe first condition makes $m$ an upper bound; the second makes it the least upper bound. Both conditions are necessary, and antisymmetry makes such an element unique.

Suppose $m$ is the greatest lower bound of the set $X$ of all upper bounds of $S$. Every $s\in S$ satisfies $s⪯x$ for every $x\in X$, so each such $s$ is a lower bound of $X$. Since $m$ is the greatest of those lower bounds, $s⪯m$ for every $s\in S$. Thus $m$ itself is an upper bound of $S$, meaning $m\in X$.

Also $m$, being a lower bound of $X$, satisfies $m⪯x$ for every $x\in X$. It is therefore an upper bound of $S$ below every other upper bound, which proves $m=\mathrm{lub}(S)$. The argument also covers empty $S$ or $X$ whenever the assumed greatest lower bound exists.

Put $H_n={\sum }_{k=0}^{\lfloor n/2\rfloor }\left(\genfrac{}{}{0ex}{}{n-k}{k}\right)$; the other summands in the printed sum vanish. The initial values are $H_0=1=F_1$ and $H_1=1=F_2$. For $n\ge 2$, Pascal's identity givesFor the first sum, when $n$ is even its final term is zero; otherwise its range already agrees with $H_{n-1}$. In the second sum put $j=k-1$, obtaining $\left(\genfrac{}{}{0ex}{}{n-2-j}{j}\right)$ for $0\le j\le \lfloor (n-2)/2\rfloor$. Thus both range identifications hold without negative upper arguments in a binomial coefficient.

Now strong induction gives $H_n=F_n+F_{n-1}=F_{n+1}$ from the two preceding cases and the Fibonacci recurrence. Hence

We prove the contrapositive. If $3\nmid a$, Euclidean division gives $a=3q+1$ or $a=3q+2$ for an integer $q$. Squaring gives respectively $a^2=3(3q^2+2q)+1$ or $a^2=3(3q^2+4q+1)+1$. Both have remainder $1$ upon division by $3$, so $3\nmid a^2$. Taking the contrapositive yields $3\mid a^2\Rightarrow 3\mid a$.

For a proof by contradiction, suppose $\sqrt{3}=a/b$ for positive integers $a,b$ in lowest terms, so $\gcd (a,b)=1$. Squaring gives $a^2=3b^2$, and part (a) implies $3\mid a$. Write $a=3c$; then $9c^2=3b^2$, hence $b^2=3c^2$, and part (a) again implies $3\mid b$. This contradicts the coprimality of $a,b$. Therefore $\sqrt{3}$ is an irrational number.

The fifty disjoint sets $\{1,100\},\{2,99\},\dots ,\{50,51\}$ form a partition of a set $\{1,\dots ,100\}$. If a chosen subset met each pair at most once, it would contain at most fifty elements. The pigeonhole principle therefore forces a $51$-element subset to contain both elements of at least one pair. Those two distinct elements sum to $101$.

Assume $n\ge 1$ and list the elements of $X$ as $a_1,\dots ,a_n$. Define the partial sums $s_j=a_1+\cdots +a_j$ for $1\le j\le n$. If one is divisible by $n$, its corresponding nonempty prefix is a suitable $Y$.

Otherwise the $n$ partial sums have remainders in the $n-1$ nonzero residue classes. The pigeonhole principle gives $i<j$ with $s_i\equiv s_j(\mathrm{mod}n)$. Thus $s_j-s_i=a_{i+1}+\cdots +a_j$ is divisible by $n$, giving a nonempty subset $Y=\{a_{i+1},\dots ,a_j\}$.

Therefore a nonempty $Y$ exists. This strengthens the literal assertion, which would otherwise allow the trivial empty set with sum zero.

Since $h(n)=\max \{f(n),g(n)\}$, both $f(n)\le h(n)$ and $g(n)\le h(n)$. Therefore $f(n)+g(n)\le 2h(n)$ for every positive $n$. The definition of big O notation is satisfied with constant $2$ and threshold $1$. True: $f+g=O(h)$.

Positivity gives $\max \{f(n),g(n)\}\le f(n)+g(n)$. Thus $h(n)\le f(n)+g(n)$ for every positive $n$, meeting big O notation with constant $1$ and threshold $1$. True: $h=O(f+g)$.

Take $f(n)=g(n)=n^2$, so $h(n)=n^2$ but $(f\circ g)(n)=n^4$. The ratio $(f\circ g)(n)/h(n)=n^2$ is unbounded, precluding any eventual constant upper bound in big O notation. False: in general $f\circ g\ne O(h)$. This is a counterexample involving function composition, not pointwise addition.

For each fixed positive integer $k$, part (i) gives $(f(n)+g(n){)}^k\le (2h(n){)}^k=2^{k}h(n{)}^k$. This meets big O notation with constant $2^k$ and threshold $1$. True: $(f+g{)}^k=O(h^k)$ for fixed $k$. The constant may depend on $k$; no claim uniform in a varying $k$ is required.

Prove the explicit bound $n!\le 2^{n^2}$ by mathematical induction. At $n=1$, $1\le 2$. For the step, note that $n+1\le 2^n$ for $n\ge 1$: this auxiliary inequality has base $2=2$ and follows at the next index from $n+2\le 2(n+1)$. Hence, using the induction hypothesis,Thus $n!=O((2^n{)}^n)$, with constant $1$ and threshold $1$ in big O notation.

We prove the stronger explicit bound $n!\le n^n/2^{n-1}$ by mathematical induction. The case $n=1$ is equality. The binomial theorem gives $(1+1/n{)}^n\ge 1+n/n=2$, so $(n+1{)}^n\ge 2n^n$. Consequently the induction hypothesis yieldsTherefore $n!=O(n^n/2^n)$, with constant $2$ and threshold $1$.

The second bound is asymptotically tighter. Using $n\le 2^n$,Thus its bounding function is negligible relative to the first in little o notation; this compares the bounds without needing Stirling's formula.

Use partial fraction decomposition:Integrating each term gives the antiderivativeThis holds on any interval avoiding $-2,0,2$; the constant may differ between these intervals. Differentiation of the logarithm recovers $1/[4(x^2-4)]$, providing a direct check.

The characteristic equation of a constant-coefficient differential equation here is $r^2-3r+2=(r-1)(r-2)=0$. Its homogeneous solution is $C_1{e}^x+C_2{e}^{2x}$. Because the forcing $e^x$ is already a homogeneous mode, the method of undetermined coefficients requires $y_p=Ax{e}^x$ rather than $A{e}^x$.

Here $y_p^{\prime }=A(x+1)e^x$ and $y_p^{\prime \prime }=A(x+2)e^x$, so $y_p^{\prime \prime }-3y_p^{\prime }+2y_p=-A{e}^x$. Thus $A=-1$, and the general solution is

The gradient vanishes when $4x+3y-1=0$ and $3x+2y-1=0$. Subtracting these equations gives $x+y=0$, so the unique critical point is $\boxed{(x,y)=(1,-1)}$, with $f(1,-1)=0$.

The Hessian matrix isIt is indefinite, so the critical point is a saddle point. Explicitly, around that point the change is exactly $2u^2+3uv+v^2$: it is positive for $v=0,u\ne 0$ and negative for $v=-3u/2,u\ne 0$. Thus arbitrarily close points have both larger and smaller values.

On the unit circle the constraint gradient $(2x,2y)$ never vanishes. The Lagrange multiplier equations areA nonzero solution of the first two equations requiresso $\lambda =9/2$ or $\lambda =-1/2$. Multiplying the first equation by $x$, the second by $y$, and adding shows $2f=2\lambda (x^2+y^2)=2\lambda$. Thus each candidate value of $f$ equals its multiplier.

For $\lambda =9/2$, $y=-x/3$, giving $(x,y)=\pm (3,-1)/\sqrt{10}$. For $\lambda =-1/2$, $y=3x$, giving $(x,y)=\pm (1,3)/\sqrt{10}$. Since a continuous function attains its extrema on the compact set given by the unit circle and these exhaust the Lagrange multiplier candidates,Each $\pm$ changes both coordinates together.

The chain rule gives $\frac{d}{dx}\cos (\mu x)=-\mu \sin (\mu x)$. Dividing by the nonzero constant $-\mu$ gives the antiderivative

Apply integration by parts with $u=x$ and $dv=\sin (\mu x)dx$. Part (i) gives $v=-\cos (\mu x)/\mu$, so

For the Fourier sine series write $u_0(x)={\sum }_{n\ge 1}{b}_n\sin (n\pi x/L)$. Orthogonality of trigonometric functions givesIn the second half of the integral put $z=L-x$; then $u_0(L-z)=\rho z$ and $\sin [n\pi (L-z)/L]=(-1{)}^{n+1}\sin (n\pi z/L)$. HenceEvery even coefficient is zero. For odd $n$, part (a) or the supplied integral yieldsPutting $n=2m+1$ therefore givesThis is the Fourier sine series of a symmetric tent. The absolute values of its terms are uniformly bounded by a summable sequence, giving absolute convergence and uniform convergence; the piecewise smooth odd extension and the Dirichlet convergence theorem for Fourier series identify its value with the continuous $u_0$, including the zero endpoints and the peak.

The printed lower limit $m=1$ is an error. The original PDF visibly has this lower limit. It omits the nonzero fundamental coefficient $F_0=4L\rho /{\pi }^2$. In particular, the printed series equals $u_0(x)-F_0\sin (\pi x/L)$, rather than $u_0(x)$. At $x=L/2$ it gives $L\rho /2-4L\rho /{\pi }^2$ instead of $L\rho /2$. The corrected lower limit is displayed explicitly above.

Apply separation of variables to each mode of the damped wave equation $u_{tt}+2k^2{u}_t=c^2{u}_{xx}$, assuming $L,c>0$. The spatial ordinary differential equation is $X_n^{\prime \prime }+({\lambda }_n/c{)}^2{X}_n=0$. Its general solution is $C\sin ({\lambda }_{n}x/c)+D\cos ({\lambda }_{n}x/c)$. The boundary condition at $0$ gives $D=0$; a nonzero mode at $L$ requiresOnly odd $n=2m+1$ occur in the initial Fourier sine series. Put ${\omega }_m=(2m+1)\pi c/L$ and $d_m=\sqrt{k^4-{\omega }_m^2}$. The temporal equation $T_m^{\prime \prime }+2k^2{T}_m^{\prime }+{\omega }_m^2{T}_m=0$ has roots $-k^2\pm d_m$. DefineFor distinct roots, let the full amplitude be $q_m(t)=A_m{e}^{-{\alpha }_{m}t}+B_m{e}^{-{\beta }_{m}t}$. The initial displacement and zero initial velocity impose $A_m+B_m=F_m$ and ${\alpha }_m{A}_m+{\beta }_m{B}_m=0$. Solving givesThus the physically consistent superposition isFor ${\omega }_m<k^2$ there is overdamping, with two real decaying exponentials. For ${\omega }_m>k^2$ there is underdamping; set ${\nu }_m=\sqrt{{\omega }_m^2-k^4}$; the equivalent real expression isAt critical damping, the repeated-root case ${\omega }_m=k^2$, take the limit, giving $q_m(t)=F_m(1+k^{2}t)e^{-k^{2}t}$. These formulas all satisfy $q_m(0)=F_m$ and $q_m^{\prime }(0)=0$.

Three source qualifications matter. First, the sum must start at $m=0$, for the same reason as in (b). Second, the printed $X(x)=u_0(x)$ cannot hold for a single separated mode: the tent has $X^{\prime \prime }=0$ on each open linear segment but $X\ne 0$, contradicting $X^{\prime \prime }=-({\lambda }_n/c{)}^{2}X$ for positive ${\lambda }_n$, and its peak is not twice differentiable. Separation applies mode by mode, with the initial tent recovered by superposition. Third, no finite “large” $k$ makes every mode overdamped, because ${\omega }_m\to \infty$. The two-exponential expression permits complex conjugate roots, while a repeated root requires its displayed limiting form. The tent initial data are naturally interpreted through the convergent modal solution, rather than as a single smooth separated product.

Under the hypotheses of Taylor's theorem with Lagrange remainder, for example $f\in C^{n+1}$ on an interval containing $x$ and $x+h$, there is a point $\xi$ between them such thatThe Lagrange remainder makes this an exact equality, rather than just a truncated Taylor polynomial. For $h=0$ the equality is immediate.

Set $h=(b-a)/n$ and $x_i=a+ih$. Summing the areas of the $n$ endpoint trapezia gives the composite trapezoidal ruleEvery interior value is shared by two adjacent strips; the two endpoint values occur only once with half weight. Evenness of $n$ is not needed for this rule.

For the same uniform grid and even $n$, the composite Simpson's rule integrates a quadratic interpolant over each successive pair of strips:The weights are $1,4,2,4,\dots ,2,4,1$, which explains the even number of strips.