# Part IA, 2021

### Jump to course

Paper 1, Section I, F

commentState and prove the Bolzano-Weierstrass theorem.

Consider a bounded sequence $\left(x_{n}\right)$. Prove that if every convergent subsequence of $\left(x_{n}\right)$ converges to the same limit $L$ then $\left(x_{n}\right)$ converges to $L$.

Paper 1, Section I, F

commentState and prove the alternating series test. Hence show that the series $\sum_{n=1}^{\infty} \frac{(-1)^{n+1}}{n}$ converges. Show also that

$\frac{7}{12} \leqslant \sum_{n=1}^{\infty} \frac{(-1)^{n+1}}{n} \leqslant \frac{47}{60}$

Paper 1, Section II, F

comment(a) Let $\sum_{n=0}^{\infty} a_{n} z^{n}$ be a power series with $a_{n} \in \mathbb{C}$. Show that there exists $R \in[0, \infty]$ (called the radius of convergence) such that the series is absolutely convergent when $|z|<R$ but is divergent when $|z|>R$.

Suppose that the radius of convergence of the series $\sum_{n=0}^{\infty} a_{n} z^{n}$ is $R=2$. For a fixed positive integer $k$, find the radii of convergence of the following series. [You may assume that $\lim _{n \rightarrow \infty}\left|a_{n}\right|^{1 / n}$ exists.] (i) $\sum_{n=0}^{\infty} a_{n}^{k} z^{n}$. (ii) $\sum_{n=0}^{\infty} a_{n} z^{k n}$. (iii) $\sum_{n=0}^{\infty} a_{n} z^{n^{2}}$.

(b) Suppose that there exist values of $z$ for which $\sum_{n=0}^{\infty} b_{n} e^{n z}$ converges and values for which it diverges. Show that there exists a real number $S$ such that $\sum_{n=0}^{\infty} b_{n} e^{n z}$ diverges whenever $\operatorname{Re}(z)>S$ and converges whenever $\operatorname{Re}(z)<S$.

Determine the set of values of $z$ for which

$\sum_{n=0}^{\infty} \frac{2^{n} e^{i n z}}{(n+1)^{2}}$

converges.

Paper 1, Section II, F

commentLet $f: \mathbb{R} \rightarrow \mathbb{R}$ be $n$-times differentiable, for some $n>0$.

(a) State and prove Taylor's theorem for $f$, with the Lagrange form of the remainder. [You may assume Rolle's theorem.]

(b) Suppose that $f: \mathbb{R} \rightarrow \mathbb{R}$ is an infinitely differentiable function such that $f(0)=1$ and $f^{\prime}(0)=0$, and satisfying the differential equation $f^{\prime \prime}(x)=-f(x)$. Prove carefully that

$f(x)=\sum_{k=0}^{\infty}(-1)^{k} \frac{x^{2 k}}{(2 k) !}$

Paper 1, Section II, F

commentLet $f:[a, b] \rightarrow \mathbb{R}$ be a continuous function.

(a) Let $m=\min _{x \in[a, b]} f(x)$ and $M=\max _{x \in[a, b]} f(x)$. If $g:[a, b] \rightarrow \mathbb{R}$ is a positive continuous function, prove that

$m \int_{a}^{b} g(x) d x \leqslant \int_{a}^{b} f(x) g(x) d x \leqslant M \int_{a}^{b} g(x) d x$

directly from the definition of the Riemann integral.

(b) Let $f:[0,1] \rightarrow \mathbb{R}$ be a continuous function. Show that

$\int_{0}^{1 / \sqrt{n}} n f(x) e^{-n x} d x \rightarrow f(0)$

as $n \rightarrow \infty$, and deduce that

$\int_{0}^{1} n f(x) e^{-n x} d x \rightarrow f(0)$

as $n \rightarrow \infty$

Paper 1, Section II, F

comment(a) State the intermediate value theorem. Show that if $f: \mathbb{R} \rightarrow \mathbb{R}$ is a continuous bijection and $x_{1}<x_{2}<x_{3}$ then either $f\left(x_{1}\right)<f\left(x_{2}\right)<f\left(x_{3}\right)$ or $f\left(x_{1}\right)>f\left(x_{2}\right)>f\left(x_{3}\right)$. Deduce that $f$ is either strictly increasing or strictly decreasing.

(b) Let $f: \mathbb{R} \rightarrow \mathbb{R}$ and $g: \mathbb{R} \rightarrow \mathbb{R}$ be functions. Which of the following statements are true, and which can be false? Give a proof or counterexample as appropriate.

(i) If $f$ and $g$ are continuous then $f \circ g$ is continuous.

(ii) If $g$ is strictly increasing and $f \circ g$ is continuous then $f$ is continuous.

(iii) If $f$ is continuous and a bijection then $f^{-1}$ is continuous.

(iv) If $f$ is differentiable and a bijection then $f^{-1}$ is differentiable.

Paper 2, Section I, A

commentLet $y_{1}$ and $y_{2}$ be two linearly independent solutions to the differential equation

$\frac{\mathrm{d}^{2} y}{\mathrm{~d} x^{2}}+p(x) \frac{\mathrm{d} y}{\mathrm{~d} x}+q(x) y=0 .$

Show that the Wronskian $W=y_{1} y_{2}^{\prime}-y_{2} y_{1}^{\prime}$ satisfies

$\frac{\mathrm{d} W}{\mathrm{~d} x}+p W=0 .$

Deduce that if $y_{2}\left(x_{0}\right)=0$ then

$y_{2}(x)=y_{1}(x) \int_{x_{0}}^{x} \frac{W(t)}{y_{1}(t)^{2}} \mathrm{~d} t .$

Given that $y_{1}(x)=x^{3}$ satisfies the equation

$x^{2} \frac{\mathrm{d}^{2} y}{\mathrm{~d} x^{2}}-x \frac{\mathrm{d} y}{\mathrm{~d} x}-3 y=0$

find the solution which satisfies $y(1)=0$ and $y^{\prime}(1)=1$.

Paper 2, Section I, A

commentSolve the difference equation

$y_{n+2}-4 y_{n+1}+4 y_{n}=n$

subject to the initial conditions $y_{0}=1$ and $y_{1}=0$.

Paper 2, Section II, A

commentBy means of the change of variables $\eta=x-t$ and $\xi=x+t$, show that the wave equation for $u=u(x, t)$

$\frac{\partial^{2} u}{\partial x^{2}}-\frac{\partial^{2} u}{\partial t^{2}}=0$

is equivalent to the equation

$\frac{\partial^{2} U}{\partial \eta \partial \xi}=0$

where $U(\eta, \xi)=u(x, t)$. Hence show that the solution to $(*)$ on $x \in \mathbf{R}$ and $t>0$, subject to the initial conditions

$u(x, 0)=f(x), \quad \frac{\partial u}{\partial t}(x, 0)=g(x)$

$u(x, t)=\frac{1}{2}[f(x-t)+f(x+t)]+\frac{1}{2} \int_{x-t}^{x+t} g(y) \mathrm{d} y$

Deduce that if $f(x)=0$ and $g(x)=0$ on the interval $\left|x-x_{0}\right|>r$ then $u(x, t)=0$ on $\left|x-x_{0}\right|>r+t$.

Suppose now that $y=y(x, t)$ is a solution to the wave equation $(*)$ on the finite interval $0<x<L$ and obeys the boundary conditions

$y(0, t)=y(L, t)=0$

for all $t$. The energy is defined by

$E(t)=\frac{1}{2} \int_{0}^{L}\left[\left(\frac{\partial y}{\partial x}\right)^{2}+\left(\frac{\partial y}{\partial t}\right)^{2}\right] \mathrm{d} x$

By considering $\mathrm{d} E / \mathrm{d} t$, or otherwise, show that the energy remains constant in time.

Paper 2, Section II, A

commentFor a linear, second order differential equation define the terms ordinary point, singular point and regular singular point.

For $a, b \in \mathbb{R}$ and $b \notin \mathbb{Z}$ consider the following differential equation

$x \frac{\mathrm{d}^{2} y}{\mathrm{~d} x^{2}}+(b-x) \frac{\mathrm{d} y}{\mathrm{~d} x}-a y=0 .$

Find coefficients $c_{m}(a, b)$ such that the function $y_{1}=M(x, a, b)$, where

$M(x, a, b)=\sum_{m=0}^{\infty} c_{m}(a, b) x^{m}$

satisfies $(*)$. By making the substitution $y=x^{1-b} u(x)$, or otherwise, find a second linearly independent solution of the form $y_{2}=x^{1-b} M(x, \alpha, \beta)$ for suitable $\alpha, \beta$.

Suppose now that $b=1$. By considering a limit of the form

$\lim _{b \rightarrow 1} \frac{y_{2}-y_{1}}{b-1}$

or otherwise, obtain two linearly independent solutions to $(*)$ in terms of $M$ and derivatives thereof.

Paper 2, Section II, A

commentFor an $n \times n$ matrix $A$, define the matrix exponential by

$\exp (A)=\sum_{m=0}^{\infty} \frac{A^{m}}{m !}$

where $A^{0} \equiv I$, with $I$ being the $n \times n$ identity matrix. [You may assume that $\exp ((s+t) A)=\exp (s A) \exp (t A)$ for real numbers $s, t$ and you do not need to consider issues of convergence.] Show that

$\frac{\mathrm{d}}{\mathrm{d} t} \exp (t A)=A \exp (t A)$

Deduce that the unique solution to the initial value problem

$\frac{\mathrm{d} \mathbf{y}}{\mathrm{d} t}=A \mathbf{y}, \quad \mathbf{y}(0)=\mathbf{y}_{0}, \quad \text { where } \mathbf{y}(t)=\left(\begin{array}{c} y_{1}(t) \\ \vdots \\ y_{n}(t) \end{array}\right)$

is $\mathbf{y}(t)=\exp (t A) \mathbf{y}_{0}$.

Let $\mathbf{x}=\mathbf{x}(t)$ and $\mathbf{f}=\mathbf{f}(t)$ be vectors of length $n$ and $A$ a real $n \times n$ matrix. By considering a suitable integrating factor, show that the unique solution to

$\frac{\mathrm{d} \mathbf{x}}{\mathrm{d} t}-A \mathbf{x}=\mathbf{f}, \quad \mathbf{x}(0)=\mathbf{x}_{0}$

is given by

$\mathbf{x}(t)=\exp (t A) \mathbf{x}_{0}+\int_{0}^{t} \exp [(t-s) A] \mathbf{f}(s) \mathrm{d} s$

Hence, or otherwise, solve the system of differential equations $(*)$ when

$A=\left(\begin{array}{ccc} 2 & 2 & -2 \\ 5 & 1 & -3 \\ 1 & 5 & -3 \end{array}\right), \quad \mathbf{f}(t)=\left(\begin{array}{c} \sin t \\ 3 \sin t \\ 0 \end{array}\right), \quad \mathbf{x}_{0}=\left(\begin{array}{l} 1 \\ 1 \\ 2 \end{array}\right)$

[Hint: Compute $A^{2}$ and show that $\left.A^{3}=0 .\right]$

Paper 2, Section II, A

commentThe function $\theta=\theta(t)$ takes values in the interval $(-\pi, \pi]$ and satisfies the differential equation

$\frac{\mathrm{d}^{2} \theta}{\mathrm{d} t^{2}}+(\lambda-2 \mu) \sin \theta+\frac{2 \mu \sin \theta}{\sqrt{5+4 \cos \theta}}=0$

where $\lambda$ and $\mu$ are positive constants.

Let $\omega=\dot{\theta}$. Express $(*)$ in terms of a pair of first order differential equations in $(\theta, \omega)$. Show that if $3 \lambda<4 \mu$ then there are three fixed points in the region $0 \leqslant \theta \leqslant \pi .$

Classify all the fixed points of the system in the case $3 \lambda<4 \mu$. Sketch the phase portrait in the case $\lambda=1$ and $\mu=3 / 2$.

Comment briefly on the case when $3 \lambda>4 \mu$.

Paper 4, Section I, C

commentA rigid body composed of $N$ particles with positions $\mathbf{x}_{i}$, and masses $m_{i}(i=$ $1,2, \ldots, N)$, rotates about the $z$-axis with constant angular speed $\omega$. Show that the body's kinetic energy is $T=\frac{1}{2} I \omega^{2}$, where you should give an expression for the moment of inertia $I$ in terms of the particle masses and positions.

Consider a solid cuboid of uniform density, mass $M$, and dimensions $2 a \times 2 b \times 2 c$. Choose coordinate axes so that the cuboid is described by the points $(x, y, z)$ with $-a \leqslant x \leqslant a,-b \leqslant y \leqslant b$, and $-c \leqslant z \leqslant c$. In terms of $M, a$, $b$, and $c$, find the cuboid's moment of inertia $I$ for rotations about the $z$-axis.

Paper 4, Section I, C

commentA trolley travels with initial speed $v_{0}$ along a frictionless, horizontal, linear track. It slows down by ejecting gas in the direction of motion. The gas is emitted at a constant mass ejection rate $\alpha$ and with constant speed $u$ relative to the trolley. The trolley and its supply of gas initially have a combined mass of $m_{0}$. How much time is spent ejecting gas before the trolley stops? [Assume that the trolley carries sufficient gas.]

Paper 4, Section II, 10C

comment(a) A mass $m$ is acted upon by a central force

$\mathbf{F}=-\frac{k m}{r^{3}} \mathbf{r}$

where $k$ is a positive constant and $\mathbf{r}$ is the displacement of the mass from the origin. Show that the angular momentum and energy of the mass are conserved.

(b) Working in plane polar coordinates $(r, \theta)$, or otherwise, show that the distance $r=|\mathbf{r}|$ between the mass and the origin obeys the following differential equation

$\ddot{r}=-\frac{k}{r^{2}}+\frac{h^{2}}{r^{3}}$

where $h$ is the angular momentum per unit mass.

(c) A satellite is initially in a circular orbit of radius $r_{1}$ and experiences the force described above. At $\theta=0$ and time $t_{1}$, the satellite emits a short rocket burst putting it on an elliptical orbit with its closest distance to the centre $r_{1}$ and farthest distance $r_{2}$. When $\theta=\pi$ and the time is $t_{2}$, the satellite reaches the farthest distance and a second short rocket burst puts the rocket on a circular orbit of radius $r_{2}$. (See figure.) [Assume that the duration of the rocket bursts is negligible.]

(i) Show that the satellite's angular momentum per unit mass while in the elliptical orbit is

$h=\sqrt{\frac{C k r_{1} r_{2}}{r_{1}+r_{2}}}$

where $C$ is a number you should determine.

(ii) What is the change in speed as a result of the rocket burst at time $t_{1}$ ? And what is the change in speed at $t_{2}$ ?

(iii) Given that the elliptical orbit can be described by

$r=\frac{h^{2}}{k(1+e \cos \theta)}$

where $e$ is the eccentricity of the orbit, find $t_{2}-t_{1}$ in terms of $r_{1}, r_{2}$, and $k$. [Hint: The area of an ellipse is equal to $\pi a b$, where $a$ and b are its semi-major and semi-minor axes; these are related to the eccentricity by $\left.e=\sqrt{1-\frac{b^{2}}{a^{2}}} .\right]$

Paper 4, Section II, C

commentWrite down the expression for the momentum of a particle of rest mass $m$, moving with velocity $\mathbf{v}$ where $v=|\mathbf{v}|$ is near the speed of light $c$. Write down the corresponding 4-momentum.

Such a particle experiences a force $\mathbf{F}$. Why is the following expression for the particle's acceleration,

$\mathbf{a}=\frac{\mathbf{F}}{m}$

not generally correct? Show that the force can be written as follows

$\mathbf{F}=m \gamma\left(\frac{\gamma^{2}}{c^{2}}(\mathbf{v} \cdot \mathbf{a}) \mathbf{v}+\mathbf{a}\right)$

Invert this expression to find the particle's acceleration as the sum of two vectors, one parallel to $\mathbf{F}$ and one parallel to $\mathbf{v}$.

A particle with rest mass $m$ and charge $q$ is in the presence of a constant electric field $\mathbf{E}$ which exerts a force $\mathbf{F}=q \mathbf{E}$ on the particle. If the particle is at rest at $t=0$, its motion will be in the direction of $\mathbf{E}$ for $t>0$. Determine the particle's speed for $t>0$. How does the velocity behave as $t \rightarrow \infty$ ?

[Hint: You may find that trigonometric substitution is helpful in evaluating an integral.]

Paper 4, Section II, C

commentConsider an inertial frame of reference $S$ and a frame of reference $S^{\prime}$ which is rotating with constant angular velocity $\boldsymbol{\omega}$ relative to $S$. Assume that the two frames have a common origin $O$.

Let $\mathbf{A}$ be any vector. Explain why the derivative of $\mathbf{A}$ in frame $S$ is related to its derivative in $S^{\prime}$ by the following equation

$\left(\frac{d \mathbf{A}}{d t}\right)_{S}=\left(\frac{d \mathbf{A}}{d t}\right)_{S^{\prime}}+\omega \times \mathbf{A} .$

[Hint: It may be useful to use Cartesian basis vectors in both frames.]

Let $\mathbf{r}(t)$ be the position vector of a particle, measured from $O$. Derive the expression relating the particle's acceleration as observed in $S,\left(\frac{d^{2} \mathbf{r}}{d t^{2}}\right)_{S}$, to the acceleration observed in $S^{\prime},\left(\frac{d^{2} \mathbf{r}}{d t^{2}}\right)_{S^{\prime}}$, written in terms of $\mathbf{r}, \boldsymbol{\omega}$ and $\left(\frac{d \mathbf{r}}{d t}\right)_{S^{\prime}}$

A small bead of mass $m$ is threaded on a smooth, rigid, circular wire of radius $R$. At any given instant, the wire hangs in a vertical plane with respect to a downward gravitational acceleration $\mathbf{g}$. The wire is rotating with constant angular velocity $\boldsymbol{\omega}$ about its vertical diameter. Let $\theta(t)$ be the angle between the downward vertical and the radial line going from the centre of the hoop to the bead.

(i) Show that $\theta(t)$ satisfies the following equation of motion

$\ddot{\theta}=\left(\omega^{2} \cos \theta-\frac{g}{R}\right) \sin \theta .$

(ii) Find any equilibrium angles and determine their stability.

(iii) Find the force of the wire on the bead as a function of $\theta$ and $\dot{\theta}$.

Paper 4, Section II, C

commentA particle of mass $m$ follows a one-dimensional trajectory $x(t)$ in the presence of a variable force $F(x, t)$. Write down an expression for the work done by this force as the particle moves from $x\left(t_{a}\right)=a$ to $x\left(t_{b}\right)=b$. Assuming that this is the only force acting on the particle, show that the work done by the force is equal to the change in the particle's kinetic energy.

What does it mean if a force is said to be conservative?

A particle moves in a force field given by

$F(x)=\left\{\begin{array}{cc} -F_{0} e^{-x / \lambda} & x \geqslant 0 \\ F_{0} e^{x / \lambda} & x<0 \end{array}\right.$

where $F_{0}$ and $\lambda$ are positive constants. The particle starts at the origin $x=0$ with initial velocity $v_{0}>0$. Show that, as the particle's position increases from $x=0$ to larger $x>0$, the particle's velocity $v$ at position $x$ is given by

$v(x)=\sqrt{v_{0}^{2}+v_{e}^{2}\left(e^{-|x| / \lambda}-1\right)}$

where you should determine $v_{e}$. What determines whether the particle will escape to infinity or oscillate about the origin? Sketch $v(x)$ versus $x$ for each of these cases, carefully identifying any significant velocities or positions.

In the case of oscillatory motion, find the period of oscillation in terms of $v_{0}, v_{e}$, and $\lambda$. [Hint: You may use the fact that

$\int_{w}^{1} \frac{d u}{u \sqrt{u-w}}=\frac{2 \cos ^{-1} \sqrt{w}}{\sqrt{w}}$

for $0<w<1$.]

Paper 3 , Section I, D

commentLet $G$ be a finite group and denote the centre of $G$ by $Z(G)$. Prove that if the quotient group $G / Z(G)$ is cyclic then $G$ is abelian. Does there exist a group $H$ such that (i) $|H / Z(H)|=7$ ? (ii) $|H| Z(H) \mid=6$ ?

Justify your answers.

Paper 3, Section I, D

commentLet $g$ and $h$ be elements of a group $G$. What does it mean to say $g$ and $h$ are conjugate in $G$ ? Prove that if two elements in a group are conjugate then they have the same order.

Define the MÃ¶bius group $\mathcal{M}$. Prove that if $g, h \in \mathcal{M}$ are conjugate they have the same number of fixed points. Quoting clearly any results you use, show that any nontrivial element of $\mathcal{M}$ of finite order has precisely 2 fixed points.

Paper 3, Section II, $7 \mathrm{D}$

commentLet $G$ be a finite group of order $n$. Show that $G$ is isomorphic to a subgroup $H$ of $S_{n}$, the symmetric group of degree $n$. Furthermore show that this isomorphism can be chosen so that any nontrivial element of $H$ has no fixed points.

Suppose $n$ is even. Prove that $G$ contains an element of order 2 .

What does it mean for an element of $S_{m}$ to be odd? Suppose $H$ is a subgroup of $S_{m}$ for some $m$, and $H$ contains an odd element. Prove that precisely half of the elements of $H$ are odd.

Now suppose $n=4 k+2$ for some positive integer $k$. Prove that $G$ is not simple. [Hint: Consider the sign of an element of order 2.]

Can a nonabelian group of even order be simple?

Paper 3, Section II, D

comment(a) Let $A$ be an abelian group (not necessarily finite). We define the generalised dihedral group to be the set of pairs

$D(A)=\{(a, \varepsilon): a \in A, \varepsilon=\pm 1\}$

with multiplication given by

$(a, \varepsilon)(b, \eta)=\left(a b^{\varepsilon}, \varepsilon \eta\right)$

The identity is $(e, 1)$ and the inverse of $(a, \varepsilon)$ is $\left(a^{-\varepsilon}, \varepsilon\right)$. You may assume that this multiplication defines a group operation on $D(A)$.

(i) Identify $A$ with the set of all pairs in which $\varepsilon=+1$. Show that $A$ is a subgroup of $D(A)$. By considering the index of $A$ in $D(A)$, or otherwise, show that $A$ is a normal subgroup of $D(A)$.

(ii) Show that every element of $D(A)$ not in $A$ has order 2 . Show that $D(A)$ is abelian if and only if $a^{2}=e$ for all $a \in A$. If $D(A)$ is non-abelian, what is the centre of $D(A) ?$ Justify your answer.

(b) Let $\mathrm{O}(2)$ denote the group of $2 \times 2$ orthogonal matrices. Show that all elements of $\mathrm{O}(2)$ have determinant 1 or $-1$. Show that every element of $\mathrm{SO}(2)$ is a rotation. Let $J=\left(\begin{array}{cc}1 & 0 \\ 0 & -1\end{array}\right)$. Show that $\mathrm{O}(2)$ decomposes as a union $\mathrm{SO}(2) \cup \operatorname{SO}(2) J$.

[You may assume standard properties of determinants.]

(c) Let $B$ be the (abelian) group $\{z \in \mathbb{C}:|z|=1\}$, with multiplication of complex numbers as the group operation. Write down, without proof, isomorphisms $\mathrm{SO}(2) \cong B \cong \mathbb{R} / \mathbb{Z}$ where $\mathbb{R}$ denotes the additive group of real numbers and $\mathbb{Z}$ the subgroup of integers. Deduce that $\mathrm{O}(2) \cong D(B)$, the generalised dihedral group defined in part (a).

Paper 3, Section II, D

comment(a) Let $G$ be a finite group acting on a set $X$. For $x \in X$, define the orbit $\operatorname{Orb}(x)$ and the stabiliser $\operatorname{Stab}(x)$ of $x$. Show that $\operatorname{Stab}(x)$ is a subgroup of $G$. State and prove the orbit-stabiliser theorem.

(b) Let $n \geqslant k \geqslant 1$ be integers. Let $G=S_{n}$, the symmetric group of degree $n$, and $X$ be the set of all ordered $k$-tuples $\left(x_{1}, \ldots, x_{k}\right)$ with $x_{i} \in\{1,2, \ldots, n\}$. Then $G$ acts on $X$, where the action is defined by $\sigma\left(x_{1}, \ldots, x_{k}\right)=\left(\sigma\left(x_{1}\right), \ldots, \sigma\left(x_{k}\right)\right)$ for $\sigma \in S_{n}$ and $\left(x_{1}, \ldots, x_{k}\right) \in X$. For $x=(1,2, \ldots, k) \in X$, determine $\operatorname{Orb}(x)$ and $\operatorname{Stab}(x)$ and verify that the orbit-stabiliser theorem holds in this case.

(c) We say that $G$ acts doubly transitively on $X$ if, whenever $\left(x_{1}, x_{2}\right)$ and $\left(y_{1}, y_{2}\right)$ are elements of $X \times X$ with $x_{1} \neq x_{2}$ and $y_{1} \neq y_{2}$, there exists some $g \in G$ such that $g x_{1}=y_{1}$ and $g x_{2}=y_{2}$.

Assume that $G$ is a finite group that acts doubly transitively on $X$, and let $x \in X$. Show that if $H$ is a subgroup of $G$ that properly contains $\operatorname{Stab}(x)($ that is, $\operatorname{Stab}(x) \subseteq H$ but $\operatorname{Stab}(x) \neq H)$ then the action of $H$ on $X$ is transitive. Deduce that $H=G$.

Paper 3, Section II, D

comment(a) Let $x$ be an element of a finite group $G$. Define the order of $x$ and the order of $G$. State and prove Lagrange's theorem. Deduce that the order of $x$ divides the order of $G$.

(b) If $G$ is a group of order $n$, and $d$ is a divisor of $n$ where $d<n$, is it always true that $G$ must contain an element of order $d$ ? Justify your answer.

(c) Denote the cyclic group of order $m$ by $C_{m}$.

(i) Prove that if $m$ and $n$ are coprime then the direct product $C_{m} \times C_{n}$ is cyclic.

(ii) Show that if a finite group $G$ has all non-identity elements of order 2 , then $G$ is isomorphic to $C_{2} \times \cdots \times C_{2}$. [The direct product theorem may be used without proof.]

(d) Let $G$ be a finite group and $H$ a subgroup of $G$.

(i) Let $x$ be an element of order $d$ in $G$. If $r$ is the least positive integer such that $x^{r} \in H$, show that $r$ divides $d$.

(ii) Suppose further that $H$ has index $n$. If $x \in G$, show that $x^{k} \in H$ for some $k$ such that $0<k \leqslant n$. Is it always the case that the least positive such $k$ is a factor of $n$ ? Justify your answer.

Paper 4 , Section I, E

commentConsider functions $f: X \rightarrow Y$ and $g: Y \rightarrow X$. Which of the following statements are always true, and which can be false? Give proofs or counterexamples as appropriate.

(i) If $g \circ f$ is surjective then $f$ is surjective.

(ii) If $g \circ f$ is injective then $f$ is injective.

(iii) If $g \circ f$ is injective then $g$ is injective.

If $X=\{1, \ldots, m\}$ and $Y=\{1, \ldots, n\}$ with $m<n$, and $g \circ f$ is the identity on $X$, then how many possibilities are there for the pair of functions $f$ and $g$ ?

Paper 4, Section I, $2 E$

commentThe Fibonacci numbers $F_{n}$ are defined by $F_{1}=1, F_{2}=1, F_{n+2}=F_{n+1}+F_{n}(n \geqslant 1)$. Let $a_{n}=F_{n+1} / F_{n}$ be the ratio of successive Fibonacci numbers.

(i) Show that $a_{n+1}=1+1 / a_{n}$. Hence prove by induction that

$(-1)^{n} a_{n+2} \leqslant(-1)^{n} a_{n}$

for all $n \geqslant 1$. Deduce that the sequence $a_{2 n}$ is monotonically decreasing.

(ii) Prove that

$F_{n+2} F_{n}-F_{n+1}^{2}=(-1)^{n+1}$

for all $n \geqslant 1$. Hence show that $a_{n+1}-a_{n} \rightarrow 0$ as $n \rightarrow \infty$.

(iii) Explain without detailed justification why the sequence $a_{n}$ has a limit.

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

comment(a) (i) By considering Euclid's algorithm, show that the highest common factor of two positive integers $a$ and $b$ can be written in the form $\alpha a+\beta b$ for suitable integers $\alpha$ and $\beta$. Find an integer solution of

$15 x+21 y+35 z=1$

Is your solution unique?

(ii) Suppose that $n$ and $m$ are coprime. Show that the simultaneous congruences

$\begin{array}{ll} x \equiv a & (\bmod n) \\ x \equiv b & (\bmod m) \end{array}$

have the same set of solutions as $x \equiv c(\bmod m n)$ for some $c \in \mathbb{N}$. Hence solve (i.e. find all solutions of) the simultaneous congruences

$\begin{array}{ll} 3 x \equiv 1 & (\bmod 5) \\ 5 x \equiv 1 & (\bmod 7) \\ 7 x \equiv 1 & (\bmod 3) \end{array}$

(b) State the inclusion-exclusion principle.

For integers $r, n \geqslant 1$, denote by $\phi_{r}(n)$ the number of ordered r-tuples $\left(x_{1}, \ldots, x_{r}\right)$ of integers $x_{i}$ satisfying $1 \leqslant x_{i} \leqslant n$ for $i=1, \ldots, r$ and such that the greatest common divisor of $\left\{n, x_{1}, \ldots, x_{r}\right\}$ is 1 . Show that

$\phi_{r}(n)=n^{r} \prod_{p \mid n}\left(1-\frac{1}{p^{r}}\right)$

where the product is over all prime numbers $p$ dividing $n$.

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

comment(a) Prove that every real number $\alpha \in(0,1]$ can be written in the form $\alpha=$ $\sum_{n=1}^{\infty} 2^{-b_{n}}$ where $\left(b_{n}\right)$ is a strictly increasing sequence of positive integers.

Are such expressions unique?

(b) Let $\theta \in \mathbb{R}$ be a root of $f(x)=\alpha_{d} x^{d}+\cdots+\alpha_{1} x+\alpha_{0}$, where $\alpha_{0}, \ldots, \alpha_{d} \in \mathbb{Z}$. Suppose that $f$ has no rational roots, except possibly $\theta$.

(i) Show that if $s, t \in \mathbb{R}$ then

$|f(s)-f(t)| \leqslant A(\max \{|s|,|t|, 1\})^{d-1}|s-t| .$

where $A$ is a constant depending only on $f$.

(ii) Deduce that if $p, q \in \mathbb{Z}$ with $q>0$ and $0<\left|\theta-\frac{p}{q}\right|<1$ then

$\left|\theta-\frac{p}{q}\right| \geqslant \frac{1}{A}\left(\frac{1}{|\theta|+1}\right)^{d-1} \frac{1}{q^{d}} .$

(c) Prove that $\alpha=\sum_{n=1}^{\infty} 2^{-n !}$ is transcendental.

(d) Let $\beta$ and $\gamma$ be transcendental numbers. What of the following statements are always true and which can be false? Briefly justify your answers.

(i) $\beta \gamma$ is transcendental.

(ii) $\beta^{n}$ is transcendental for every $n \in \mathbb{N}$.

Paper 4, Section II, 8E

comment(a) Prove that a countable union of countable sets is countable.

(b) (i) Show that the set $\mathbb{N}^{\mathbb{N}}$ of all functions $\mathbb{N} \rightarrow \mathbb{N}$ is uncountable.

(ii) Determine the countability or otherwise of each of the two sets

$\begin{aligned} &A=\left\{f \in \mathbb{N}^{\mathbb{N}}: f(n) \leqslant f(n+1) \text { for all } n \in \mathbb{N}\right\}, \\ &B=\left\{f \in \mathbb{N}^{\mathbb{N}}: f(n) \geqslant f(n+1) \text { for all } n \in \mathbb{N}\right\} \end{aligned}$

Justify your answers.

(c) A permutation $\sigma$ of the natural numbers $\mathbb{N}$ is a mapping $\sigma \in \mathbb{N}^{\mathbb{N}}$ that is bijective. Determine the countability or otherwise of each of the two sets $C$ and $D$ of permutations, justifying your answers:

(i) $C$ is the set of all permutations $\sigma$ of $\mathbb{N}$ such that $\sigma(j)=j$ for all sufficiently large $j$.

(ii) $D$ is the set all permutations $\sigma$ of $\mathbb{N}$ such that

$\sigma(j)=j-1 \text { or } j \text { or } j+1$

for each $j$.

Paper 4, Section II, E

comment(a) Let $S$ be the set of all functions $f: \mathbb{N} \rightarrow \mathbb{R}$. Define $\delta: S \rightarrow S$ by

$(\delta f)(n)=f(n+1)-f(n)$

(i) Define the binomial coefficient $\left(\begin{array}{l}n \\ r\end{array}\right)$ for $0 \leqslant r \leqslant n$. Setting $\left(\begin{array}{l}n \\ r\end{array}\right)=0$ when $r>n$, prove from your definition that if $f_{r}(n)=\left(\begin{array}{l}n \\ r\end{array}\right)$ then $\delta f_{r}=f_{r-1}$.

(ii) Show that if $f \in S$ is integer-valued and $\delta^{k+1} f=0$, then

$f(n)=c_{0}\left(\begin{array}{l} n \\ k \end{array}\right)+c_{1}\left(\begin{array}{c} n \\ k-1 \end{array}\right)+\cdots+c_{k-1}\left(\begin{array}{l} n \\ 1 \end{array}\right)+c_{k}$

for some integers $c_{0}, \ldots, c_{k}$.

(b) State the binomial theorem. Show that

$\sum_{r=0}^{n}(-1)^{r}\left(\begin{array}{l} n \\ r \end{array}\right)^{2}=\left\{\begin{array}{cl} 0 & \text { if } n \text { is odd } \\ (-1)^{n / 2}\left(\begin{array}{c} n \\ n / 2 \end{array}\right) & \text { if } n \text { is even } \end{array}\right.$

Paper 2, Section I, D

commentA coin has probability $p$ of landing heads. Let $q_{n}$ be the probability that the number of heads after $n$ tosses is even. Give an expression for $q_{n+1}$ in terms of $q_{n}$. Hence, or otherwise, find $q_{n}$.

Paper 2, Section I, F

commentLet $X$ be a continuous random variable taking values in $[0, \sqrt{3}]$. Let the probability density function of $X$ be

$f_{X}(x)=\frac{c}{1+x^{2}}, \quad \text { for } x \in[0, \sqrt{3}]$

where $c$ is a constant.

Find the value of $c$ and calculate the mean, variance and median of $X$.

[Recall that the median of $X$ is the number $m$ such that $\left.\mathbb{P}(X \leqslant m)=\frac{1}{2} .\right]$

Paper 2, Section II, 10E

comment(a) Alanya repeatedly rolls a fair six-sided die. What is the probability that the first number she rolls is a 1 , given that she rolls a 1 before she rolls a $6 ?$

(b) Let $\left(X_{n}\right)_{n \geqslant 0}$ be a simple symmetric random walk on the integers starting at $x \in \mathbb{Z}$, that is,

$X_{n}=\left\{\begin{array}{cl} x & \text { if } n=0 \\ x+\sum_{i=1}^{n} Y_{i} & \text { if } n \geqslant 1 \end{array}\right.$

where $\left(Y_{n}\right)_{n \geqslant 1}$ is a sequence of IID random variables with $\mathbb{P}\left(Y_{n}=1\right)=\mathbb{P}\left(Y_{n}=-1\right)=\frac{1}{2}$. Let $T=\min \left\{n \geqslant 0: X_{n}=0\right\}$ be the time that the walk first hits 0 .

(i) Let $n$ be a positive integer. For $0<x<n$, calculate the probability that the walk hits 0 before it hits $n$.

(ii) Let $x=1$ and let $A$ be the event that the walk hits 0 before it hits 3 . Find $\mathbb{P}\left(X_{1}=0 \mid A\right)$. Hence find $\mathbb{E}(T \mid A)$.

(iii) Let $x=1$ and let $B$ be the event that the walk hits 0 before it hits 4 . Find $\mathbb{E}(T \mid B)$.

Paper 2, Section II, 12F

commentState and prove Chebyshev's inequality.

Let $\left(X_{i}\right)_{i \geqslant 1}$ be a sequence of independent, identically distributed random variables such that

$\mathbb{P}\left(X_{i}=0\right)=p \text { and } \mathbb{P}\left(X_{i}=1\right)=1-p$

for some $p \in[0,1]$, and let $f:[0,1] \rightarrow \mathbb{R}$ be a continuous function.

(i) Prove that

$B_{n}(p):=\mathbb{E}\left(f\left(\frac{X_{1}+\cdots+X_{n}}{n}\right)\right)$

is a polynomial function of $p$, for any natural number $n$.

(ii) Let $\delta>0$. Prove that

$\sum_{k \in K_{\delta}}\left(\begin{array}{l} n \\ k \end{array}\right) p^{k}(1-p)^{n-k} \leqslant \frac{1}{4 n \delta^{2}}$

where $K_{\delta}$ is the set of natural numbers $0 \leqslant k \leqslant n$ such that $|k / n-p|>\delta$.

(iii) Show that

$\sup _{p \in[0,1]}\left|f(p)-B_{n}(p)\right| \rightarrow 0$

as $n \rightarrow \infty$. [You may use without proof that, for any $\epsilon>0$, there is a $\delta>0$ such that $|f(x)-f(y)| \leqslant \epsilon$ for all $x, y \in[0,1]$ with $|x-y| \leqslant \delta$.]

Paper 2, Section II, 9E

comment(a) (i) Define the conditional probability $\mathbb{P}(A \mid B)$ of the event $A$ given the event $B$. Let $\left\{B_{j}: 1 \leqslant j \leqslant n\right\}$ be a partition of the sample space such that $\mathbb{P}\left(B_{j}\right)>0$ for all $j$. Show that, if $\mathbb{P}(A)>0$,

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

(ii) There are $n$ urns, the $r$ th of which contains $r-1$ red balls and $n-r$ blue balls. Alice picks an urn (uniformly) at random and removes two balls without replacement. Find the probability that the first ball is blue, and the conditional probability that the second ball is blue, given that the first is blue. [You may assume, if you wish, that $\sum_{i=1}^{n-1} i(i-1)=\frac{1}{3} n(n-1)(n-2)$.]

(b) (i) What is meant by saying that two events $A$ and $B$ are independent? Two fair (6-sided) dice are rolled. Let $A_{t}$ be the event that the sum of the numbers shown is $t$, and let $B_{i}$ be the event that the first die shows $i$. For what values of $t$ and $i$ are the two events $A_{t}$ and $B_{i}$ independent?

(ii) The casino at Monte Corona features the following game: three coins each show heads with probability $3 / 5$ and tails otherwise. The first counts 10 points for a head and 2 for a tail; the second counts 4 points for both a head and a tail; and the third counts 3 points for a head and 20 for a tail. You and your opponent each choose a coin. You cannot both choose the same coin. Each of you tosses your coin once and the person with the larger score wins the jackpot. Would you prefer to be the first or the second to choose a coin?

Paper 2, Section II, D

commentLet $\Delta$ be the disc of radius 1 with centre at the origin $O$. Let $P$ be a random point uniformly distributed in $\Delta$. Let $(R, \Theta)$ be the polar coordinates of $P$. Show that $R$ and $\Theta$ are independent and find their probability density functions $f_{R}$ and $f_{\Theta}$.

Let $A, B$ and $C$ be three random points selected independently and uniformly in $\Delta$. Find the expected area of triangle $O A B$ and hence find the probability that $C$ lies in the interior of triangle $O A B$.

Find the probability that $O, A, B$ and $C$ are the vertices of a convex quadrilateral.

Paper 3, Section I, B

comment(a) What is meant by an antisymmetric tensor of second rank? Show that if a second rank tensor is antisymmetric in one Cartesian coordinate system, it is antisymmetric in every Cartesian coordinate system.

(b) Consider the vector field $\mathbf{F}=(y, z, x)$ and the second rank tensor defined by $T_{i j}=\partial F_{i} / \partial x_{j}$. Calculate the components of the antisymmetric part of $T_{i j}$ and verify that it equals $-(1 / 2) \epsilon_{i j k} B_{k}$, where $\epsilon_{i j k}$ is the alternating tensor and $\mathbf{B}=\boldsymbol{\nabla} \times \mathbf{F}$.

Paper 3, Section I, B

comment(a) Prove that

$\begin{aligned} &\nabla \times(\psi \mathbf{A})=\psi \mathbf{\nabla} \times \mathbf{A}+\boldsymbol{\nabla} \psi \times \mathbf{A} \\ &\nabla \cdot(\mathbf{A} \times \mathbf{B})=\mathbf{B} \cdot \boldsymbol{\nabla} \times \mathbf{A}-\mathbf{A} \cdot \boldsymbol{\nabla} \times \mathbf{B} \end{aligned}$

where $\mathbf{A}$ and $\mathbf{B}$ are differentiable vector fields and $\psi$ is a differentiable scalar field.

(b) Find the solution of $\nabla^{2} u=16 r^{2}$ on the two-dimensional domain $\mathcal{D}$ when

(i) $\mathcal{D}$ is the unit disc $0 \leqslant r \leqslant 1$, and $u=1$ on $r=1$;

(ii) $\mathcal{D}$ is the annulus $1 \leqslant r \leqslant 2$, and $u=1$ on both $r=1$ and $r=2$.

[Hint: the Laplacian in plane polar coordinates is:

$\left.\nabla^{2} u=\frac{1}{r} \frac{\partial}{\partial r}\left(r \frac{\partial u}{\partial r}\right)+\frac{1}{r^{2}} \frac{\partial^{2} u}{\partial \theta^{2}} . \quad\right]$

Paper 3, Section II, B

commentFor a given charge distribution $\rho(\mathbf{x}, t)$ and current distribution $\mathbf{J}(\mathbf{x}, t)$ in $\mathbb{R}^{3}$, the electric and magnetic fields, $\mathbf{E}(\mathbf{x}, t)$ and $\mathbf{B}(\mathbf{x}, t)$, satisfy Maxwell's equations, which in suitable units, read

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

The Poynting vector $\mathbf{P}$ is defined as $\mathbf{P}=\mathbf{E} \times \mathbf{B}$.

(a) For a closed surface $\mathcal{S}$ around a volume $\mathcal{V}$, show that

$\int_{\mathcal{S}} \mathbf{P} \cdot d \mathbf{S}=-\int_{\mathcal{V}} \mathbf{E} \cdot \mathbf{J} d V-\frac{\partial}{\partial t} \int_{\mathcal{V}} \frac{|\mathbf{E}|^{2}+|\mathbf{B}|^{2}}{2} d V$

(b) Suppose $\mathbf{J}=\mathbf{0}$ and consider an electromagnetic wave

$\mathbf{E}=E_{0} \hat{\mathbf{y}} \cos (k x-\omega t) \quad \text { and } \quad \mathbf{B}=B_{0} \hat{\mathbf{z}} \cos (k x-\omega t)$

where $E_{0}, B_{0}, k$ and $\omega$ are positive constants. Show that these fields satisfy Maxwell's equations for appropriate $E_{0}, \omega$, and $\rho$.

Confirm the wave satisfies the integral identity $(*)$ by considering its propagation through a box $\mathcal{V}$, defined by $0 \leqslant x \leqslant \pi /(2 k), 0 \leqslant y \leqslant L$, and $0 \leqslant z \leqslant L$.

Paper 3, Section II, B

comment(a) By a suitable change of variables, calculate the volume enclosed by the ellipsoid $x^{2} / a^{2}+y^{2} / b^{2}+z^{2} / c^{2}=1$, where $a, b$, and $c$ are constants.

(b) Suppose $T_{i j}$ is a second rank tensor. Use the divergence theorem to show that

$\int_{\mathcal{S}} T_{i j} n_{j} d S=\int_{\mathcal{V}} \frac{\partial T_{i j}}{\partial x_{j}} d V$

where $\mathcal{S}$ is a closed surface, with unit normal $n_{j}$, and $\mathcal{V}$ is the volume it encloses.

[Hint: Consider $e_{i} T_{i j}$ for a constant vector $\left.e_{i} .\right]$

(c) A half-ellipsoidal membrane $\mathcal{S}$ is described by the open surface $4 x^{2}+4 y^{2}+z^{2}=4$, with $z \geqslant 0$. At a given instant, air flows beneath the membrane with velocity $\mathbf{u}=$ $(-y, x, \alpha)$, where $\alpha$ is a constant. The flow exerts a force on the membrane given by

$F_{i}=\int_{\mathcal{S}} \beta^{2} u_{i} u_{j} n_{j} d S$

where $\beta$ is a constant parameter.

Show the vector $a_{i}=\partial\left(u_{i} u_{j}\right) / \partial x_{j}$ can be rewritten as $\mathbf{a}=-(x, y, 0)$.

Hence use $(*)$ to calculate the force $F_{i}$ on the membrane.

Paper 3, Section II, B

comment(a) By considering an appropriate double integral, show that

$\int_{0}^{\infty} e^{-a x^{2}} d x=\sqrt{\frac{\pi}{4 a}}$

where $a>0$.

(b) Calculate $\int_{0}^{1} x^{y} d y$, treating $x$ as a constant, and hence show that

$\int_{0}^{\infty} \frac{\left(e^{-u}-e^{-2 u}\right)}{u} d u=\log 2$

(c) Consider the region $\mathcal{D}$ in the $x-y$ plane enclosed by $x^{2}+y^{2}=4, y=1$, and $y=\sqrt{3} x$ with $1<y<\sqrt{3} x$.

Sketch $\mathcal{D}$, indicating any relevant polar angles.

A surface $\mathcal{S}$ is given by $z=x y /\left(x^{2}+y^{2}\right)$. Calculate the volume below this surface and above $\mathcal{D}$.

Paper 3, Section II, B

(a) Given a space curve $\mathbf{r}(t)=(x(t), y(t), z(t)$, with $t$ a parameter (not necessarily arc-length), give mathematical expressions for the unit tangent, unit normal, and unit binormal vectors.

(b) Consider the closed curve given by

$x=2 \cos ^{3} t, \quad y=\sin ^{3} t, \quad z=\sqrt{3} \sin ^{3} t$

where $t \in[0,2 \pi)$.

Show that the unit tangent vector $\mathbf{T}$ may be written as

$\mathbf{T}=\pm \frac{1}{2}(-2 \cos t, \sin t, \sqrt{3} \sin t)$

with each sign associated with a certain range of $t$, which you should specify.

Calculate the unit normal and the unit binormal vectors, and hence deduce that the curve lies in a plane.

(c) A closed space curve $\mathcal{C}$ lies in a plane with unit normal $\mathbf{n}=(a, b, c)$. Use Stokes' theorem to prove that the planar area enclosed by $\mathcal{C}$ is the absolute value of the line integral

$\frac{1}{2} \int_{\mathcal{C}}(b z-c y) d x+(c x-a z) d y+(a y-b x) d z$