# Part IA, 2013

### Jump to course

Paper 1, Section I, D

commentShow that $\exp (x) \geqslant 1+x$ for $x \geqslant 0$.

Let $\left(a_{j}\right)$ be a sequence of positive real numbers. Show that for every $n$,

$\sum_{1}^{n} a_{j} \leqslant \prod_{1}^{n}\left(1+a_{j}\right) \leqslant \exp \left(\sum_{1}^{n} a_{j}\right)$

Deduce that $\prod_{1}^{n}\left(1+a_{j}\right)$ tends to a limit as $n \rightarrow \infty$ if and only if $\sum_{1}^{n} a_{j}$ does.

Paper 1, Section I, F

comment(a) Suppose $b_{n} \geqslant b_{n+1} \geqslant 0$ for $n \geqslant 1$ and $b_{n} \rightarrow 0$. Show that $\sum_{n=1}^{\infty}(-1)^{n-1} b_{n}$ converges.

(b) Does the series $\sum_{n=2}^{\infty} \frac{1}{n \log n}$ converge or diverge? Explain your answer.

Paper 1, Section II, D

comment(a) Determine the radius of convergence of each of the following power series:

$\sum_{n \geqslant 1} \frac{x^{n}}{n !}, \quad \sum_{n \geqslant 1} n ! x^{n}, \quad \sum_{n \geqslant 1}(n !)^{2} x^{n^{2}}$

(b) State Taylor's theorem.

Show that

$(1+x)^{1 / 2}=1+\sum_{n \geqslant 1} c_{n} x^{n}$

for all $x \in(0,1)$, where

$c_{n}=\frac{\frac{1}{2}\left(\frac{1}{2}-1\right) \ldots\left(\frac{1}{2}-n+1\right)}{n !}$

Paper 1, Section II, E

comment(i) State (without proof) Rolle's Theorem.

(ii) State and prove the Mean Value Theorem.

(iii) Let $f, g:[a, b] \rightarrow \mathbb{R}$ be continuous, and differentiable on $(a, b)$ with $g^{\prime}(x) \neq 0$ for all $x \in(a, b)$. Show that there exists $\xi \in(a, b)$ such that

$\frac{f^{\prime}(\xi)}{g^{\prime}(\xi)}=\frac{f(b)-f(a)}{g(b)-g(a)}$

Deduce that if moreover $f(a)=g(a)=0$, and the limit

$\ell=\lim _{x \rightarrow a} \frac{f^{\prime}(x)}{g^{\prime}(x)}$

exists, then

$\frac{f(x)}{g(x)} \rightarrow \ell \text { as } x \rightarrow a$

(iv) Deduce that if $f: \mathbb{R} \rightarrow \mathbb{R}$ is twice differentiable then for any $a \in \mathbb{R}$

$f^{\prime \prime}(a)=\lim _{h \rightarrow 0} \frac{f(a+h)+f(a-h)-2 f(a)}{h^{2}} .$

Paper 1, Section II, E

comment(a) Let $f:[a, b] \rightarrow \mathbb{R}$. Suppose that for every sequence $\left(x_{n}\right)$ in $[a, b]$ with limit $y \in[a, b]$, the sequence $\left(f\left(x_{n}\right)\right)$ converges to $f(y)$. Show that $f$ is continuous at $y$.

(b) State the Intermediate Value Theorem.

Let $f:[a, b] \rightarrow \mathbb{R}$ be a function with $f(a)=c<f(b)=d$. We say $f$ is injective if for all $x, y \in[a, b]$ with $x \neq y$, we have $f(x) \neq f(y)$. We say $f$ is strictly increasing if for all $x, y$ with $x<y$, we have $f(x)<f(y)$.

(i) Suppose $f$ is strictly increasing. Show that it is injective, and that if $f(x)<f(y)$ then $x<y .$

(ii) Suppose $f$ is continuous and injective. Show that if $a<x<b$ then $c<f(x)<d$. Deduce that $f$ is strictly increasing.

(iii) Suppose $f$ is strictly increasing, and that for every $y \in[c, d]$ there exists $x \in[a, b]$ with $f(x)=y$. Show that $f$ is continuous at $b$. Deduce that $f$ is continuous on $[a, b]$.

Paper 1, Section II, F

commentFix a closed interval $[a, b]$. For a bounded function $f$ on $[a, b]$ and a dissection $\mathcal{D}$ of $[a, b]$, how are the lower sum $s(f, \mathcal{D})$ and upper sum $S(f, \mathcal{D})$ defined? Show that $s(f, \mathcal{D}) \leqslant S(f, \mathcal{D})$.

Suppose $\mathcal{D}^{\prime}$ is a dissection of $[a, b]$ such that $\mathcal{D} \subseteq \mathcal{D}^{\prime}$. Show that

$s(f, \mathcal{D}) \leqslant s\left(f, \mathcal{D}^{\prime}\right) \text { and } S\left(f, \mathcal{D}^{\prime}\right) \leqslant S(f, \mathcal{D})$

By using the above inequalities or otherwise, show that if $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$ are two dissections of $[a, b]$ then

$s\left(f, \mathcal{D}_{1}\right) \leqslant S\left(f, \mathcal{D}_{2}\right)$

For a function $f$ and dissection $\mathcal{D}=\left\{x_{0}, \ldots, x_{n}\right\}$ let

$p(f, \mathcal{D})=\prod_{k=1}^{n}\left[1+\left(x_{k}-x_{k-1}\right) \inf _{x \in\left[x_{k-1}, x_{k}\right]} f(x)\right]$

If $f$ is non-negative and Riemann integrable, show that

$p(f, \mathcal{D}) \leqslant e^{\int_{a}^{b} f(x) d x} .$

[You may use without proof the inequality $e^{t} \geqslant t+1$ for all $t$.]

Paper 2, Section I, A

commentUse the transformation $z=\ln x$ to solve

$\ddot{z}=-\dot{z}^{2}-1-e^{-z}$

subject to the conditions $z=0$ and $\dot{z}=V$ at $t=0$, where $V$ is a positive constant.

Show that when $\dot{z}(t)=0$

$z=\ln \left(\sqrt{V^{2}+4}-1\right)$

Paper 2, Section I, A

commentSolve the equation

$\ddot{y}-\dot{y}-2 y=3 e^{2 t}+3 e^{-t}+3+6 t$

subject to the conditions $y=\dot{y}=0$ at $t=0$.

Paper 2, Section II, $6 \mathrm{~A}$

commentConsider the function

$f(x, y)=\left(x^{2}-y^{4}\right)\left(1-x^{2}-y^{4}\right)$

Determine the type of each of the nine critical points.

Sketch contours of constant $f(x, y)$.

Paper 2, Section II, A

commentThe function $y(x)$ satisfies the equation

$y^{\prime \prime}+p(x) y^{\prime}+q(x) y=0 .$

Give the definitions of the terms ordinary point, singular point, and regular singular point for this equation.

For the equation

$x y^{\prime \prime}+y=0$

classify the point $x=0$ according to your definitions. Find the series solution about $x=0$ which satisfies

$y=0 \quad \text { and } \quad y^{\prime}=1 \quad \text { at } x=0$

For a second solution with $y=1$ at $x=0$, consider an expansion

$y(x)=y_{0}(x)+y_{1}(x)+y_{2}(x)+\ldots,$

where $y_{0}=1$ and $x y_{n+1}^{\prime \prime}=-y_{n}$. Find $y_{1}$ and $y_{2}$ which have $y_{n}(0)=0$ and $y_{n}^{\prime}(1)=0$. Comment on $y^{\prime}$ near $x=0$ for this second solution.

Paper 2, Section II, A

commentMedical equipment is sterilised by placing it in a hot oven for a time $T$ and then removing it and letting it cool for the same time. The equipment at temperature $\theta(t)$ warms and cools at a rate equal to the product of a constant $\alpha$ and the difference between its temperature and its surroundings, $\theta_{1}$ when warming in the oven and $\theta_{0}$ when cooling outside. The equipment starts the sterilisation process at temperature $\theta_{0}$.

Bacteria are killed by the heat treatment. Their number $N(t)$ decreases at a rate equal to the product of the current number and a destruction factor $\beta$. This destruction factor varies linearly with temperature, vanishing at $\theta_{0}$ and having a maximum $\beta_{\max }$ at $\theta_{1}$.

Find an implicit equation for $T$ such that the number of bacteria is reduced by a factor of $10^{-20}$ by the sterilisation process.

A second hardier species of bacteria requires the oven temperature to be increased to achieve the same destruction factor $\beta_{\max }$. How is the sterilisation time $T$ affected?

Paper 2, Section II, A

commentFind $x(t)$ and $y(t)$ which satisfy

$\begin{aligned} &3 \dot{x}+\dot{y}+5 x-y=2 e^{-t}+4 e^{-3 t} \\ &\dot{x}+4 \dot{y}-2 x+7 y=-3 e^{-t}+5 e^{-3 t} \end{aligned}$

subject to $x=y=0$ at $t=0$.

Paper 4 , Section II, B

comment(i) An inertial frame $S$ has orthonormal coordinate basis vectors $\mathbf{e}_{1}, \mathbf{e}_{2}, \mathbf{e}_{3}$. A second frame $S^{\prime}$ rotates with angular velocity $\boldsymbol{\omega}$ relative to $S$ and has coordinate basis vectors $\mathbf{e}_{1}^{\prime}, \mathbf{e}_{2}^{\prime}, \mathbf{e}_{3}^{\prime}$. The motion of $S^{\prime}$ is characterised by the equations $d \mathbf{e}_{i}^{\prime} / d t=\boldsymbol{\omega} \times \mathbf{e}_{i}^{\prime}$ and at $t=0$ the two coordinate frames coincide.

If a particle $P$ has position vector $\mathbf{r}$ show that $\mathbf{v}=\mathbf{v}^{\prime}+\boldsymbol{\omega} \times \mathbf{r}$ where $\mathbf{v}$ and $\mathbf{v}^{\prime}$ are the velocity vectors of $P$ as seen by observers fixed respectively in $S$ and $S^{\prime}$.

(ii) For the remainder of this question you may assume that $\mathbf{a}=\mathbf{a}^{\prime}+2 \boldsymbol{\omega} \times \mathbf{v}^{\prime}+\boldsymbol{\omega} \times(\boldsymbol{\omega} \times \mathbf{r})$ where $\mathbf{a}$ and $\mathbf{a}^{\prime}$ are the acceleration vectors of $P$ as seen by observers fixed respectively in $S$ and $S^{\prime}$, and that $\omega$ is constant.

Consider again the frames $S$ and $S^{\prime}$ in (i). Suppose that $\omega=\omega \mathbf{e}_{3}$ with $\omega$ constant. A particle of mass $m$ moves under a force $\mathbf{F}=-4 m \omega^{2} \mathbf{r}$. When viewed in $S^{\prime}$ its position and velocity at time $t=0$ are $\left(x^{\prime}, y^{\prime}, z^{\prime}\right)=(1,0,0)$ and $\left(\dot{x}^{\prime}, \dot{y}^{\prime}, \dot{z}^{\prime}\right)=(0,0,0)$. Find the motion of the particle in the coordinates of $S^{\prime}$. Show that for an observer fixed in $S^{\prime}$, the particle achieves its maximum speed at time $t=\pi /(4 \omega)$ and determine that speed. [Hint: you may find it useful to consider the combination $\zeta=x^{\prime}+i y^{\prime}$.]

Paper 4, Section $I$, B

commentA frame $S^{\prime}$ moves with constant velocity $v$ along the $x$ axis of an inertial frame $S$ of Minkowski space. A particle $P$ moves with constant velocity $u^{\prime}$ along the $x^{\prime}$ axis of $S^{\prime}$. Find the velocity $u$ of $P$ in $S$.

The rapidity $\varphi$ of any velocity $w$ is defined by $\tanh \varphi=w / c$. Find a relation between the rapidities of $u, u^{\prime}$ and $v$.

Suppose now that $P$ is initially at rest in $S$ and is subsequently given $n$ successive velocity increments of $c / 2$ (each delivered in the instantaneous rest frame of the particle). Show that the resulting velocity of $P$ in $S$ is

$c\left(\frac{e^{2 n \alpha}-1}{e^{2 n \alpha}+1}\right)$

where $\tanh \alpha=1 / 2$.

[You may use without proof the addition formulae $\sinh (a+b)=\sinh a \cosh b+\cosh a \sinh b$ and $\cosh (a+b)=\cosh a \cosh b+\sinh a \sinh b$.]

Paper 4, Section I, B

commentA hot air balloon of mass $M$ is equipped with a bag of sand of mass $m=m(t)$ which decreases in time as the sand is gradually released. In addition to gravity the balloon experiences a constant upwards buoyancy force $T$ and we neglect air resistance effects. Show that if $v(t)$ is the upward speed of the balloon then

$(M+m) \frac{d v}{d t}=T-(M+m) g .$

Initially at $t=0$ the mass of sand is $m(0)=m_{0}$ and the balloon is at rest in equilibrium. Subsequently the sand is released at a constant rate and is depleted in a time $t_{0}$. Show that the speed of the balloon at time $t_{0}$ is

$g t_{0}\left(\left(1+\frac{M}{m_{0}}\right) \ln \left(1+\frac{m_{0}}{M}\right)-1\right)$

[You may use without proof the indefinite integral $\int t /(A-t) d t=-t-A \ln |A-t|+C .$ ]

Paper 4, Section II, B

comment(a) Let $S$ with coordinates $(c t, x, y)$ and $S^{\prime}$ with coordinates $\left(c t^{\prime}, x^{\prime}, y^{\prime}\right)$ be inertial frames in Minkowski space with two spatial dimensions. $S^{\prime}$ moves with velocity $v$ along the $x$-axis of $S$ and they are related by the standard Lorentz transformation:

$\left(\begin{array}{c} c t \\ x \\ y \end{array}\right)=\left(\begin{array}{ccc} \gamma & \gamma v / c & 0 \\ \gamma v / c & \gamma & 0 \\ 0 & 0 & 1 \end{array}\right)\left(\begin{array}{c} c t^{\prime} \\ x^{\prime} \\ y^{\prime} \end{array}\right), \quad \text { where } \gamma=\frac{1}{\sqrt{1-v^{2} / c^{2}}} .$

A photon is emitted at the spacetime origin. In $S^{\prime}$ it has frequency $\nu^{\prime}$ and propagates at angle $\theta^{\prime}$ to the $x^{\prime}$-axis.

Write down the 4 -momentum of the photon in the frame $S^{\prime}$.

Hence or otherwise find the frequency of the photon as seen in $S$. Show that it propagates at angle $\theta$ to the $x$-axis in $S$, where

$\tan \theta=\frac{\tan \theta^{\prime}}{\gamma\left(1+\frac{v}{c} \sec \theta^{\prime}\right)}$

A light source in $S^{\prime}$ emits photons uniformly in all directions in the $x^{\prime} y^{\prime}$-plane. Show that for large $v$, in $S$ half of the light is concentrated into a narrow cone whose semi-angle $\alpha$ is given by $\cos \alpha=v / c$.

(b) The centre-of-mass frame for a system of relativistic particles in Minkowski space is the frame in which the total relativistic 3-momentum is zero.

Two particles $A_{1}$ and $A_{2}$ of rest masses $m_{1}$ and $m_{2}$ move collinearly with uniform velocities $u_{1}$ and $u_{2}$ respectively, along the $x$-axis of a frame $S$. They collide, coalescing to form a single particle $A_{3}$.

Determine the velocity of the centre-of-mass frame of the system comprising $A_{1}$ and $A_{2}$.

Find the speed of $A_{3}$ in $S$ and show that its rest mass $m_{3}$ is given by

$m_{3}^{2}=m_{1}^{2}+m_{2}^{2}+2 m_{1} m_{2} \gamma_{1} \gamma_{2}\left(1-\frac{u_{1} u_{2}}{c^{2}}\right),$

where $\gamma_{i}=\left(1-u_{i}^{2} / c^{2}\right)^{-1 / 2}$

Paper 4, Section II, B

comment(a) A rigid body $Q$ is made up of $N$ particles of masses $m_{i}$ at positions $\mathbf{r}_{i}(t)$. Let $\mathbf{R}(t)$ denote the position of its centre of mass. Show that the total kinetic energy of $Q$ may be decomposed into $T_{1}$, the kinetic energy of the centre of mass, plus a term $T_{2}$ representing the kinetic energy about the centre of mass.

Suppose now that $Q$ is rotating with angular velocity $\boldsymbol{\omega}$ about its centre of mass. Define the moment of inertia $I$ of $Q$ (about the axis defined by $\boldsymbol{\omega}$ ) and derive an expression for $T_{2}$ in terms of $I$ and $\omega=|\omega|$.

(b) Consider a uniform rod $A B$ of length $2 l$ and mass $M$. Two such rods $A B$ and $B C$ are freely hinged together at $B$. The end $A$ is attached to a fixed point $O$ on a perfectly smooth horizontal floor and $A B$ is able to rotate freely about $O$. The rods are initially at rest, lying in a vertical plane with $C$ resting on the floor and each rod making angle $\alpha$ with the horizontal. The rods subsequently move under gravity in their vertical plane.

Find an expression for the angular velocity of rod $A B$ when it makes angle $\theta$ with the floor. Determine the speed at which the hinge strikes the floor.

Paper 4, Section II, B

comment(a) A particle $P$ of unit mass moves in a plane with polar coordinates $(r, \theta)$. You may assume that the radial and angular components of the acceleration are given by $\left(\ddot{r}-r \dot{\theta}^{2}, r \ddot{\theta}+2 \dot{r} \dot{\theta}\right)$, where the dot denotes $d / d t$. The particle experiences a central force corresponding to a potential $V=V(r)$.

(i) Prove that $l=r^{2} \dot{\theta}$ is constant in time and show that the time dependence of the radial coordinate $r(t)$ is equivalent to the motion of a particle in one dimension $x$ in a potential $V_{\text {eff }}$ given by

$V_{\text {eff }}=V(x)+\frac{l^{2}}{2 x^{2}}$

(ii) Now suppose that $V(r)=-e^{-r}$. Show that if $l^{2}<27 / e^{3}$ then two circular orbits are possible with radii $r_{1}<3$ and $r_{2}>3$. Determine whether each orbit is stable or unstable.

(b) Kepler's first and second laws for planetary motion are the following statements:

K1: the planet moves on an ellipse with a focus at the Sun;

K2: the line between the planet and the Sun sweeps out equal areas in equal times.

Show that K2 implies that the force acting on the planet is a central force.

Show that K2 together with $\mathbf{K 1}$ implies that the force is given by the inverse square law.

[You may assume that an ellipse with a focus at the origin has polar equation $\frac{A}{r}=1+\varepsilon \cos \theta$ with $A>0$ and $0<\varepsilon<1$.]

Paper 3, Section I, D

commentDefine what it means for a group to be cyclic, and for a group to be abelian. Show that every cyclic group is abelian, and give an example to show that the converse is false.

Show that a group homomorphism from the cyclic group $C_{n}$ of order $n$ to a group $G$ determines, and is determined by, an element $g$ of $G$ such that $g^{n}=1$.

Hence list all group homomorphisms from $C_{4}$ to the symmetric group $S_{4}$.

Paper 3, Section I, D

commentState Lagrange's Theorem.

Let $G$ be a finite group, and $H$ and $K$ two subgroups of $G$ such that

(i) the orders of $H$ and $K$ are coprime;

(ii) every element of $G$ may be written as a product $h k$, with $h \in H$ and $k \in K$;

(iii) both $H$ and $K$ are normal subgroups of $G$.

Prove that $G$ is isomorphic to $H \times K$.

Paper 3, Section II, D

commentLet $p$ be a prime number.

Prove that every group whose order is a power of $p$ has a non-trivial centre.

Show that every group of order $p^{2}$ is abelian, and that there are precisely two of them, up to isomorphism.

Paper 3, Section II, D

comment(a) Let $G$ be the dihedral group of order $4 n$, the symmetry group of a regular polygon with $2 n$ sides.

Determine all elements of order 2 in $G$. For each element of order 2 , determine its conjugacy class and the smallest normal subgroup containing it.

(b) Let $G$ be a finite group.

(i) Prove that if $H$ and $K$ are subgroups of $G$, then $K \cup H$ is a subgroup if and only if $H \subseteq K$ or $K \subseteq H$.

(ii) Let $H$ be a proper subgroup of $G$, and write $G \backslash H$ for the elements of $G$ not in $H$. Let $K$ be the subgroup of $G$ generated by $G \backslash H$.

Show that $K=G$.

Paper 3, Section II, D

comment(a) Let $p$ be a prime, and let $G=S L_{2}(p)$ be the group of $2 \times 2$ matrices of determinant 1 with entries in the field $\mathbb{F}_{p}$ of integers $\bmod p$.

(i) Define the action of $G$ on $X=\mathbb{F}_{p} \cup\{\infty\}$ by MÃ¶bius transformations. [You need not show that it is a group action.]

State the orbit-stabiliser theorem.

Determine the orbit of $\infty$ and the stabiliser of $\infty$. Hence compute the order of $S L_{2}(p)$.

(ii) Let

$A=\left(\begin{array}{ll} 1 & 1 \\ 0 & 1 \end{array}\right), \quad B=\left(\begin{array}{ll} 1 & 3 \\ 0 & 1 \end{array}\right)$

Show that $A$ is conjugate to $B$ in $G$ if $p=11$, but not if $p=5$.

(b) Let $G$ be the set of all $3 \times 3$ matrices of the form

$\left(\begin{array}{lll} 1 & a & x \\ 0 & 1 & b \\ 0 & 0 & 1 \end{array}\right)$

where $a, b, x \in \mathbb{R}$. Show that $G$ is a subgroup of the group of all invertible real matrices.

Let $H$ be the subset of $G$ given by matrices with $a=0$. Show that $H$ is a normal subgroup, and that the quotient group $G / H$ is isomorphic to $\mathbb{R}$.

Determine the centre $Z(G)$ of $G$, and identify the quotient group $G / Z(G)$.

Paper 3, Section II, D

comment(a) Let $G$ be a finite group. Show that there exists an injective homomorphism $G \rightarrow \operatorname{Sym}(X)$ to a symmetric group, for some set $X$.

(b) Let $H$ be the full group of symmetries of the cube, and $X$ the set of edges of the cube.

Show that $H$ acts transitively on $X$, and determine the stabiliser of an element of $X$. Hence determine the order of $H$.

Show that the action of $H$ on $X$ defines an injective homomorphism $H \rightarrow \operatorname{Sym}(X)$ to the group of permutations of $X$, and determine the number of cosets of $H$ in $\operatorname{Sym}(X)$.

Is $H$ a normal subgroup of $\operatorname{Sym}(X) ?$ Prove your answer.

Paper 4, Section I, E

commentLet $\left(x_{n}\right)_{n=1}^{\infty}$ be a sequence of real numbers. What does it mean to say that the sequence $\left(x_{n}\right)$ is convergent? What does it mean to say the series $\sum x_{n}$ is convergent? Show that if $\sum x_{n}$ is convergent, then the sequence $\left(x_{n}\right)$ converges to zero. Show that the converse is not necessarily true.

Paper 4, Section I, E

commentLet $m$ and $n$ be positive integers. State what is meant by the greatest common divisor $\operatorname{gcd}(m, n)$ of $m$ and $n$, and show that there exist integers $a$ and $b$ such that $\operatorname{gcd}(m, n)=a m+b n$. Deduce that an integer $k$ divides both $m$ and $n$ only if $k$ divides $\operatorname{gcd}(m, n)$.

Prove (without using the Fundamental Theorem of Arithmetic) that for any positive integer $k, \operatorname{gcd}(k m, k n)=k \operatorname{gcd}(m, n)$.

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

comment(i) What does it mean to say that a set is countable? Show directly from your definition that any subset of a countable set is countable, and that a countable union of countable sets is countable.

(ii) Let $X$ be either $\mathbb{Z}$ or $\mathbb{Q}$. A function $f: X \rightarrow \mathbb{Z}$ is said to be periodic if there exists a positive integer $n$ such that for every $x \in X, f(x+n)=f(x)$. Show that the set of periodic functions from $\mathbb{Z}$ to itself is countable. Is the set of periodic functions $f: \mathbb{Q} \rightarrow \mathbb{Z}$ countable? Justify your answer.

(iii) Show that $\mathbb{R}^{2}$ is not the union of a countable collection of lines.

[You may assume that $\mathbb{R}$ and the power set of $\mathbb{N}$ are uncountable.]

Paper 4, Section II, E

commentLet $p$ be a prime number, and $x, n$ integers with $n \geqslant 1$.

(i) Prove Fermat's Little Theorem: for any integer $x, x^{p} \equiv x(\bmod p)$.

(ii) Show that if $y$ is an integer such that $x \equiv y\left(\bmod p^{n}\right)$, then for every integer $r \geqslant 0$,

$x^{p^{r}} \equiv y^{p^{r}}\left(\bmod p^{n+r}\right)$

Deduce that $x^{p^{n}} \equiv x^{p^{n-1}}\left(\bmod p^{n}\right) .$

(iii) Show that there exists a unique integer $y \in\left\{0,1, \ldots, p^{n}-1\right\}$ such that

$y \equiv x \quad(\bmod p) \quad \text { and } \quad y^{p} \equiv y \quad\left(\bmod p^{n}\right)$

Paper 4, Section II, E

comment(i) Let $N$ and $r$ be integers with $N \geqslant 0, r \geqslant 1$. Let $S$ be the set of $(r+1)$-tuples $\left(n_{0}, n_{1}, \ldots, n_{r}\right)$ of non-negative integers satisfying the equation $n_{0}+\cdots+n_{r}=N$. By mapping elements of $S$ to suitable subsets of $\{1, \ldots, N+r\}$ of size $r$, or otherwise, show that the number of elements of $S$ equals

$\left(\begin{array}{c} N+r \\ r \end{array}\right)$

(ii) State the Inclusion-Exclusion principle.

(iii) Let $a_{0}, \ldots, a_{r}$ be positive integers. Show that the number of $(r+1)$-tuples $\left(n_{i}\right)$ of integers satisfying

$n_{0}+\cdots+n_{r}=N, \quad 0 \leqslant n_{i}<a_{i} \text { for all } i$

$\begin{aligned} \left(\begin{array}{c} N+r \\ r \end{array}\right) &-\sum_{0 \leqslant i \leqslant r}\left(\begin{array}{c} N+r-a_{i} \\ r \end{array}\right)+\sum_{0 \leqslant i<j \leqslant r}\left(\begin{array}{c} N+r-a_{i}-a_{j} \\ r \end{array}\right) \\ &-\sum_{0 \leqslant i<j<k \leqslant r}\left(\begin{array}{c} N+r-a_{i}-a_{j}-a_{k} \\ r \end{array}\right)+\cdots \end{aligned}$

where the binomial coefficient $\left(\begin{array}{c}m \\ r\end{array}\right)$ is defined to be zero if $m<r$.

Paper 4, Section II, E

comment(i) What does it mean to say that a function $f: X \rightarrow Y$ is injective? What does it mean to say that $f$ is surjective? Let $g: Y \rightarrow Z$ be a function. Show that if $g \circ f$ is injective, then so is $f$, and that if $g \circ f$ is surjective, then so is $g$.

(ii) Let $X_{1}, X_{2}$ be two sets. Their product $X_{1} \times X_{2}$ is the set of ordered pairs $\left(x_{1}, x_{2}\right)$ with $x_{i} \in X_{i}(i=1,2)$. Let $p_{i}$ (for $\left.i=1,2\right)$ be the function

$p_{i}: X_{1} \times X_{2} \rightarrow X_{i}, \quad p_{i}\left(x_{1}, x_{2}\right)=x_{i}$

When is $p_{i}$ surjective? When is $p_{i}$ injective?

(iii) Now let $Y$ be any set, and let $f_{1}: Y \rightarrow X_{1}, f_{2}: Y \rightarrow X_{2}$ be functions. Show that there exists a unique $g: Y \rightarrow X_{1} \times X_{2}$ such that $f_{1}=p_{1} \circ g$ and $f_{2}=p_{2} \circ g$.

Show that if $f_{1}$ or $f_{2}$ is injective, then $g$ is injective. Is the converse true? Justify your answer.

Show that if $g$ is surjective then both $f_{1}$ and $f_{2}$ are surjective. Is the converse true? Justify your answer.

Paper 2, Section I, F

comment(i) Let $X$ be a random variable. Use Markov's inequality to show that

$\mathbb{P}(X \geqslant k) \leqslant \mathbb{E}\left(e^{t X}\right) e^{-k t}$

for all $t \geqslant 0$ and real $k$.

(ii) Calculate $\mathbb{E}\left(e^{t X}\right)$ in the case where $X$ is a Poisson random variable with parameter $\lambda=1$. Using the inequality from part (i) with a suitable choice of $t$, prove that

$\frac{1}{k !}+\frac{1}{(k+1) !}+\frac{1}{(k+2) !}+\ldots \leqslant\left(\frac{e}{k}\right)^{k}$

for all $k \geqslant 1$.

Paper 2, Section I, F

commentLet $X$ be a random variable with mean $\mu$ and variance $\sigma^{2}$. Let

$G(a)=\mathbb{E}\left[(X-a)^{2}\right]$

Show that $G(a) \geqslant \sigma^{2}$ for all $a$. For what value of $a$ is there equality?

Let

$H(a)=\mathbb{E}[|X-a|]$

Supposing that $X$ has probability density function $f$, express $H(a)$ in terms of $f$. Show that $H$ is minimised when $a$ is such that $\int_{-\infty}^{a} f(x) d x=1 / 2$.

Paper 2, Section II, F

commentLet $\Omega$ be the sample space of a probabilistic experiment, and suppose that the sets $B_{1}, B_{2}, \ldots, B_{k}$ are a partition of $\Omega$ into events of positive probability. Show that

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

for any event $A$ of positive probability.

A drawer contains two coins. One is an unbiased coin, which when tossed, is equally likely to turn up heads or tails. The other is a biased coin, which will turn up heads with probability $p$ and tails with probability $1-p$. One coin is selected (uniformly) at random from the drawer. Two experiments are performed:

(a) The selected coin is tossed $n$ times. Given that the coin turns up heads $k$ times and tails $n-k$ times, what is the probability that the coin is biased?

(b) The selected coin is tossed repeatedly until it turns up heads $k$ times. Given that the coin is tossed $n$ times in total, what is the probability that the coin is biased?

Paper 2, Section II, F

commentLet $X$ be a geometric random variable with $\mathbb{P}(X=1)=p$. Derive formulae for $\mathbb{E}(X)$ and $\operatorname{Var}(X)$ in terms of $p .$

A jar contains $n$ balls. Initially, all of the balls are red. Every minute, a ball is drawn at random from the jar, and then replaced with a green ball. Let $T$ be the number of minutes until the jar contains only green balls. Show that the expected value of $T$ is $n \sum_{i=1}^{n} 1 / i$. What is the variance of $T ?$

Paper 2, Section II, F

commentLet $X$ be a random variable taking values in the non-negative integers, and let $G$ be the probability generating function of $X$. Assuming $G$ is everywhere finite, show that

$G^{\prime}(1)=\mu \text { and } G^{\prime \prime}(1)=\sigma^{2}+\mu^{2}-\mu$

where $\mu$ is the mean of $X$ and $\sigma^{2}$ is its variance. [You may interchange differentiation and expectation without justification.]

Consider a branching process where individuals produce independent random numbers of offspring with the same distribution as $X$. Let $X_{n}$ be the number of individuals in the $n$-th generation, and let $G_{n}$ be the probability generating function of $X_{n}$. Explain carefully why

$G_{n+1}(t)=G_{n}(G(t))$

Assuming $X_{0}=1$, compute the mean of $X_{n}$. Show that

$\operatorname{Var}\left(X_{n}\right)=\sigma^{2} \frac{\mu^{n-1}\left(\mu^{n}-1\right)}{\mu-1}$

Suppose $\mathbb{P}(X=0)=3 / 7$ and $\mathbb{P}(X=3)=4 / 7$. Compute the probability that the population will eventually become extinct. You may use standard results on branching processes as long as they are clearly stated.

Paper 2, Section II, F

commentLet $Z$ be an exponential random variable with parameter $\lambda=1$. Show that

$\mathbb{P}(Z>s+t \mid Z>s)=\mathbb{P}(Z>t)$

for any $s, t \geqslant 0$.

Let $Z_{\text {int }}=\lfloor Z\rfloor$ be the greatest integer less than or equal to $Z$. What is the probability mass function of $Z_{\text {int }}$ ? Show that $\mathbb{E}\left(Z_{\text {int }}\right)=\frac{1}{e-1}$.

Let $Z_{\mathrm{frac}}=Z-Z_{\mathrm{int}}$ be the fractional part of $Z$. What is the density of $Z_{\mathrm{frac}}$ ?

Show that $Z_{\text {int }}$ and $Z_{\text {frac }}$ are independent.

Paper 3, Section $I$, C

commentState a necessary and sufficient condition for a vector field $\mathbf{F}$ on $\mathbb{R}^{3}$ to be conservative.

Check that the field

$\mathbf{F}=\left(2 x \cos y-2 z^{3}, 3+2 y e^{z}-x^{2} \sin y, y^{2} e^{z}-6 x z^{2}\right)$

is conservative and find a scalar potential for $\mathbf{F}$.

Paper 3, Section I, C

commentThe curve $C$ is given by

$\mathbf{r}(t)=\left(\sqrt{2} e^{t},-e^{t} \sin t, e^{t} \cos t\right), \quad-\infty<t<\infty$

(i) Compute the arc length of $C$ between the points with $t=0$ and $t=1$.

(ii) Derive an expression for the curvature of $C$ as a function of arc length $s$ measured from the point with $t=0$.

Paper 3, Section II, C

comment(a) Prove that

$\nabla \times(\mathbf{F} \times \mathbf{G})=\mathbf{F}(\nabla \cdot \mathbf{G})-\mathbf{G}(\nabla \cdot \mathbf{F})+(\mathbf{G} \cdot \nabla) \mathbf{F}-(\mathbf{F} \cdot \nabla) \mathbf{G}$

(b) State the divergence theorem for a vector field $\mathbf{F}$ in a closed region $\Omega \subset \mathbb{R}^{3}$ bounded by $\partial \Omega$.

For a smooth vector field $\mathbf{F}$ and a smooth scalar function $g$ prove that

$\int_{\Omega} \mathbf{F} \cdot \nabla g+g \nabla \cdot \mathbf{F} d V=\int_{\partial \Omega} g \mathbf{F} \cdot \mathbf{n} d S,$

where $\mathbf{n}$ is the outward unit normal on the surface $\partial \Omega$.

Use this identity to prove that the solution $u$ to the Laplace equation $\nabla^{2} u=0$ in $\Omega$ with $u=f$ on $\partial \Omega$ is unique, provided it exists.

Paper 3, Section II, C

commentIf $\mathbf{E}$ and $\mathbf{B}$ are vectors in $\mathbb{R}^{3}$, show that

$T_{i j}=E_{i} E_{j}+B_{i} B_{j}-\frac{1}{2} \delta_{i j}\left(E_{k} E_{k}+B_{k} B_{k}\right)$

is a second rank tensor.

Now assume that $\mathbf{E}(\mathbf{x}, t)$ and $\mathbf{B}(\mathbf{x}, t)$ obey Maxwell's equations, which in suitable units read

$\begin{aligned} &\nabla \cdot \mathbf{E}=\rho \\ &\nabla \cdot \mathbf{B}=0 \\ &\nabla \times \mathbf{E}=-\frac{\partial \mathbf{B}}{\partial t} \\ &\nabla \times \mathbf{B}=\mathbf{J}+\frac{\partial \mathbf{E}}{\partial t} \end{aligned}$

where $\rho$ is the charge density and $\mathbf{J}$ the current density. Show that

$\frac{\partial}{\partial t}(\mathbf{E} \times \mathbf{B})=\mathbf{M}-\rho \mathbf{E}-\mathbf{J} \times \mathbf{B} \quad \text { where } \quad M_{i}=\frac{\partial T_{i j}}{\partial x_{j}}$

Paper 3, Section II, C

commentConsider the bounded surface $S$ that is the union of $x^{2}+y^{2}=4$ for $-2 \leqslant z \leqslant 2$ and $(4-z)^{2}=x^{2}+y^{2}$ for $2 \leqslant z \leqslant 4$. Sketch the surface.

Using suitable parametrisations for the two parts of $S$, calculate the integral

$\int_{S}(\nabla \times \mathbf{F}) \cdot d \mathbf{S}$

for $\mathbf{F}=y z^{2} \mathbf{i}$.

Check your result using Stokes's Theorem.

Paper 3, Section II, C

commentGive an explicit formula for $\mathcal{J}$ which makes the following result hold:

$\int_{D} f d x d y d z=\int_{D^{\prime}} \phi|\mathcal{J}| d u d v d w$

where the region $D$, with coordinates $x, y, z$, and the region $D^{\prime}$, with coordinates $u, v, w$, are in one-to-one correspondence, and

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

Explain, in outline, why this result holds.

Let $D$ be the region in $\mathbb{R}^{3}$ defined by $4 \leqslant x^{2}+y^{2}+z^{2} \leqslant 9$ and $z \geqslant 0$. Sketch the region and employ a suitable transformation to evaluate the integral

$\int_{D}\left(x^{2}+y^{2}\right) d x d y d z$

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

comment(a) State de Moivre's theorem and use it to derive a formula for the roots of order $n$ of a complex number $z=a+i b$. Using this formula compute the cube roots of $z=-8$.

(b) Consider the equation $|z+3 i|=3|z|$ for $z \in \mathbb{C}$. Give a geometric description of the set $S$ of solutions and sketch $S$ as a subset of the complex plane.

Paper 1, Section I, A

commentLet $A$ be a real $3 \times 3$ matrix.

(i) For $B=R_{1} A$ with

$R_{1}=\left(\begin{array}{ccc} 1 & 0 & 0 \\ 0 & \cos \theta_{1} & -\sin \theta_{1} \\ 0 & \sin \theta_{1} & \cos \theta_{1} \end{array}\right)$

find an angle $\theta_{1}$ so that the element $b_{31}=0$, where $b_{i j}$ denotes the $i j^{\text {th }}$entry of the matrix $B$.

(ii) For $C=R_{2} B$ with $b_{31}=0$ and

$R_{2}=\left(\begin{array}{ccc} \cos \theta_{2} & -\sin \theta_{2} & 0 \\ \sin \theta_{2} & \cos \theta_{2} & 0 \\ 0 & 0 & 1 \end{array}\right)$

show that $c_{31}=0$ and find an angle $\theta_{2}$ so that $c_{21}=0$.

(iii) For $D=R_{3} C$ with $c_{31}=c_{21}=0$ and

$R_{3}=\left(\begin{array}{ccc} 1 & 0 & 0 \\ 0 & \cos \theta_{3} & -\sin \theta_{3} \\ 0 & \sin \theta_{3} & \cos \theta_{3} \end{array}\right)$

show that $d_{31}=d_{21}=0$ and find an angle $\theta_{3}$ so that $d_{32}=0$.

(iv) Deduce that any real $3 \times 3$ matrix can be written as a product of an orthogonal matrix and an upper triangular matrix.

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

commentLet $\mathbf{x}$ and $\mathbf{y}$ be non-zero vectors in $\mathbb{R}^{n}$. What is meant by saying that $\mathbf{x}$ and $\mathbf{y}$ are linearly independent? What is the dimension of the subspace of $\mathbb{R}^{n}$ spanned by $\mathbf{x}$ and $\mathbf{y}$ if they are (1) linearly independent, (2) linearly dependent?

Define the scalar product $\mathbf{x} \cdot \mathbf{y}$ for $\mathbf{x}, \mathbf{y} \in \mathbb{R}^{n}$. Define the corresponding norm $\|\mathbf{x}\|$ of $\mathbf{x} \in \mathbb{R}^{n}$. State and prove the Cauchy-Schwarz inequality, and deduce the triangle inequality. Under what condition does equality hold in the Cauchy-Schwarz inequality?

Let $\mathbf{x}, \mathbf{y}, \mathbf{z}$ be unit vectors in $\mathbb{R}^{3}$. Let

$S=\mathbf{x} \cdot \mathbf{y}+\mathbf{y} \cdot \mathbf{z}+\mathbf{z} \cdot \mathbf{x}$

Show that for any fixed, linearly independent vectors $\mathbf{x}$ and $\mathbf{y}$, the minimum of $S$ over $\mathbf{z}$ is attained when $\mathbf{z}=\lambda(\mathbf{x}+\mathbf{y})$ for some $\lambda \in \mathbb{R}$, and that for this value of $\lambda$ we have

(i) $\lambda \leqslant-\frac{1}{2}$ (for any choice of $\mathbf{x}$ and $\left.\mathbf{y}\right)$;

(ii) $\lambda=-1$ and $S=-\frac{3}{2}$ in the case where $\mathbf{x} \cdot \mathbf{y}=\cos \frac{2 \pi}{3}$.

Paper 1, Section II, $6 \mathrm{~A}$

commentDefine the kernel and the image of a linear map $\alpha$ from $\mathbb{R}^{m}$ to $\mathbb{R}^{n}$.

Let $\left\{\mathbf{e}_{1}, \mathbf{e}_{2}, \ldots, \mathbf{e}_{m}\right\}$ be a basis of $\mathbb{R}^{m}$ and $\left\{\mathbf{f}_{1}, \mathbf{f}_{2}, \ldots, \mathbf{f}_{n}\right\}$ a basis of $\mathbb{R}^{n}$. Explain how to represent $\alpha$ by a matrix $A$ relative to the given bases.

A second set of bases $\left\{\mathbf{e}_{1}^{\prime}, \mathbf{e}_{2}^{\prime}, \ldots, \mathbf{e}_{m}^{\prime}\right\}$ and $\left\{\mathbf{f}_{1}^{\prime}, \mathbf{f}_{2}^{\prime}, \ldots, \mathbf{f}_{n}^{\prime}\right\}$ is now used to represent $\alpha$ by a matrix $A^{\prime}$. Relate the elements of $A^{\prime}$ to the elements of $A$.

Let $\beta$ be a linear map from $\mathbb{R}^{2}$ to $\mathbb{R}^{3}$ defined by

$\beta\left(\begin{array}{l} 1 \\ 1 \end{array}\right)=\left(\begin{array}{l} 1 \\ 2 \\ 3 \end{array}\right), \quad \beta\left(\begin{array}{c} 1 \\ -1 \end{array}\right)=\left(\begin{array}{l} 6 \\ 4 \\ 2 \end{array}\right)$

Either find one or more $\mathbf{x}$ in $\mathbb{R}^{2}$ such that

$\beta \mathbf{x}=\left(\begin{array}{c} 1 \\ -2 \\ 1 \end{array}\right)$

or explain why one cannot be found.

Let $\gamma$ be a linear map from $\mathbb{R}^{3}$ to $\mathbb{R}^{2}$ defined by

$\gamma\left(\begin{array}{l} 1 \\ 2 \\ 0 \end{array}\right)=\left(\begin{array}{l} 1 \\ 3 \end{array}\right), \quad \gamma\left(\begin{array}{l} 0 \\ 1 \\ 1 \end{array}\right)=\left(\begin{array}{c} -2 \\ 1 \end{array}\right), \quad \gamma\left(\begin{array}{l} 0 \\ 1 \\ 0 \end{array}\right)=\left(\begin{array}{l} 0 \\ 1 \end{array}\right)$

Find the kernel of $\gamma$.

Paper 1, Section II, B

comment(a) Let $A$ and $A^{\prime}$ be the matrices of a linear map $L$ on $\mathbb{C}^{2}$ relative to bases $\mathcal{B}$ and $\mathcal{B}^{\prime}$ respectively. In this question you may assume without proof that $A$ and $A^{\prime}$ are similar.

(i) State how the matrix $A$ of $L$ relative to the basis $\mathcal{B}=\left\{\mathbf{e}_{1}, \mathbf{e}_{2}\right\}$ is constructed from $L$ and $\mathcal{B}$. Also state how $A$ may be used to compute $L \mathbf{v}$ for any $\mathbf{v} \in \mathbb{C}^{2}$.

(ii) Show that $A$ and $A^{\prime}$ have the same characteristic equation.

(iii) Show that for any $k \neq 0$ the matrices

$\left(\begin{array}{ll} a & c \\ b & d \end{array}\right) \text { and }\left(\begin{array}{cc} a & c / k \\ b k & d \end{array}\right)$

are similar. [Hint: if $\left\{\mathbf{e}_{1}, \mathbf{e}_{2}\right\}$ is a basis then so is $\left\{k \mathbf{e}_{1}, \mathbf{e}_{2}\right\}$.]

(b) Using the results of (a), or otherwise, prove that any $2 \times 2$ complex matrix $M$ with equal eigenvalues is similar to one of

$\left(\begin{array}{ll} a & 0 \\ 0 & a \end{array}\right) \text { and }\left(\begin{array}{ll} a & 1 \\ 0 & a \end{array}\right) \text { with } a \in \mathbb{C} .$

(c) Consider the matrix

$B(r)=\frac{1}{2}\left(\begin{array}{ccc} 1+r & 1-r & 1 \\ 1-r & 1+r & -1 \\ -1 & 1 & 2 r \end{array}\right)$

Show that there is a real value $r_{0}>0$ such that $B\left(r_{0}\right)$ is an orthogonal matrix. Show that $B\left(r_{0}\right)$ is a rotation and find the axis and angle of the rotation.

Paper 1, Section II, B

(a) Let $\lambda_{1}, \ldots, \lambda_{d}$ be distinct eigenvalues of an $n \times n$