# Part IA, 2019

### Jump to course

Paper 1, Section I, E

commentState the Bolzano-Weierstrass theorem.

Let $\left(a_{n}\right)$ be a sequence of non-zero real numbers. Which of the following conditions is sufficient to ensure that $\left(1 / a_{n}\right)$ converges? Give a proof or counter-example as appropriate.

(i) $a_{n} \rightarrow \ell$ for some real number $\ell$.

(ii) $a_{n} \rightarrow \ell$ for some non-zero real number $\ell$.

(iii) $\left(a_{n}\right)$ has no convergent subsequence.

Paper 1, Section I, F

commentLet $\sum_{n=1}^{\infty} a_{n} x^{n}$ be a real power series that diverges for at least one value of $x$. Show that there exists a non-negative real number $R$ such that $\sum_{n=1}^{\infty} a_{n} x^{n}$ converges absolutely whenever $|x|<R$ and diverges whenever $|x|>R$.

Find, with justification, such a number $R$ for each of the following real power series:

(i) $\sum_{n=1}^{\infty} \frac{x^{n}}{3^{n}}$;

(ii) $\sum_{n=1}^{\infty} x^{n}\left(1+\frac{1}{n}\right)^{n}$.

Paper 1, Section II, D

commentState and prove the Intermediate Value Theorem.

State the Mean Value Theorem.

Suppose that the function $g$ is differentiable everywhere in some open interval containing $[a, b]$, and that $g^{\prime}(a)<k<g^{\prime}(b)$. By considering the functions $h$ and $f$ defined by

$h(x)=\frac{g(x)-g(a)}{x-a}(a<x \leqslant b), \quad h(a)=g^{\prime}(a)$

and

$f(x)=\frac{g(b)-g(x)}{b-x}(a \leqslant x<b), \quad f(b)=g^{\prime}(b),$

or otherwise, show that there is a subinterval $[\alpha, \beta] \subseteq[a, b]$ such that

$\frac{g(\beta)-g(\alpha)}{\beta-\alpha}=k$

Deduce that there exists $c \in(a, b)$ with $g^{\prime}(c)=k$.

Paper 1, Section II, D

commentLet $g: \mathbb{R} \rightarrow \mathbb{R}$ be a function that is continuous at at least one point $z \in \mathbb{R}$. Suppose further that $g$ satisfies

$g(x+y)=g(x)+g(y)$

for all $x, y \in \mathbb{R}$. Show that $g$ is continuous on $\mathbb{R}$.

Show that there exists a constant $c$ such that $g(x)=c x$ for all $x \in \mathbb{R}$.

Suppose that $h: \mathbb{R} \rightarrow \mathbb{R}$ is a continuous function defined on $\mathbb{R}$ and that $h$ satisfies the equation

$h(x+y)=h(x) h(y)$

for all $x, y \in \mathbb{R}$. Show that $h$ is either identically zero or everywhere positive. What is the general form for $h$ ?

Paper 1, Section II, E

commentLet $\left(a_{n}\right)$ and $\left(b_{n}\right)$ be sequences of positive real numbers. Let $s_{n}=\sum_{i=1}^{n} a_{i}$.

(a) Show that if $\sum a_{n}$ and $\sum b_{n}$ converge then so does $\sum\left(a_{n}^{2}+b_{n}^{2}\right)^{1 / 2}$.

(b) Show that if $\sum a_{n}$ converges then $\sum \sqrt{a_{n} a_{n+1}}$ converges. Is the converse true?

(c) Show that if $\sum a_{n}$ diverges then $\sum \frac{a_{n}}{s_{n}}$ diverges. Is the converse true?

$[$ For part (c), it may help to show that for any $N \in \mathbb{N}$ there exist $m \geqslant n \geqslant N$ with

$\left.\frac{a_{n+1}}{s_{n+1}}+\frac{a_{n+2}}{s_{n+2}}+\ldots+\frac{a_{m}}{s_{m}} \geqslant \frac{1}{2} .\right]$

Paper 1, Section II, F

commentLet $f:[0,1] \rightarrow \mathbb{R}$ be a bounded function. Define the upper and lower integrals of $f$. What does it mean to say that $f$ is Riemann integrable? If $f$ is Riemann integrable, what is the Riemann integral $\int_{0}^{1} f(x) d x$ ?

Which of the following functions $f:[0,1] \rightarrow \mathbb{R}$ are Riemann integrable? For those that are Riemann integrable, find $\int_{0}^{1} f(x) d x$. Justify your answers.

(i) $f(x)= \begin{cases}1 & \text { if } x \in \mathbb{Q} \\ 0 & \text { if } x \notin \mathbb{Q}\end{cases}$

(ii) $f(x)=\left\{\begin{array}{ll}1 & \text { if } x \in A \\ 0 & \text { if } x \notin A\end{array}\right.$,

where $A=\{x \in[0,1]: x$ has a base-3 expansion containing a 1$\}$;

[Hint: You may find it helpful to note, for example, that $\frac{2}{3} \in A$ as one of the base-3 expansions of $\frac{2}{3}$ is $\left.0.1222 \ldots .\right]$

(iii) $f(x)=\left\{\begin{array}{ll}1 & \text { if } x \in B \\ 0 & \text { if } x \notin B\end{array}\right.$,

where $B=\{x \in[0,1]: x$ has a base $-3$ expansion containing infinitely many $1 \mathrm{~s}\}$.

Paper 2, Section I, $2 \mathrm{C}$

commentConsider the first order system

$\frac{d \boldsymbol{v}}{d t}-B \boldsymbol{v}=e^{\lambda t} \boldsymbol{x}$

to be solved for $\boldsymbol{v}(t)=\left(v_{1}(t), v_{2}(t), \ldots, v_{n}(t)\right) \in \mathbb{R}^{n}$, where the $n \times n$ matrix $B, \lambda \in \mathbb{R}$ and $\boldsymbol{x} \in \mathbb{R}^{n}$ are all independent of time. Show that if $\lambda$ is not an eigenvalue of $B$ then there is a solution of the form $\boldsymbol{v}(t)=e^{\lambda t} \boldsymbol{u}$, with $\boldsymbol{u}$ constant.

For $n=2$, given

$B=\left(\begin{array}{ll} 0 & 3 \\ 1 & 0 \end{array}\right) \quad \lambda=2 \quad \text { and } \boldsymbol{x}=\left(\begin{array}{l} 0 \\ 1 \end{array}\right)$

find the general solution to (1).

Paper 2, Section I, C

commentThe function $y(x)$ satisfies the inhomogeneous second-order linear differential equation

$y^{\prime \prime}-2 y^{\prime}-3 y=-16 x e^{-x}$

Find the solution that satisfies the conditions that $y(0)=1$ and $y(x)$ is bounded as $x \rightarrow \infty$.

Paper 2, Section II, $5 \mathrm{C}$

commentConsider the problem of solving

$\frac{d^{2} y}{d t^{2}}=t$

subject to the initial conditions $y(0)=\frac{d y}{d t}(0)=0$ using a discrete approach where $y$ is computed at discrete times, $y_{n}=y\left(t_{n}\right)$ where $t_{n}=n h(n=-1,0,1, \ldots, N)$ and $0<h=1 / N \ll 1 .$

(a) By using Taylor expansions around $t_{n}$, derive the centred-difference formula

$\frac{y_{n+1}-2 y_{n}+y_{n-1}}{h^{2}}=\left.\frac{d^{2} y}{d t^{2}}\right|_{t=t_{n}}+O\left(h^{\alpha}\right)$

where the value of $\alpha$ should be found.

(b) Find the general solution of $y_{n+1}-2 y_{n}+y_{n-1}=0$ and show that this is the discrete version of the corresponding general solution to $\frac{d^{2} y}{d t^{2}}=0$.

(c) The fully discretized version of the differential equation (1) is

$\frac{y_{n+1}-2 y_{n}+y_{n-1}}{h^{2}}=n h \quad \text { for } \quad n=0, \ldots, N-1$

By finding a particular solution first, write down the general solution to the difference equation (2). For the solution which satisfies the discretized initial conditions $y_{0}=0$ and $y_{-1}=y_{1}$, find the error in $y_{N}$ in terms of $h$ only.

Paper 2, Section II, $6 \mathrm{C}$

commentFind all power series solutions of the form $y=\sum_{n=0}^{\infty} a_{n} x^{n}$ to the equation

$\left(1-x^{2}\right) y^{\prime \prime}-x y^{\prime}+\lambda^{2} y=0$

for $\lambda$ a real constant. [It is sufficient to give a recurrence relationship between coefficients.]

Impose the condition $y^{\prime}(0)=0$ and determine those values of $\lambda$ for which your power series gives polynomial solutions (i.e., $a_{n}=0$ for $n$ sufficiently large). Give the values of $\lambda$ for which the corresponding polynomials have degree less than 6 , and compute these polynomials. Hence, or otherwise, find a polynomial solution of

$\left(1-x^{2}\right) y^{\prime \prime}-x y^{\prime}+y=8 x^{4}-3$

satisfying $y^{\prime}(0)=0$.

Paper 2, Section II, C

commentConsider the nonlinear system

$\begin{aligned} &\dot{x}=y-2 y^{3} \\ &\dot{y}=-x \end{aligned}$

(a) Show that $H=H(x, y)=x^{2}+y^{2}-y^{4}$ is a constant of the motion.

(b) Find all the critical points of the system and analyse their stability. Sketch the phase portrait including the special contours with value $H(x, y)=\frac{1}{4}$.

(c) Find an explicit expression for $y=y(t)$ in the solution which satisfies $(x, y)=\left(\frac{1}{2}, 0\right)$ at $t=0$. At what time does it reach the point $(x, y)=\left(\frac{1}{4},-\frac{1}{2}\right) ?$

Paper 2, Section II, C

commentTwo cups of tea at temperatures $T_{1}(t)$ and $T_{2}(t)$ cool in a room at ambient constant temperature $T_{\infty}$. Initially $T_{1}(0)=T_{2}(0)=T_{0}>T_{\infty}$.

Cup 1 has cool milk added instantaneously at $t=1$ and then hot water added at a constant rate after $t=2$ which is modelled as follows

$\frac{d T_{1}}{d t}=-a\left(T_{1}-T_{\infty}\right)-\delta(t-1)+H(t-2)$

whereas cup 2 is left undisturbed and evolves as follows

$\frac{d T_{2}}{d t}=-a\left(T_{2}-T_{\infty}\right)$

where $\delta(t)$ and $H(t)$ are the Dirac delta and Heaviside functions respectively, and $a$ is a positive constant.

(a) Derive expressions for $T_{1}(t)$ when $0<t \leqslant 1$ and for $T_{2}(t)$ when $t>0$.

(b) Show for $1<t<2$ that

$T_{1}(t)=T_{\infty}+\left(T_{0}-T_{\infty}-e^{a}\right) e^{-a t}$

(c) Derive an expression for $T_{1}(t)$ for $t>2$.

(d) At what time $t^{*}$ is $T_{1}=T_{2}$ ?

(e) Find how $t^{*}$ behaves for $a \rightarrow 0$ and explain your result.

Paper 4, Section I, A

commentGalileo releases a cannonball of mass $m$ from the top of the leaning tower of Pisa, a vertical height $h$ above the ground. Ignoring the rotation of the Earth but assuming that the cannonball experiences a quadratic drag force whose magnitude is $\gamma v^{2}$ (where $v$ is the speed of the cannonball), find the time for it to hit the ground in terms of $h, m, \gamma$ and $g$, the acceleration due to gravity. [You may assume that $g$ is constant.]

Paper 4, Section I, A

commentA rocket of mass $m(t)$ moving at speed $v(t)$ and ejecting fuel behind it at a constant speed $u$ relative to the rocket, is subject to an external force $F$. Considering a small time interval $\delta t$, derive the rocket equation

$m \frac{d v}{d t}+u \frac{d m}{d t}=F$

In deep space where $F=0$, how much faster does the rocket go if it burns half of its mass in fuel?

Paper 4, Section II, A

commentAn inertial frame $S$ and another reference frame $S^{\prime}$ have a common origin $O$, and $S^{\prime}$ rotates with angular velocity vector $\omega(t)$ with respect to $S$. Derive the results (a) and (b) below, where dot denotes a derivative with respect to time $t$ :

(a) The rates of change of an arbitrary vector $\mathbf{a}(t)$ in frames $S$ and $S^{\prime}$ are related by

$(\dot{\mathbf{a}})_{S}=(\dot{\mathbf{a}})_{S^{\prime}}+\boldsymbol{\omega} \times \mathbf{a} .$

(b) The accelerations in $S$ and $S^{\prime}$ are related by

$(\ddot{\mathbf{r}})_{S}=(\ddot{\mathbf{r}})_{S^{\prime}}+2 \boldsymbol{\omega} \times(\dot{\mathbf{r}})_{S^{\prime}}+(\dot{\boldsymbol{\omega}})_{S^{\prime}} \times \mathbf{r}+\boldsymbol{\omega} \times(\boldsymbol{\omega} \times \mathbf{r}),$

where $\mathbf{r}(t)$ is the position vector relative to $O$.

Just after passing the South Pole, a ski-doo of mass $m$ is travelling on a constant longitude with speed $v$. Find the magnitude and direction of the sideways component of apparent force experienced by the ski-doo. [The sideways component is locally along the surface of the Earth and perpendicular to the motion of the ski-doo.]

Paper 4, Section II, A

comment(a) Writing a mass dimension as $M$, a time dimension as $T$, a length dimension as $L$ and a charge dimension as $Q$, write, using relations that you know, the dimensions of:

(i) force

(ii) electric field

(b) In the Large Hadron Collider at CERN, a proton of rest mass $m$ and charge $q>0$ is accelerated by a constant electric field $\mathbf{E} \neq \mathbf{0}$. At time $t=0$, the particle is at rest at the origin.

Writing the proton's position as $\mathbf{x}(t)$ and including relativistic effects, calculate $\dot{\mathbf{x}}(t)$. Use your answers to part (a) to check that the dimensions in your expression are correct.

Sketch a graph of $|\dot{\mathbf{x}}(t)|$ versus $t$, commenting on the $t \rightarrow \infty$ limit.

Calculate $|\mathbf{x}(t)|$ as an explicit function of $t$ and find the non-relativistic limit at small times $t$. What kind of motion is this?

(c) At a later time $t_{0}$, an observer in the laboratory frame sees a cosmic microwave photon of energy $E_{\gamma}$ hit the accelerated proton, leaving only a $\Delta^{+}$particle of mass $m_{\Delta}$ in the final state. In its rest frame, the $\Delta^{+}$takes a time $t_{\Delta}$ to decay. How long does it take to decay in the laboratory frame as a function of $q, \mathbf{E}, t_{0}, m, E_{\gamma}, m_{\Delta}, t_{\Delta}$ and $c$, the speed of light in a vacuum?

Paper 4, Section II, A

comment(a) A particle of mass $m$ and positive charge $q$ moves with velocity $\dot{\mathbf{x}}$ in a region in which the magnetic field $\mathbf{B}=(0,0, B)$ is constant and no other forces act, where $B>0$. Initially, the particle is at position $\mathbf{x}=(1,0,0)$ and $\dot{\mathbf{x}}=(0, v, v)$. Write the equation of motion of the particle and then solve it to find $\mathbf{x}$ as a function of time $t$. Sketch its path in $(x, y, z)$.

(b) For $B=0$, three point particles, each of charge $q$, are fixed at $(0, a / \sqrt{3}, 0)$, $(a / 2,-a /(2 \sqrt{3}), 0)$ and $(-a / 2,-a /(2 \sqrt{3}), 0)$, respectively. Another point particle of mass $m$ and charge $q$ is constrained to move in the $z=0$ plane and suffers Coulomb repulsion from each fixed charge. Neglecting any magnetic fields,

(i) Find the position of an equilibrium point.

(ii) By finding the form of the electric potential near this point, deduce that the equilibrium is stable.

(iii) Consider small displacements of the point particle from the equilibrium point. By resolving forces in the directions $(1,0,0)$ and $(0,1,0)$, show that the frequency of oscillation is

$\omega=A \frac{|q|}{\sqrt{m \epsilon_{0} a^{3}}},$

where $A$ is a constant which you should find.

[You may assume that if two identical charges $q$ are separated by a distance $d$ then the repulsive Coulomb force experienced by each of the charges is $q^{2} /\left(4 \pi \epsilon_{0} d^{2}\right)$, where $\epsilon_{0}$ is a constant.]

Paper 4, Section II, A

commentIn an alien invasion, a flying saucer hovers at a fixed point $S$, a height $l$ far above the White House, which is at point $W$. A wrecking ball of mass $m$ is attached to one end of a light inextensible rod, also of length $l$. The other end of the rod is attached to the flying saucer. The wrecking ball is initially at rest at point $B$, and the angle $W S B$ is $\theta_{0}$. At $W$, the acceleration due to gravity is $g$. Assume that the rotation of the Earth can be neglected and that the only force acting is Earth's gravity.

(a) Under the approximations that gravity acts everywhere parallel to the line $S W$ and that the acceleration due to Earth's gravity is constant throughout the space through which the wrecking ball is travelling, find the speed $v_{1}$ with which the wrecking ball hits the White House, in terms of the constants introduced above.

(b) Taking into account the fact that gravity is non-uniform and acts toward the centre of the Earth, find the speed $v_{2}$ with which the wrecking ball hits the White House in terms of the constants introduced above and $R$, where $R$ is the radius of the Earth, which you may assume is exactly spherical.

(c) Finally, show that

$v_{2}=v_{1}\left(1+\left(A+B \cos \theta_{0}\right) \frac{l}{R}+O\left(\frac{l^{2}}{R^{2}}\right)\right)$

where $A$ and $B$ are constants, which you should determine.

Paper 3, Section $I$, D

commentWhat is the orthogonal group $\mathrm{O}(n)$ ? What is the special orthogonal group $\mathrm{SO}(n) ?$

Show that every element of $\mathrm{SO}(3)$ has an eigenvector with eigenvalue $1 .$

Is it true that every element of $\mathrm{O}(3)$ is either a rotation or a reflection? Justify your answer.

Paper 3, Section I, D

commentProve that two elements of $S_{n}$ are conjugate if and only if they have the same cycle type.

Describe a condition on the centraliser (in $S_{n}$ ) of a permutation $\sigma \in A_{n}$ that ensures the conjugacy class of $\sigma$ in $A_{n}$ is the same as the conjugacy class of $\sigma$ in $S_{n}$. Justify your answer.

How many distinct conjugacy classes are there in $A_{5}$ ?

Paper 3, Section II, D

commentLet $\mathcal{M}$ be the group of Möbius transformations of $\mathbb{C} \cup\{\infty\}$ and let $\mathrm{SL}_{2}(\mathbb{C})$ be the group of all $2 \times 2$ complex matrices of determinant 1 .

Show that the map $\theta: \mathrm{SL}_{2}(\mathbb{C}) \rightarrow \mathcal{M}$ given by

$\theta\left(\begin{array}{ll} a & b \\ c & d \end{array}\right)(z)=\frac{a z+b}{c z+d}$

is a surjective homomorphism. Find its kernel.

Show that any $T \in \mathcal{M}$ not equal to the identity is conjugate to a Möbius map $S$ where either $S z=\mu z$ with $\mu \neq 0,1$ or $S z=z+1$. [You may use results about matrices in $\mathrm{SL}_{2}(\mathbb{C})$ as long as they are clearly stated.]

Show that any non-identity Möbius map has one or two fixed points. Also show that if $T$ is a Möbius map with just one fixed point $z_{0}$ then $T^{n} z \rightarrow z_{0}$ as $n \rightarrow \infty$ for any $z \in \mathbb{C} \cup\{\infty\}$. [You may assume that Möbius maps are continuous.]

Paper 3, Section II, D

commentState and prove the first isomorphism theorem. [You may assume that kernels of homomorphisms are normal subgroups and images are subgroups.]

Let $G$ be a group with subgroup $H$ and normal subgroup $N$. Prove that $N H=\{n h: n \in N, h \in H\}$ is a subgroup of $G$ and $N \cap H$ is a normal subgroup of $H$. Further, show that $N$ is a normal subgroup of $N H$.

Prove that $\frac{H}{N \cap H}$ is isomorphic to $\frac{N H}{N}$.

If $K$ and $H$ are both normal subgroups of $G$ must $K H$ be a normal subgroup of $G$ ?

If $K$ and $H$ are subgroups of $G$, but not normal subgroups, must $K H$ be a subgroup of $G$ ?

Justify your answers.

Paper 3, Section II, D

commentState and prove Lagrange's Theorem.

Hence show that if $G$ is a finite group and $g \in G$ then the order of $g$ divides the order of $G$.

How many elements are there of order 3 in the following groups? Justify your answers.

(a) $C_{3} \times C_{9}$, where $C_{n}$ denotes the cyclic group of order $n$.

(b) $D_{2 n}$ the dihedral group of order $2 n$.

(c) $S_{7}$ the symmetric group of degree 7 .

(d) $A_{7}$ the alternating group of degree 7 .

Paper 3, Section II, D

commentLet $H$ and $K$ be subgroups of a group $G$ satisfying the following two properties.

(i) All elements of $G$ can be written in the form $h k$ for some $h \in H$ and some $k \in K$.

(ii) $H \cap K=\{e\}$.

Prove that $H$ and $K$ are normal subgroups of $G$ if and only if all elements of $H$ commute with all elements of $K$.

State and prove Cauchy's Theorem.

Let $p$ and $q$ be distinct primes. Prove that an abelian group of order $p q$ is isomorphic to $C_{p} \times C_{q}$. Is it true that all abelian groups of order $p^{2}$ are isomorphic to $C_{p} \times C_{p}$ ?

Paper 4, Section $I$, E

commentShow that the series

$\sum_{n=1}^{\infty} \frac{1}{n^{2}+n} \quad \text { and } \quad \sum_{n=1}^{\infty} \frac{1}{(2 n-1) !}$

converge. Determine in each case whether the limit is a rational number. Justify your answers.

Paper 4, Section I, E

commentFind all solutions to the simultaneous congruences

$4 x \equiv 1 \quad(\bmod 21) \quad \text { and } \quad 2 x \equiv 5 \quad(\bmod 45)$

Paper 4, Section II, $7 \mathrm{E}$

comment(a) Let $f: X \rightarrow Y$ be a function. Show that the following statements are equivalent.

(i) $f$ is injective.

(ii) For every subset $A \subset X$ we have $f^{-1}(f(A))=A$.

(iii) For every pair of subsets $A, B \subset X$ we have $f(A \cap B)=f(A) \cap f(B)$.

(b) Let $f: X \rightarrow X$ be an injection. Show that $X=A \cup B$ for some subsets $A, B \subset X$ such that

$\bigcap_{n=1}^{\infty} f^{n}(A)=\emptyset \quad \text { and } \quad f(B)=B$

[Here $f^{n}$ denotes the $n$-fold composite of $f$ with itself.]

Paper 4, Section II, E

comment(a) What is a countable set? Let $X, A, B$ be sets with $A, B$ countable. Show that if $f: X \rightarrow A \times B$ is an injection then $X$ is countable. Deduce that $\mathbb{Z}$ and $\mathbb{Q}$ are countable. Show too that a countable union of countable sets is countable.

(b) Show that, in the plane, any collection of pairwise disjoint circles with rational radius is countable.

(c) A lollipop is any subset of the plane obtained by translating, rotating and scaling (by any factor $\lambda>0$ ) the set

$\left\{(x, y) \in \mathbb{R}^{2} \mid x^{2}+y^{2}=1\right\} \cup\left\{(0, y) \in \mathbb{R}^{2} \mid-3 \leqslant y \leqslant-1\right\} .$

What happens if in part (b) we replace 'circles with rational radius' by 'lollipops'?

Paper 4, Section II, E

commentState the inclusion-exclusion principle.

Let $n \geqslant 2$ be an integer. Let $X=\{0,1,2, \ldots, n-1\}$ and

$Y=\left\{(a, b) \in X^{2} \mid \operatorname{gcd}(a, b, n)=1\right\}$

where $\operatorname{gcd}\left(x_{1}, \ldots, x_{k}\right)$ is the largest number dividing all of $x_{1}, \ldots, x_{k}$. Let $R$ be the relation on $Y$ where $(a, b) R(c, d)$ if $a d-b c \equiv 0(\bmod n)$.

(a) Show that

$|Y|=n^{2} \prod_{p \mid n}\left(1-\frac{1}{p^{2}}\right)$

where the product is over all primes $p$ dividing $n$.

(b) Show that if $\operatorname{gcd}(a, b, n)=1$ then there exist integers $r, s, t$ with $r a+s b+t n=1$.

(c) Show that if $(a, b) R(c, d)$ then there exists an integer $\lambda$ with $\lambda a \equiv c(\bmod n)$ and $\lambda b \equiv d(\bmod n)$. [Hint: Consider $\lambda=r c+s d$, where $r, s$ are as in part (b).] Deduce that $R$ is an equivalence relation.

(d) What is the size of the equivalence class containing $(1,1) ?$ Show that all equivalence classes have the same size, and deduce that the number of equivalence classes is

$n \prod_{p \mid n}\left(1+\frac{1}{p}\right) \text {. }$

Paper 4, Section II, E

comment(a) State and prove Fermat's theorem. Use it to compute $3^{803}(\bmod 17)$.

(b) The Fibonacci numbers $F_{0}, F_{1}, F_{2}, \ldots$ are defined by $F_{0}=0, F_{1}=1$, and $F_{n}=F_{n-1}+F_{n-2}$ for all $n \geqslant 2$. Prove by induction that for all $n \geqslant 1$ we have

$F_{2 n}=F_{n}\left(F_{n-1}+F_{n+1}\right) \quad \text { and } \quad F_{2 n+1}=F_{n}^{2}+F_{n+1}^{2}$

(c) Let $m \geqslant 1$ and let $p$ be an odd prime dividing $F_{m}$. Which of the following statements are true, and which can be false? Justify your answers.

(i) If $m$ is odd then $p \equiv 1(\bmod 4)$.

(ii) If $m$ is even then $p \equiv 3(\bmod 4)$.

Paper 2, Section I, 3F

comment(a) Prove that $\log (n !) \sim n \log n$ as $n \rightarrow \infty$.

(b) State Stirling's approximation for $n$ !.

(c) A school party of $n$ boys and $n$ girls travel on a red bus and a green bus. Each bus can hold $n$ children. The children are distributed at random between the buses.

Let $A_{n}$ be the event that the boys all travel on the red bus and the girls all travel on the green bus. Show that

$\mathbb{P}\left(A_{n}\right) \sim \frac{\sqrt{\pi n}}{4^{n}} \text { as } n \rightarrow \infty$

Paper 2, Section I, F

commentLet $X$ and $Y$ be independent exponential random variables each with parameter 1 . Write down the joint density function of $X$ and $Y$.

Let $U=6 X+8 Y$ and $V=2 X+3 Y$. Find the joint density function of $U$ and $V$.

Are $U$ and $V$ independent? Briefly justify your answer.

Paper 2, Section II, F

commentLet $A_{1}, A_{2}, \ldots, A_{n}$ be events in some probability space. Let $X$ be the number of $A_{i}$ that occur (so $X$ is a random variable). Show that

$\mathbb{E}(X)=\sum_{i=1}^{n} \mathbb{P}\left(A_{i}\right)$

and

$\operatorname{Var}(X)=\sum_{i=1}^{n} \sum_{j=1}^{n}\left(\mathbb{P}\left(A_{i} \cap A_{j}\right)-\mathbb{P}\left(A_{i}\right) \mathbb{P}\left(A_{j}\right)\right)$

[Hint: Write $X=\sum_{i=1}^{n} X_{i}$ where $X_{i}=\left\{\begin{array}{ll}1 & \text { if } A_{i} \text { occurs } \\ 0 & \text { if not }\end{array}\right.$.]

A collection of $n$ lightbulbs are arranged in a circle. Each bulb is on independently with probability $p$. Let $X$ be the number of bulbs such that both that bulb and the next bulb clockwise are on. Find $\mathbb{E}(X)$ and $\operatorname{Var}(X)$.

Let $B$ be the event that there is at least one pair of adjacent bulbs that are both on.

Use Markov's inequality to show that if $p=n^{-0.6}$ then $\mathbb{P}(B) \rightarrow 0$ as $n \rightarrow \infty$.

Use Chebychev's inequality to show that if $p=n^{-0.4}$ then $\mathbb{P}(B) \rightarrow 1$ as $n \rightarrow \infty$.

Paper 2, Section II, F

commentRecall that a random variable $X$ in $\mathbb{R}^{2}$ is bivariate normal or Gaussian if $u^{T} X$ is normal for all $u \in \mathbb{R}^{2}$. Let $X=\left(\begin{array}{c}X_{1} \\ X_{2}\end{array}\right)$ be bivariate normal.

(a) (i) Show that if $A$ is a $2 \times 2$ real matrix then $A X$ is bivariate normal.

(ii) Let $\mu=\mathbb{E}(X)$ and $V=\operatorname{Var}(X)=\mathbb{E}\left[(X-\mu)(X-\mu)^{T}\right]$. Find the moment generating function $M_{X}(\lambda)=\mathbb{E}\left(e^{\lambda^{T}} X\right)$ of $X$ and deduce that the distribution of a bivariate normal random variable $X$ is uniquely determined by $\mu$ and $V$.

(iii) Let $\mu_{i}=\mathbb{E}\left(X_{i}\right)$ and $\sigma_{i}^{2}=\operatorname{Var}\left(X_{i}\right)$ for $i=1,2$. Let $\rho=\frac{\operatorname{Cov}\left(X_{1}, X_{2}\right)}{\sigma_{1} \sigma_{2}}$ be the correlation of $X_{1}$ and $X_{2}$. Write down $V$ in terms of some or all of $\mu_{1}, \mu_{2}, \sigma_{1}, \sigma_{2}$ and $\rho$. If $\operatorname{Cov}\left(X_{1}, X_{2}\right)=0$, why must $X_{1}$ and $X_{2}$ be independent?

For each $a \in \mathbb{R}$, find $\operatorname{Cov}\left(X_{1}, X_{2}-a X_{1}\right)$. Hence show that $X_{2}=a X_{1}+Y$ for some normal random variable $Y$ in $\mathbb{R}$ that is independent of $X_{1}$ and some $a \in \mathbb{R}$ that should be specified.

(b) A certain species of East Anglian goblin has left arm of mean length $100 \mathrm{~cm}$ with standard deviation $1 \mathrm{~cm}$, and right arm of mean length $102 \mathrm{~cm}$ with standard deviation $2 \mathrm{~cm}$. The correlation of left- and right-arm-length of a goblin is $\frac{1}{2}$. You may assume that the distribution of left- and right-arm-lengths can be modelled by a bivariate normal distribution. What is the probability that a randomly selected goblin has longer right arm than left arm?

[You may give your answer in terms of the distribution function $\Phi$ of a $N(0,1)$ random variable $Z$. That is, $\Phi(t)=\mathbb{P}(Z \leqslant t)$.J

Paper 2, Section II, F

commentLet $m$ and $n$ be positive integers with $n>m>0$ and let $p \in(0,1)$ be a real number. A random walk on the integers starts at $m$. At each step, the walk moves up 1 with probability $p$ and down 1 with probability $q=1-p$. Find, with proof, the probability that the walk hits $n$ before it hits 0 .

Patricia owes a very large sum $£ 2(N$ !) of money to a member of a violent criminal gang. She must return the money this evening to avoid terrible consequences but she only has $£ N$ !. She goes to a casino and plays a game with the probability of her winning being $\frac{18}{37}$. If she bets $£ a$ on the game and wins then her $£ a$ is returned along with a further $£ a$; if she loses then her $£ a$ is lost.

The rules of the casino allow Patricia to play the game repeatedly until she runs out of money. She may choose the amount $£ a$ that she bets to be any integer a with $1 \leqslant a \leqslant N$, but it must be the same amount each time. What choice of $a$ would be best and why?

What choice of $a$ would be best, and why, if instead the probability of her winning the game is $\frac{19}{37}$ ?

Paper 2, Section II, F

comment(a) State the axioms that must be satisfied by a probability measure $\mathbb{P}$ on a probability space $\Omega$.

Let $A$ and $B$ be events with $\mathbb{P}(B)>0$. Define the conditional probability $\mathbb{P}(A \mid B)$.

Let $B_{1}, B_{2}, \ldots$ be pairwise disjoint events with $\mathbb{P}\left(B_{i}\right)>0$ for all $i$ and $\Omega=\cup_{i=1}^{\infty} B_{i}$. Starting from the axioms, show that

$\mathbb{P}(A)=\sum_{i=1}^{\infty} \mathbb{P}\left(A \mid B_{i}\right) \mathbb{P}\left(B_{i}\right)$

and deduce Bayes' theorem.

(b) Two identical urns contain white balls and black balls. Urn I contains 45 white balls and 30 black balls. Urn II contains 12 white balls and 36 black balls. You do not know which urn is which.

(i) Suppose you select an urn and draw one ball at random from it. The ball is white. What is the probability that you selected Urn I?

(ii) Suppose instead you draw one ball at random from each urn. One of the balls is white and one is black. What is the probability that the white ball came from Urn I?

(c) Now suppose there are $n$ identical urns containing white balls and black balls, and again you do not know which urn is which. Each urn contains 1 white ball. The $i$ th urn contains $2^{i}-1$ black balls $(1 \leqslant i \leqslant n)$. You select an urn and draw one ball at random from it. The ball is white. Let $p(n)$ be the probability that if you replace this ball and again draw a ball at random from the same urn then the ball drawn on the second occasion is also white. Show that $p(n) \rightarrow \frac{1}{3}$ as $n \rightarrow \infty$

Paper 3, Section I, B

commentLet

$\begin{aligned} u &=\left(2 x+x^{2} z+z^{3}\right) \exp ((x+y) z) \\ v &=\left(x^{2} z+z^{3}\right) \exp ((x+y) z) \\ w &=\left(2 z+x^{3}+x^{2} y+x z^{2}+y z^{2}\right) \exp ((x+y) z) \end{aligned}$

Show that $u d x+v d y+w d z$ is an exact differential, clearly stating any criteria that you use.

Show that for any path between $(-1,0,1)$ and $(1,0,1)$

$\int_{(-1,0,1)}^{(1,0,1)}(u d x+v d y+w d z)=4 \sinh 1$

Paper 3, Section I, B

commentApply the divergence theorem to the vector field $\mathbf{u}(\mathbf{x})=\mathbf{a} \phi(\mathbf{x})$ where $\mathbf{a}$ is an arbitrary constant vector and $\phi$ is a scalar field, to show that

$\int_{V} \nabla \phi d V=\int_{S} \phi d \mathbf{S}$

where $V$ is a volume bounded by the surface $S$ and $d \mathbf{S}$ is the outward pointing surface element.

Verify that this result holds when $\phi=x+y$ and $V$ is the spherical volume $x^{2}+$ $y^{2}+z^{2} \leqslant a^{2}$. [You may use the result that $d \mathbf{S}=a^{2} \sin \theta d \theta d \phi(\sin \theta \cos \phi, \sin \theta \sin \phi, \cos \theta)$, where $\theta$ and $\phi$ are the usual angular coordinates in spherical polars and the components of $d \mathbf{S}$ are with respect to standard Cartesian axes.]

Paper 3, Section II, B

comment(a) The function $u$ satisfies $\nabla^{2} u=0$ in the volume $V$ and $u=0$ on $S$, the surface bounding $V$.

Show that $u=0$ everywhere in $V$.

The function $v$ satisfies $\nabla^{2} v=0$ in $V$ and $v$ is specified on $S$. Show that for all functions $w$ such that $w=v$ on $S$

$\int_{V} \nabla v \cdot \nabla w d V=\int_{V}|\nabla v|^{2} d V$

Hence show that

$\int_{V}|\boldsymbol{\nabla} w|^{2} d V=\int_{V}\left\{|\boldsymbol{\nabla} v|^{2}+|\boldsymbol{\nabla}(w-v)|^{2}\right\} d V \geqslant \int_{V}|\boldsymbol{\nabla} v|^{2} d V$

(b) The function $\phi$ satisfies $\nabla^{2} \phi=\rho(\mathbf{x})$ in the spherical region $|\mathbf{x}|<a$, with $\phi=0$ on $|\mathbf{x}|=a$. The function $\rho(\mathbf{x})$ is spherically symmetric, i.e. $\rho(\mathbf{x})=\rho(|\mathbf{x}|)=\rho(r)$.

Suppose that the equation and boundary conditions are satisfied by a spherically symmetric function $\Phi(r)$. Show that

$4 \pi r^{2} \Phi^{\prime}(r)=4 \pi \int_{0}^{r} s^{2} \rho(s) d s$

Hence find the function $\Phi(r)$ when $\rho(r)$ is given by $\rho(r)=\left\{\begin{array}{ll}\rho_{0} & \text { if } 0 \leqslant r \leqslant b \\ 0 & \text { if } b<r \leqslant a\end{array}\right.$, with $\rho_{0}$ constant.

Explain how the results obtained in part (a) of the question imply that $\Phi(r)$ is the only solution of $\nabla^{2} \phi=\rho(r)$ which satisfies the specified boundary condition on $|\mathbf{x}|=a$.

Use your solution and the results obtained in part (a) of the question to show that, for any function $w$ such that $w=1$ on $r=b$ and $w=0$ on $r=a$,

$\int_{U(b, a)}|\nabla w|^{2} d V \geqslant \frac{4 \pi a b}{a-b}$

where $U(b, a)$ is the region $b<r<a$.

Paper 3, Section II, B

commentShow that for a vector field $\mathbf{A}$

$\nabla \times(\boldsymbol{\nabla} \times \mathbf{A})=\boldsymbol{\nabla}(\boldsymbol{\nabla} \cdot \mathbf{A})-\nabla^{2} \mathbf{A}$

Hence find an $\mathbf{A}(\mathbf{x})$, with $\boldsymbol{\nabla} \cdot \mathbf{A}=0$, such that $\mathbf{u}=\left(y^{2}, z^{2}, x^{2}\right)=\nabla \times \mathbf{A}$. [Hint: Note that $\mathbf{A}(\mathbf{x})$ is not defined uniquely. Choose your expression for $\mathbf{A}(\mathbf{x})$ to be as simple as possible.

Now consider the cone $x^{2}+y^{2} \leqslant z^{2} \tan ^{2} \alpha, 0 \leqslant z \leqslant h$. Let $S_{1}$ be the curved part of the surface of the cone $\left(x^{2}+y^{2}=z^{2} \tan ^{2} \alpha, 0 \leqslant z \leqslant h\right)$ and $S_{2}$ be the flat part of the surface of the cone $\left(x^{2}+y^{2} \leqslant h^{2} \tan ^{2} \alpha, z=h\right)$.

Using the variables $z$ and $\phi$ as used in cylindrical polars $(r, \phi, z)$ to describe points on $S_{1}$, give an expression for the surface element $d \mathbf{S}$ in terms of $d z$ and $d \phi$.

Evaluate $\int_{S_{1}} \mathbf{u} \cdot d \mathbf{S}$.

What does the divergence theorem predict about the two surface integrals $\int_{S_{1}} \mathbf{u} \cdot d \mathbf{S}$ and $\int_{S_{2}} \mathbf{u} \cdot d \mathbf{S}$ where in each case the vector $d \mathbf{S}$ is taken outwards from the cone?

What does Stokes theorem predict about the integrals $\int_{S_{1}} \mathbf{u} \cdot d \mathbf{S}$ and $\int_{S_{2}} \mathbf{u} \cdot d \mathbf{S}$ (defined as in the previous paragraph) and the line integral $\int_{C} \mathbf{A} \cdot d \mathbf{l}$ where $C$ is the circle $x^{2}+y^{2}=h^{2} \tan ^{2} \alpha, z=h$ and the integral is taken in the anticlockwise sense, looking from the positive $z$ direction?

Evaluate $\int_{S_{2}} \mathbf{u} \cdot d \mathbf{S}$ and $\int_{C} \mathbf{A} \cdot d \mathbf{l}$, making your method clear and verify that each of these predictions holds.

Paper 3, Section II, B

commentFor a given set of coordinate axes the components of a 2 nd rank tensor $T$ are given by $T_{i j}$.

(a) Show that if $\lambda$ is an eigenvalue of the matrix with elements $T_{i j}$ then it is also an eigenvalue of the matrix of the components of $T$ in any other coordinate frame.

Show that if $T$ is a symmetric tensor then the multiplicity of the eigenvalues of the matrix of components of $T$ is independent of coordinate frame.

A symmetric tensor $T$ in three dimensions has eigenvalues $\lambda, \lambda, \mu$, with $\mu \neq \lambda$.

Show that the components of $T$ can be written in the form

$T_{i j}=\alpha \delta_{i j}+\beta n_{i} n_{j}$

where $n_{i}$ are the components of a unit vector.

(b) The tensor $T$ is defined by

$T_{i j}(\mathbf{y})=\int_{S} x_{i} x_{j} \exp \left(-c|\mathbf{y}-\mathbf{x}|^{2}\right) d A(\mathbf{x})$

where $S$ is the surface of the unit sphere, $\mathbf{y}$ is the position vector of a point on $S$, and $c$ is a constant.

Deduce, with brief reasoning, that the components of $T$ can be written in the form (1) with $n_{i}=y_{i}$. [You may quote any results derived in part (a).]

Using suitable spherical polar coordinates evaluate $T_{k k}$ and $T_{i j} y_{i} y_{j}$.

Explain how to deduce the values of $\alpha$ and $\beta$ from $T_{k k}$ and $T_{i j} y_{i} y_{j}$. [You do not need to write out the detailed formulae for these quantities.]

Paper 3, Section II, B

commentDefine the Jacobian, $J$, of the one-to-one transformation

$(x, y, z) \rightarrow(u, v, w)$

Give a careful explanation of the result

$\int_{D} f(x, y, z) d x d y d z=\int_{\Delta}|J| \phi(u, v, w) d u d v d w$

where

$\phi(u, v, w)=f(x(u, v, w), y(u, v, w), z(u, v, w))$

and the region $D$ maps under the transformation to the region $\Delta$.

Consider the region $D$ defined by

$x^{2}+\frac{y^{2}}{k^{2}}+z^{2} \leqslant 1$

and

$\frac{x^{2}}{\alpha^{2}}+\frac{y^{2}}{k^{2} \alpha^{2}}-\frac{z^{2}}{\gamma^{2}} \geqslant 1$

where $\alpha, \gamma$ and $k$ are positive constants.

Let $\tilde{D}$ be the intersection of $D$ with the plane $y=0$. Write down the conditions for $\tilde{D}$ to be non-empty. Sketch the geometry of $\tilde{D}$ in $x>0$, clearly specifying the curves that define its boundaries and points that correspond to minimum and maximum values of $x$ and of $z$ on the boundaries.

Use a suitable change of variables to evaluate the volume of the region $D$, clearly explaining the steps in your calculation.

Paper 1, Section I, $1 \mathrm{C}$

comment(a) If

$x+i y=\sum_{a=0}^{200} i^{a}+\prod_{b=1}^{50} i^{b}$

where $x, y \in \mathbb{R}$, what is the value of $x y$ ?

(b) Evaluate

$\frac{(1+i)^{2019}}{(1-i)^{2017}}$

(c) Find a complex number $z$ such that

$i^{i^{z}}=2$

(d) Interpret geometrically the curve defined by the set of points satisfying

$\log z=i \log \bar{z}$

in the complex $z$-plane.

Paper 1, Section I, A

commentIf $A$ is an $n$ by $n$ matrix, define its determinant $\operatorname{det} A$.

Find the following in terms of $\operatorname{det} A$ and a scalar $\lambda$, clearly showing your argument:

(i) $\operatorname{det} B$, where $B$ is obtained from $A$ by multiplying one row by $\lambda$.

(ii) $\operatorname{det}(\lambda A)$.

(iii) $\operatorname{det} C$, where $C$ is obtained from $A$ by switching row $k$ and row $l(k \neq l)$.

(iv) $\operatorname{det} D$, where $D$ is obtained from $A$ by adding $\lambda$ times column $l$ to column $k$ $(k \neq l)$.

Paper 1, Section II, $\mathbf{6 B}$

commentLet $\mathbf{e}_{1}, \mathbf{e}_{2}, \mathbf{e}_{3}$ be the standard basis vectors of $\mathbb{R}^{3}$. A second set of vectors $\mathbf{f}_{1}, \mathbf{f}_{2}, \mathbf{f}_{3}$ are defined with respect to the standard basis by

$\mathbf{f}_{j}=\sum_{i=1}^{3} P_{i j} \mathbf{e}_{i}, \quad j=1,2,3$

The $P_{i j}$ are the elements of the $3 \times 3$ matrix $P$. State the condition on $P$ under which the set $\left\{\mathbf{f}_{1}, \mathbf{f}_{2}, \mathbf{f}_{3}\right\}$ forms a basis of $\mathbb{R}^{3}$.

Define the matrix $A$ that, for a given linear transformation $\alpha$, gives the relation between the components of any vector $\mathbf{v}$ and those of the corresponding $\alpha(\mathbf{v})$, with the components specified with respect to the standard basis.

Show that the relation between the matrix $A$ and the matrix $\tilde{A}$ of the same transformation with respect to the second basis $\left\{\mathbf{f}_{1}, \mathbf{f}_{2}, \mathbf{f}_{3}\right\}$ is

$\tilde{A}=P^{-1} A P$

Consider the matrix

$A=\left(\begin{array}{ccc} 2 & 6 & 2 \\ 0 & -1 & -1 \\ 0 & 6 & 4 \end{array}\right)$

Find a matrix $P$ such that $B=P^{-1} A P$ is diagonal. Give the elements of $B$ and demonstrate explicitly that the relation between $A$ and $B$ holds.

Give the elements of $A^{n} P$ for any positive integer $n$.

Paper 1, Section II, 7B

comment(a) Let $A$ be an $n \times n$ matrix. Define the characteristic polynomial $\chi_{A}(z)$ of $A$. [Choose a sign convention such that the coefficient of $z^{n}$ in the polynomial is equal to $\left.(-1)^{n} .\right]$ State and justify the relation between the characteristic polynomial and the eigenvalues of $A$. Why does $A$ have at least one eigenvalue?

(b) Assume that $A$ has $n$ distinct eigenvalues. Show that $\chi_{A}(A)=0$. [Each term $c_{r} z^{r}$ in $\chi_{A}(z)$ corresponds to a term $c_{r} A^{r}$ in $\left.\chi_{A}(A) .\right]$

(c) For a general $n \times n$ matrix $B$ and integer $m \geqslant 1$, show that $\chi_{B^{m}}\left(z^{m}\right)=\prod_{l=1}^{m} \chi_{B}\left(\omega_{l} z\right)$, where $\omega_{l}=e^{2 \pi i l / m},(l=1, \ldots, m) .[$ Hint: You may find it helpful to note the factorization of $z^{m}-1$.]

Prove that if $B^{m}$ has an eigenvalue $\lambda$ then $B$ has an eigenvalue $\mu$ where $\mu^{m}=\lambda$.

Paper 1, Section II, A

The exponential of a square matrix $M$ is defined as

$\exp M=I+\sum_{n=1}^{\infty} \frac{M^{n}}{n !}$

where $I$ is the identity matrix. [You do not have to consider issues of convergence.]

(a) Calculate the elements of $R$ and $S$, where

$R=\exp \left(\begin{array}{cc} 0 & -\theta \\ \theta & 0 \end{array}\right), \quad S=\exp \left(\begin{array}{ll} 0 & \theta \\ \theta & 0 \end{array}\right)$

and $\theta$ is a real number.

(b) Show that $R R^{T}=I$ and that

$S J S=J, \quad \text { where } \quad J=\left(\begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array}\right)$

(c) Consider the matrices

$A=\left(\begin{array}{ccc} 0 & 0 & 0 \\ 0 & 0 & -1 / 2 \\ 0 & 1 / 2 & 0 \end{array}\right), \quad B=\left(\begin{array}{lll} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \end{array}\right)$

Calculate:

(i) $\exp (x A)$,

(ii) $\exp (x B)$.

(d) Defining

$$C=\left(\begin{array}{ccc}{\textstyle 1}& {\textstyle 0}& {\textstyle 0}\\ {\textstyle 0}& {\textstyle -1}& {\textstyle 0}\\ {\textstyle 0}& {\textstyle 0}& {\textstyle -1}\end{array}\right)$$