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

The original cover identifies the examination as 9 September 2015.^[ref]

The image of a function $f:A\to B$ isThe function is surjective, or onto, exactly when every $b\in B$ equals $f(a)$ for at least one $a\in A$, equivalently $f(A)=B$. It is injective, or one-to-one, exactly whenThus surjectivity concerns whether the entire codomain is reached; injectivity concerns whether distinct inputs have distinct outputs.

Since $x^2+1\ge 2|x|$, the image of a function is contained in $[-1/2,1/2]$. Both endpoints occur, at $x=-1$ and $x=1$. By continuity and the intermediate value theorem applied on $[-1,1]$, every intermediate value occurs too. HenceIt is not surjective onto $\mathbb{R}$ because, for example, $1$ is not attained. It is not injective because $f(2)=f(1/2)=2/5$ although $2\ne 1/2$.

If $0\le x<y$, then $\sqrt{x}<\sqrt{y}$ and $x<y$, so $\sqrt{x}+x<\sqrt{y}+y$. Thus the function is strictly increasing on its domain and is injective. Its values are nonnegative, so it is not surjective onto $\mathbb{R}$:If ${\mathbb{R}}_{+}$ means $(0,\infty )$ its image of a function is $(0,\infty )$; if it includes zero its image of a function is $[0,\infty )$. Indeed, for any $u>0$, set $t=(\sqrt{1+4u}-1)/2>0$ and $x=t^2$; then $\sqrt{x}+x=t+t^2=u$. This convention does not change the classification.

With the convention $\mathbb{N}=\{0,1,2,\dots \}$, the even inputs $2j$ map to $j$ for $j\ge 0$, while the odd inputs $2j+1$ map to $-(j+1)$ for $j\ge 0$. These two images of a function are disjoint and together equal $\mathbb{Z}$. Within either class there are no repeated outputs. More explicitly the inverse function isConsequently $f$ is both injective and surjective, hence a bijection. If instead $\mathbb{N}=\{1,2,\dots \}$, the input zero is absent: $f$ remains injective but its image of a function is $\mathbb{Z}\setminus \{0\}$, so it is not onto. The printed paper does not specify this convention; the zero-based convention gives the apparent intended bijection.

Take every complement of a set relative to $\mathcal{U}$. By set difference, De Morgan's laws, and distribution of set intersection over set union,Here the middle term is the empty set, since a set and its complement of a set are disjoint.

Use set difference, associativity of set intersection, and De Morgan's laws:

The commutativity and associativity of set intersection giveEquivalently, part (ii) reduces both sides to removal of the same set union $B\cup C=C\cup B$.

For every set $S$, the definition of a power set givesEquality by identical membership therefore provesThe essential observation is that being a subset of a set intersection means being a subset of both factors.

First suppose the sets are finite, with cardinalities $a=|A|\ge 2$ and $b=|B|\ge 2$. The power set and Cartesian product counting rules giveSince $ab-a-b=(a-1)(b-1)-1\ge 0$, the desired inequality follows.

The power-set product cardinality inequality also has an injection proof that does not assume finiteness. Choose distinct $a_0,a_1\in A$ and distinct $b_0,b_1\in B$. For $S\subseteq A$ and $T\subseteq B$, define the subset of $A\times B$These three encoding regions are disjoint. The row with second coordinate $b_0$ recovers $S$; the column with first coordinate $a_0$ and second coordinate different from $b_0$ recovers $T\setminus \{b_0\}$; the extra position $(a_1,b_1)$ records whether $b_0\in T$. Thus $\Phi$ is injective, proving for arbitrary setsEncoding by $S\times T$ alone would fail: all pairs with either factor empty would have the same output.

Let $x_i$ be the number of objects in box $i$. The arrangements correspond exactly to nonnegative integer solutions of $x_1+\cdots +x_k=n$. By stars and bars, place $n$ stars and $k-1$ separating bars in a row. The number of stars between consecutive bars records the occupancy of each distinguishable box, with adjacent bars allowing an empty box. Choosing the bar positions gives

Put one object into each box first. The remaining $n-k$ objects can be distributed without restrictions, so stars and bars givesEquivalently, the substitution $u_i=x_i-1$ gives a bijection between positive integer solutions of ${\sum }_i{x}_i=n$ and nonnegative integer solutions of ${\sum }_i{u}_i=n-k$.

Use mathematical induction. For $n=1$, the left side is $2^0=1=2^1-1$. If the identity holds at $n$, thenThe base case and induction step establish the geometric series identity

For the base case $n=2$, $1+1/\sqrt{2}>\sqrt{2}$, since multiplying by $\sqrt{2}$ reduces this to $\sqrt{2}+1>2$. Suppose the claimed inequality holds for some $n\ge 2$. The identitythen givesThus mathematical induction proves

The initial values of the two sequences agree: $c_0=d_0=1$ and $c_1=-1+c_0=0=d_1$. For $n\ge 2$, use the first-order recurrence relation at $n$ and $n-1$:Therefore $c_n$ satisfies exactly the same derangement recurrence as $d_n$. By strong induction, equality of the preceding two terms implies equality of the next term. ConsequentlyThe first-order recurrence relation therefore also counts derangements.

For a binary relation $R\subseteq A\times A$, reflexivity means $aRa$ for every $a\in A$; a symmetric relation satisfies $aRb\Rightarrow bRa$ for every $a,b\in A$; an antisymmetric relation satisfies $(aRb\text{ and }bRa)\Rightarrow a=b$ for every $a,b\in A$; transitivity means $(aRb\text{ and }bRc)\Rightarrow aRc$ for every $a,b,c\in A$; an irreflexive relation satisfies $\neg (aRa)$ for every $a\in A$. In particular, failure of reflexivity means at least one missing diagonal pair, whereas irreflexivity requires every diagonal pair to be missing.

There are $n^2$ possible ordered pairs and hence $2^{n^2}$ binary relations. A reflexive relation must contain the $n$ diagonal pairs, while its remaining $n^2-n$ pairs are unrestricted. Subtracting the reflexive relations givesbinary relations that are not reflexive.

A symmetric relation has $n$ independent choices on the diagonal. For each of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ unordered pairs $\{a,b\}$ of distinct elements, either both ordered pairs are included or neither is. Thus there are $2^{n+\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$ symmetric relations, so the requested number is

For each unordered pair $\{a,b\}$ with $a\ne b$, antisymmetry allows three choices: neither direction, only $(a,b)$, or only $(b,a)$. This contributes $3^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$. The diagonal is unrestricted by antisymmetry, but being not irreflexive requires a nonempty subset of the $n$ diagonal pairs. There are $2^n-1$ such choices. HenceThis allows some diagonal pairs to be absent; “not irreflexive” does not require a reflexive relation.

Because $T$ is positive, the definition of big O notation becomesHere $C$ and $n_0$ are fixed independently of $n$.

We prove the stronger bound $T(n)\le 2n^2$ for every $n\ge 1$ by strong induction. The initial case is $T(1)=1\le 2$. For $n\ge 2$, put $m=\lfloor n/2\rfloor$. Then $1\le m<n$, so the induction hypothesis and the defining recurrence relation giveThusThe recurrence relation must be read as applying for $n\ge 2$; applying it at $n=1$ would invoke $T(0)$ outside the printed domain. No value of $T(0)$ is needed.

By modular arithmetic, $a_1-b_1=nu$ and $a_2-b_2=nv$ for some integers $u,v$. Adding givesSince $u+v$ is an integer, this proves

Using $a_i=b_i+n{u}_i$ with integers $u_i$,The quantity in parentheses is an integer, so the divisibility criterion for modular arithmetic gives

By Euclidean division, write $a=qn+r$ and $b=sn+t$, with integers $q,s$ and $0\le r,t<n$. The hypothesis is $a\equiv b(\mathrm{mod}n)$. Apply the addition rule from part (b)(i) with $-qn\equiv -sn\equiv 0(\mathrm{mod}n)$ to obtainTherefore $n\mid r-t$. But $-n<r-t<n$, and the only multiple of $n$ in that interval is zero. Henceso the two remainders agree.

The decimal expansion is $a={\sum }_{i=0}^m{a}_{i}10^i$. Since $10\equiv 1(\mathrm{mod}3)$, repeated use of the multiplication rule in part (b)(ii) gives $10^i\equiv 1(\mathrm{mod}3)$ for every $i\ge 0$. Repeated use of the addition rule in part (b)(i) now givesIf $3\mid a$, the left side is congruent to zero, whenceThis is the decimal digit-sum divisibility test for three, derived directly from modular arithmetic.

Set $k=\lfloor x\rfloor$. The definition of the floor function gives $k\le x<k+1$. Adding the integer $m$ yieldsSince $k+m$ is an integer, it is exactly the floor of $x+m$. Thus

Put $k=\lfloor y^{1/n}\rfloor$. Because $y>0$, $k$ is a nonnegative integer, andThe function $t\mapsto t^n$ is strictly increasing for $t\ge 0$, so $k^n\le y<(k+1{)}^n$. Both powers are integers. Taking the floor function therefore givesTaking nonnegative $n$th roots now gives $k\le \lfloor y{\rfloor }^{1/n}<k+1$. ConsequentlyThe argument also covers $0<y<1$, when both outer floors are zero.

By the fundamental theorem of calculus,

For the composite trapezoidal rule, the mesh width is $h=1/N$ and the nodes are $x_n=n/N$. The endpoint weights are halves and the interior weights are ones, soThis formula is an approximation to the definite integral, not an exact equality with it for finite $N$.

Let $S_N=N^{-3}{\sum }_{n=1}^N{n}^2$. The expression in part (ii) givesBecause $3x^2$ is continuous on $[0,1]$, the composite trapezoidal rule converges to its definite integral, which is $1$ by part (i). In fact its standard composite trapezoidal error bound is $|T_N-1|\le 1/(2N^2)$, since $f^{\prime \prime }=6$. Therefore

Taking the partial derivatives of the parabolic coordinates transformation, holding the other coordinate fixed each time, givesThus its Jacobian matrix is $J=\left(\begin{array}{cc}t& s\\ -s& t\end{array}\right)$.

The determinant of the Jacobian matrix is $s^2+t^2$. Wherever $(s,t)\ne (0,0)$, the inverse function theorem permits a local inverse of the parabolic coordinates transformation, andReading off its entries givesThese are local formulas on a chosen branch: $(s,t)$ and $(-s,-t)$ have the same image, and at the origin the Jacobian matrix is singular, so this inverse-derivative formula does not apply there.

Apply the multivariable chain rule to a differentiable function $f(s,t)$ on the chosen local branch of the parabolic coordinates:Substituting part (ii) gives

For $y=1+x^2$, the derivatives are $y^{\prime }=2x$ and $y^{\prime \prime }=2$. Its endpoint values are $y(0)=1$ and $y(2)=5$, so it satisfies both the ordinary differential equation and the boundary conditions. Moreover any solution of $y^{\prime \prime }=2$ has the form $x^2+Ax+B$; the boundary conditions force $B=1$ and $A=0$. Thus the unique solution of the boundary value problem is

The endpoint boundary conditions areThe finite difference equation can be written $y_{n+1}-2y_n+y_{n-1}=2h^2$. Set $d_n=y_n-y_{n-1}$. Then $d_{n+1}-d_n=2h^2$, so $d_n=d_1+2h^2(n-1)$. Summing from $1$ to $n$ givesUsing $y_N=5$ and $h=2/N$ yields $N{d}_1=4-h^{2}N(N-1)=4/N$, hence $d_1=4/N^2=h^2$. ThereforeThis also covers $N=1$, where there are no interior equations. Uniqueness follows because the difference of two solutions has zero second finite difference, hence is linear in $n$, and vanishes at both endpoints. This is an exact finite difference solution for constant second derivative: the method is exact at the nodes here because the centered second finite difference differentiates this quadratic polynomial exactly.

The characteristic equation of the constant-coefficient linear ordinary differential equation iswhose roots of a polynomial are $r=-1\pm i/2$. Taking real and imaginary parts of the corresponding exponential functions gives the real general solution

For a particular solution, try $y_p=a\sin x+b\cos x$. Substitution givesMatching coefficients requires $a-8b=1$ and $8a+b=8$, so $a=1$ and $b=0$. Adding the homogeneous solution from part (i), the general solution is

Put $a=\pi /2$. Substituting $x=-a$ and $x=a$ into part (ii), using $\cos (\pi /4)=\sin (\pi /4)=1/\sqrt{2}$, givesThus $A-B=\sqrt{2}(1+e^{-a})$ and $A+B=\sqrt{2}(1-e^a)$. Solving these two linear equations givesConsequently the solution of the boundary value problem isThe two independent boundary conditions determine $A,B$ uniquely.

Since $x>-1$, divide by $x+1$ to obtain the first-order linear ordinary differential equationAn integrating factor is $\mu (x)=e^{-3\log (x+1)}=(x+1{)}^{-3}$. Multiplication by this factor givesAfter integration, $(x+1{)}^{-3}y=\frac{1}{2}(x+1{)}^2+C$, so

Let $g_1=x^2+y^2+z^2-4$ and $g_2=(x-3{)}^2+y^2+z^2-4$. Subtracting the two constraint equations gives $-6x+9=0$, hence $x=3/2$ and $y^2+z^2=7/4$. The feasible set is therefore a circle.

For Lagrange multipliers $\lambda ,\mu$, the stationarity equation $\nabla f=\lambda \nabla g_1+\mu \nabla g_2$ becomesAt $x=3/2$, the first equation gives $\lambda =\mu$. The second ensures $\lambda +\mu \ne 0$ and $y\ne 0$, so the third gives $z=0$. The constraints then force $y=\pm \sqrt{7}/2$. Both points do satisfy the multiplier equations, taking $\lambda =\mu =1/(4y)$.

There are no missing singular constraint points: on the feasible circle, the two constraint gradients $(3,2y,2z)$ and $(-3,2y,2z)$ are linearly independent, since $y^2+z^2=7/4>0$. Thus the complete list of constrained critical points and critical values isThe bound $|y|\le \sqrt{7}/2$ on the feasible circle shows that the positive value is the global maximum and the negative value is the global minimum.

A function $f:\mathbb{R}\to \mathbb{R}$ is periodic with period $\alpha >0$ whenThe period need not be the smallest positive one; for example, every positive integer multiple of a period is also a period.