Part IA, 2011

# Part IA, 2011

### Jump to course

Paper 1, Section I, $3 F$

comment(a) State, without proof, the Bolzano-Weierstrass Theorem.

(b) Give an example of a sequence that does not have a convergent subsequence.

(c) Give an example of an unbounded sequence having a convergent subsequence.

(d) Let $a_{n}=1+(-1)^{\lfloor n / 2\rfloor}(1+1 / n)$, where $\lfloor x\rfloor$ denotes the integer part of $x$. Find all values $c$ such that the sequence $\left\{a_{n}\right\}$ has a subsequence converging to $c$. For each such value, provide a subsequence converging to it.

Paper 1, Section I, D

commentFind the radius of convergence of each of the following power series. (i) $\sum_{n \geqslant 1} n^{2} z^{n}$ (ii) $\sum_{n \geqslant 1} n^{n^{1 / 3}} z^{n}$

Paper 1, Section II, D

commentState and prove the Fundamental Theorem of Calculus.

Let $f:[0,1] \rightarrow \mathbb{R}$ be integrable, and set $F(x)=\int_{0}^{x} f(t) \mathrm{d} t$ for $0<x<1$. Must $F$ be differentiable?

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be differentiable, and set $g(x)=f^{\prime}(x)$ for $0 \leqslant x \leqslant 1$. Must the Riemann integral of $g$ from 0 to 1 exist?

Paper 1, Section II, E

commentFor each of the following two functions $f: \mathbb{R} \rightarrow \mathbb{R}$, determine the set of points at which $f$ is continuous, and also the set of points at which $f$ is differentiable.

$\begin{aligned} &\text { (i) } f(x)= \begin{cases}x & \text { if } x \in \mathbb{Q} \\ -x & \text { if } x \notin \mathbb{Q}\end{cases} \\ &\text { (ii) } f(x)= \begin{cases}x \sin (1 / x) & \text { if } x \neq 0 \\ 0 & \text { if } x=0\end{cases} \end{aligned}$

By modifying the function in (i), or otherwise, find a function (not necessarily continuous) $f: \mathbb{R} \rightarrow \mathbb{R}$ such that $f$ is differentiable at 0 and nowhere else.

Find a continuous function $f: \mathbb{R} \rightarrow \mathbb{R}$ such that $f$ is not differentiable at the points $1 / 2,1 / 3,1 / 4, \ldots$, but is differentiable at all other points.

Paper 1, Section II, E

commentState and prove the Intermediate Value Theorem.

A fixed point of a function $f: X \rightarrow X$ is an $x \in X$ with $f(x)=x$. Prove that every continuous function $f:[0,1] \rightarrow[0,1]$ has a fixed point.

Answer the following questions with justification.

(i) Does every continuous function $f:(0,1) \rightarrow(0,1)$ have a fixed point?

(ii) Does every continuous function $f: \mathbb{R} \rightarrow \mathbb{R}$ have a fixed point?

(iii) Does every function $f:[0,1] \rightarrow[0,1]$ (not necessarily continuous) have a fixed point?

(iv) Let $f:[0,1] \rightarrow[0,1]$ be a continuous function with $f(0)=1$ and $f(1)=0$. Can $f$ have exactly two fixed points?

Paper 1, Section II, F

comment(a) State, without proof, the ratio test for the series $\sum_{n \geqslant 1} a_{n}$, where $a_{n}>0$. Give examples, without proof, to show that, when $a_{n+1}<a_{n}$ and $a_{n+1} / a_{n} \rightarrow 1$, the series may converge or diverge.

(b) Prove that $\sum_{k=1}^{n-1} \frac{1}{k} \geqslant \log n$.

(c) Now suppose that $a_{n}>0$ and that, for $n$ large enough, $\frac{a_{n+1}}{a_{n}} \leqslant 1-\frac{c}{n}$ where $c>1$. Prove that the series $\sum_{n \geqslant 1} a_{n}$ converges.

[You may find it helpful to prove the inequality $\log (1-x)<-x$ for $0<x<1$.]

Paper 2, Section I, $2 A$

comment(a) For a differential equation of the form $\frac{\mathrm{d} y}{\mathrm{~d} x}=f(y)$, explain how $f^{\prime}(y)$ can be used to determine the stability of any equilibrium solutions and justify your answer.

(b) Find the equilibrium solutions of the differential equation

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

and determine their stability. Sketch representative solution curves in the $(x, y)$-plane.

Paper 2, Section I, A

comment(a) Consider the homogeneous $k$ th-order difference equation

$a_{k} y_{n+k}+a_{k-1} y_{n+k-1}+\ldots+a_{2} y_{n+2}+a_{1} y_{n+1}+a_{0} y_{n}=0$

where the coefficients $a_{k}, \ldots, a_{0}$ are constants. Show that for $\lambda \neq 0$ the sequence $y_{n}=\lambda^{n}$ is a solution if and only if $p(\lambda)=0$, where

$p(\lambda)=a_{k} \lambda^{k}+a_{k-1} \lambda^{k-1}+\ldots+a_{2} \lambda^{2}+a_{1} \lambda+a_{0}$

State the general solution of $(*)$ if $k=3$ and $p(\lambda)=(\lambda-\mu)^{3}$ for some constant $\mu$.

(b) Find an inhomogeneous difference equation that has the general solution

$y_{n}=a 2^{n}-n, \quad a \in \mathbb{R}$

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

comment(a) Define the Wronskian $W$ of two solutions $y_{1}(x)$ and $y_{2}(x)$ of the differential equation

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

and state a necessary and sufficient condition for $y_{1}(x)$ and $y_{2}(x)$ to be linearly independent. Show that $W(x)$ satisfies the differential equation

$W^{\prime}(x)=-p(x) W(x)$

(b) By evaluating the Wronskian, or otherwise, find functions $p(x)$ and $q(x)$ such that $(*)$ has solutions $y_{1}(x)=1+\cos x$ and $y_{2}(x)=\sin x$. What is the value of $W(\pi) ?$ Is there a unique solution to the differential equation for $0 \leqslant x<\infty$ with initial conditions $y(0)=0, y^{\prime}(0)=1$ ? Why or why not?

(c) Write down a third-order differential equation with constant coefficients, such that $y_{1}(x)=1+\cos x$ and $y_{2}(x)=\sin x$ are both solutions. Is the solution to this equation for $0 \leqslant x<\infty$ with initial conditions $y(0)=y^{\prime \prime}(0)=0, y^{\prime}(0)=1$ unique? Why or why not?

Paper 2, Section II, A

comment(a) A surface in $\mathbb{R}^{3}$ is defined by the equation $f(x, y, z)=c$, where $c$ is a constant. Show that the partial derivatives on this surface satisfy

$\left.\left.\left.\frac{\partial x}{\partial y}\right|_{z} \frac{\partial y}{\partial z}\right|_{x} \frac{\partial z}{\partial x}\right|_{y}=-1$

(b) Now let $f(x, y, z)=x^{2}-y^{4}+2 a y^{2}+z^{2}$, where $a$ is a constant.

(i) Find expressions for the three partial derivatives $\left.\frac{\partial x}{\partial y}\right|_{z},\left.\frac{\partial y}{\partial z}\right|_{x}$ and $\left.\frac{\partial z}{\partial x}\right|_{y}$ on the surface $f(x, y, z)=c$, and verify the identity $(*)$.

(ii) Find the rate of change of $f$ in the radial direction at the point $(x, 0, z)$.

(iii) Find and classify the stationary points of $f$.

(iv) Sketch contour plots of $f$ in the $(x, y)$-plane for the cases $a=1$ and $a=-1$.

Paper 2, Section II, A

comment(a) Find the general real solution of the system of first-order differential equations

$\begin{aligned} &\dot{x}=x+\mu y \\ &\dot{y}=-\mu x+y, \end{aligned}$

where $\mu$ is a real constant.

(b) Find the fixed points of the non-linear system of first-order differential equations

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

and determine their nature. Sketch the phase portrait indicating the direction of motion along trajectories.

Paper 2, Section II, A

comment(a) The circumference $y$ of an ellipse with semi-axes 1 and $x$ is given by

$y(x)=\int_{0}^{2 \pi} \sqrt{\sin ^{2} \theta+x^{2} \cos ^{2} \theta} \mathrm{d} \theta .$

Setting $t=1-x^{2}$, find the first three terms in a series expansion of $(*)$ around $t=0$.

(b) Euler proved that $y$ also satisfies the differential equation

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

Use the substitution $t=1-x^{2}$ for $x \geqslant 0$ to find a differential equation for $u(t)$, where $u(t)=y(x)$. Show that this differential equation has regular singular points at $t=0$ and $t=1$.

Show that the indicial equation at $t=0$ has a repeated root, and find the recurrence relation for the coefficients of the corresponding power-series solution. State the form of a second, independent solution.

Verify that the power-series solution is consistent with your answer in (a).

Paper 4, Section I, B

commentInertial frames $S$ and $S^{\prime}$ in two-dimensional space-time have coordinates $(x, t)$ and $\left(x^{\prime}, t^{\prime}\right)$, respectively. These coordinates are related by a Lorentz transformation with $v$ the velocity of $S^{\prime}$ relative to $S$. Show that if $x_{\pm}=x \pm c t$ and $x_{\pm}^{\prime}=x^{\prime} \pm c t^{\prime}$ then the Lorentz transformation can be expressed in the form

$x_{+}^{\prime}=\lambda(v) x_{+} \quad \text { and } \quad x_{-}^{\prime}=\lambda(-v) x_{-}, \quad \text { where } \quad \lambda(v)=\left(\frac{c-v}{c+v}\right)^{1 / 2} .$

Deduce that $x^{2}-c^{2} t^{2}=x^{\prime 2}-c^{2} t^{\prime 2}$.

Use the form $(*)$ to verify that successive Lorentz transformations with velocities $v_{1}$ and $v_{2}$ result in another Lorentz transformation with velocity $v_{3}$, to be determined in terms of $v_{1}$ and $v_{2}$.

Paper 4, Section I, B

commentThe motion of a planet in the gravitational field of a star of mass $M$ obeys

$\frac{\mathrm{d}^{2} r}{\mathrm{~d} t^{2}}-\frac{h^{2}}{r^{3}}=-\frac{G M}{r^{2}}, \quad r^{2} \frac{\mathrm{d} \theta}{\mathrm{d} t}=h$

where $r(t)$ and $\theta(t)$ are polar coordinates in a plane and $h$ is a constant. Explain one of Kepler's Laws by giving a geometrical interpretation of $h$.

Show that circular orbits are possible, and derive another of Kepler's Laws relating the radius $a$ and the period $T$ of such an orbit. Show that any circular orbit is stable under small perturbations that leave $h$ unchanged.

Paper 4, Section II, B

comment(a) Write down the relativistic energy $E$ of a particle of rest mass $m$ and speed $v$. Find the approximate form for $E$ when $v$ is small compared to $c$, keeping all terms up to order $(v / c)^{2}$. What new physical idea (when compared to Newtonian Dynamics) is revealed in this approximation?

(b) A particle of rest mass $m$ is fired at an identical particle which is at rest in the laboratory frame. Let $E$ be the relativistic energy and $v$ the speed of the incident particle in this frame. After the collision, there are $N$ particles in total, each with rest mass $m$. Assuming that four-momentum is conserved, find a lower bound on $E$ and hence show that

$v \geqslant \frac{N\left(N^{2}-4\right)^{1 / 2}}{N^{2}-2} c$

Paper 4, Section II, B

commentA rocket carries equipment to collect samples from a stationary cloud of cosmic dust. The rocket moves in a straight line, burning fuel and ejecting gas at constant speed $u$ relative to itself. Let $v(t)$ be the speed of the rocket, $M(t)$ its total mass, including fuel and any dust collected, and $m(t)$ the total mass of gas that has been ejected. Show that

$M \frac{\mathrm{d} v}{\mathrm{~d} t}+v \frac{\mathrm{d} M}{\mathrm{~d} t}+(v-u) \frac{\mathrm{d} m}{\mathrm{dt}}=0$

assuming that all external forces are negligible.

(a) If no dust is collected and the rocket starts from rest with mass $M_{0}$, deduce that

$v=u \log \left(M_{0} / M\right)$

(b) If cosmic dust is collected at a constant rate of $\alpha$ units of mass per unit time and fuel is consumed at a constant rate $\mathrm{d} m / \mathrm{d} t=\beta$, show that, with the same initial conditions as in (a),

$v=\frac{u \beta}{\alpha}\left(1-\left(M / M_{0}\right)^{\alpha /(\beta-\alpha)}\right)$

Verify that the solution in (a) is recovered in the limit $\alpha \rightarrow 0$.

Paper 4, Section II, B

commentThe trajectory of a particle $\mathbf{r}(t)$ is observed in a frame $S$ which rotates with constant angular velocity $\omega$ relative to an inertial frame $I$. Given that the time derivative in $I$ of any vector $\mathbf{u}$ is

$\left(\frac{\mathrm{d} \mathbf{u}}{\mathrm{d} t}\right)_{I}=\dot{\mathbf{u}}+\boldsymbol{\omega} \times \mathbf{u},$

where a dot denotes a time derivative in $S$, show that

$m \ddot{\mathbf{r}}=\mathbf{F}-2 m \boldsymbol{\omega} \times \dot{\mathbf{r}}-m \boldsymbol{\omega} \times(\boldsymbol{\omega} \times \mathbf{r}),$

where $\mathbf{F}$ is the force on the particle and $m$ is its mass.

Let $S$ be the frame that rotates with the Earth. Assume that the Earth is a sphere of radius $R$. Let $P$ be a point on its surface at latitude $\pi / 2-\theta$, and define vertical to be the direction normal to the Earth's surface at $P$.

(a) A particle at $P$ is released from rest in $S$ and is acted on only by gravity. Show that its initial acceleration makes an angle with the vertical of approximately

$\frac{\omega^{2} R}{g} \sin \theta \cos \theta$

working to lowest non-trivial order in $\omega$.

(b) Now consider a particle fired vertically upwards from $P$ with speed $v$. Assuming that terms of order $\omega^{2}$ and higher can be neglected, show that it falls back to Earth under gravity at a distance

$\frac{4}{3} \frac{\omega v^{3}}{g^{2}} \sin \theta$

from $P$. [You may neglect the curvature of the Earth's surface and the vertical variation of gravity.]

Paper 4, Section II, B

commentA particle with mass $m$ and position $\mathbf{r}(t)$ is subject to a force

$\mathbf{F}=\mathbf{A}(\mathbf{r})+\dot{\mathbf{r}} \times \mathbf{B}(\mathbf{r})$

(a) Suppose that $\mathbf{A}=-\nabla \phi$. Show that

$E=\frac{1}{2} m \dot{\mathbf{r}}^{2}+\phi(\mathbf{r})$

is constant, and interpret this result, explaining why the field $\mathbf{B}$ plays no role.

(b) Suppose, in addition, that $\mathbf{B}=-\nabla \psi$ and that both $\phi$ and $\psi$ depend only on $r=|\mathbf{r}|$. Show that

$\mathbf{L}=m \mathbf{r} \times \dot{\mathbf{r}}-\psi \mathbf{r}$

is independent of time if $\psi(r)=\mu / r$, for any constant $\mu$.

(c) Now specialise further to the case $\psi=0$. Explain why the result in (b) implies that the motion of the particle is confined to a plane. Show also that

$\mathbf{K}=\mathbf{L} \times \dot{\mathbf{r}}-\phi \mathbf{r}$

is constant provided $\phi(r)$ takes a certain form, to be determined.

[ Recall that $\mathbf{r} \cdot \dot{\mathbf{r}}=r \dot{r}$ and that if $f$ depends only on $r=|\mathbf{r}|$ then $\left.\boldsymbol{\nabla} f=f^{\prime}(r) \hat{\mathbf{r}} .\right]$

Paper 3, Section I, D

commentState and prove Lagrange's Theorem.

Show that the dihedral group of order $2 n$ has a subgroup of order $k$ for every $k$ dividing $2 n$.

Paper 3, Section I, D

comment(a) Let $G$ be the group of symmetries of the cube, and consider the action of $G$ on the set of edges of the cube. Determine the stabilizer of an edge and its orbit. Hence compute the order of $G$.

(b) The symmetric group $S_{n}$ acts on the set $X=\{1, \ldots, n\}$, and hence acts on $X \times X$ by $g(x, y)=(g x, g y)$. Determine the orbits of $S_{n}$ on $X \times X$.

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

comment(a) State the orbit-stabilizer theorem.

Let a group $G$ act on itself by conjugation. Define the centre $Z(G)$ of $G$, and show that $Z(G)$ consists of the orbits of size 1 . Show that $Z(G)$ is a normal subgroup of $G$.

(b) Now let $|G|=p^{n}$, where $p$ is a prime and $n \geqslant 1$. Show that if $G$ acts on a set $X$, and $Y$ is an orbit of this action, then either $|Y|=1$ or $p$ divides $|Y|$.

Show that $|Z(G)|>1$.

By considering the set of elements of $G$ that commute with a fixed element $x$ not in $Z(G)$, show that $Z(G)$ cannot have order $p^{n-1}$.

Paper 3, Section II, D

comment(a) Let $G$ be a finite group and let $H$ be a subgroup of $G$. Show that if $|G|=2|H|$ then $H$ is normal in $G$.

Show that the dihedral group $D_{2 n}$ of order $2 n$ has a normal subgroup different from both $D_{2 n}$ and $\{e\}$.

For each integer $k \geqslant 3$, give an example of a finite group $G$, and a subgroup $H$, such that $|G|=k|H|$ and $H$ is not normal in $G$.

(b) Show that $A_{5}$ is a simple group.

Paper 3, Section II, D

comment(a) Let

$S L_{2}(\mathbb{Z})=\left\{\left(\begin{array}{ll} a & b \\ c & d \end{array}\right) \mid a d-b c=1, \quad a, b, c, d \in \mathbb{Z}\right\}$

and, for a prime $p$, let

$S L_{2}\left(\mathbb{F}_{p}\right)=\left\{\left(\begin{array}{ll} a & b \\ c & d \end{array}\right) \mid a d-b c=1, \quad a, b, c, d \in \mathbb{F}_{p}\right\}$

where $\mathbb{F}_{p}$ consists of the elements $0,1, \ldots, p-1$, with addition and multiplication mod $p$.

Show that $S L_{2}(\mathbb{Z})$ and $S L_{2}\left(\mathbb{F}_{p}\right)$ are groups under matrix multiplication.

[You may assume that matrix multiplication is associative, and that the determinant of a product equals the product of the determinants.]

By defining a suitable homomorphism from $S L_{2}(\mathbb{Z}) \rightarrow S L_{2}\left(\mathbb{F}_{5}\right)$, show that

$\left\{\left(\begin{array}{cc} 1+5 a & 5 b \\ 5 c & 1+5 d \end{array}\right) \in S L_{2}(\mathbb{Z}) \mid a, b, c, d \in \mathbb{Z}\right\}$

is a normal subgroup of $S L_{2}(\mathbb{Z})$.

(b) Define the group $G L_{2}\left(\mathbb{F}_{5}\right)$, and show that it has order 480 . By defining a suitable homomorphism from $G L_{2}\left(\mathbb{F}_{5}\right)$ to another group, which should be specified, show that the order of $S L_{2}\left(\mathbb{F}_{5}\right)$ is 120 .

Find a subgroup of $G L_{2}\left(\mathbb{F}_{5}\right)$ of index 2 .

Paper 3, Section II, D

comment(a) Let $G$ be a finite group, and let $g \in G$. Define the order of $g$ and show it is finite. Show that if $g$ is conjugate to $h$, then $g$ and $h$ have the same order.

(b) Show that every $g \in S_{n}$ can be written as a product of disjoint cycles. For $g \in S_{n}$, describe the order of $g$ in terms of the cycle decomposition of $g$.

(c) Define the alternating group $A_{n}$. What is the condition on the cycle decomposition of $g \in S_{n}$ that characterises when $g \in A_{n}$ ?

(d) Show that, for every $n, A_{n+2}$ has a subgroup isomorphic to $S_{n}$.

Paper 4, Section I, E

commentWhat is an equivalence relation on a set $X ?$ If $\sim$ is an equivalence relation on $X$, what is an equivalence class of $\sim$ ? Prove that the equivalence classes of $\sim$ form a partition of $X$.

Let $\sim$ be the relation on the positive integers defined by $x \sim y$ if either $x$ divides $y$ or $y$ divides $x$. Is $\sim$ an equivalence relation? Justify your answer.

Write down an equivalence relation on the positive integers that has exactly four equivalence classes, of which two are infinite and two are finite.

Paper 4, Section I, E

commentWhat does it mean to say that a function $f: X \rightarrow Y$ has an inverse? Show that a function has an inverse if and only if it is a bijection.

Let $f$ and $g$ be functions from a set $X$ to itself. Which of the following are always true, and which can be false? Give proofs or counterexamples as appropriate.

(i) If $f$ and $g$ are bijections then $f \circ g$ is a bijection.

(ii) If $f \circ g$ is a bijection then $f$ and $g$ are bijections.

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

commentDefine the binomial coefficient $\left(\begin{array}{l}n \\ i\end{array}\right)$, where $n$ is a positive integer and $i$ is an integer with $0 \leqslant i \leqslant n$. Arguing from your definition, show that $\sum_{i=0}^{n}\left(\begin{array}{l}n \\ i\end{array}\right)=2^{n}$.

Prove the binomial theorem, that $(1+x)^{n}=\sum_{i=0}^{n}\left(\begin{array}{l}n \\ i\end{array}\right) x^{i}$ for any real number $x$.

By differentiating this expression, or otherwise, evaluate $\sum_{i=0}^{n} i\left(\begin{array}{l}n \\ i\end{array}\right)$ and $\sum_{i=0}^{n} i^{2}\left(\begin{array}{l}n \\ i\end{array}\right)$. By considering the identity $(1+x)^{n}(1+x)^{n}=(1+x)^{2 n}$, or otherwise, show that

$\sum_{i=0}^{n}\left(\begin{array}{l} n \\ i \end{array}\right)^{2}=\left(\begin{array}{c} 2 n \\ n \end{array}\right)$

Show that $\sum_{i=0}^{n} i\left(\begin{array}{c}n \\ i\end{array}\right)^{2}=\frac{n}{2}\left(\begin{array}{c}2 n \\ n\end{array}\right)$

Paper 4, Section II, E

commentShow that, for any set $X$, there is no surjection from $X$ to the power-set of $X$.

Show that there exists an injection from $\mathbb{R}^{2}$ to $\mathbb{R}$.

Let $A$ be a subset of $\mathbb{R}^{2}$. A section of $A$ is a subset of $\mathbb{R}$ of the form

$\{t \in \mathbb{R}: a+t b \in A\},$

where $a \in \mathbb{R}^{2}$ and $b \in \mathbb{R}^{2}$ with $b \neq 0$. Prove that there does not exist a set $A \subset \mathbb{R}^{2}$ such that every set $S \subset \mathbb{R}$ is a section of $A$.

Does there exist a set $A \subset \mathbb{R}^{2}$ such that every countable set $S \subset \mathbb{R}$ is a section of $A ? \quad$ [There is no requirement that every section of $A$ should be countable.] Justify your answer.

Paper 4, Section II, E

commentState Fermat's Theorem and Wilson's Theorem.

Let $p$ be a prime.

(a) Show that if $p \equiv 3(\bmod 4)$ then the equation $x^{2} \equiv-1(\bmod p)$ has no solution.

(b) By considering $\left(\frac{p-1}{2}\right)$ !, or otherwise, show that if $p \equiv 1(\bmod 4)$ then the equation $x^{2} \equiv-1(\bmod p)$ does have a solution.

(c) Show that if $p \equiv 2(\bmod 3)$ then the equation $x^{3} \equiv-1(\bmod p)$ has no solution other than $-1(\bmod p)$.

(d) Using the fact that $14^{2} \equiv-3(\bmod 199)$, find a solution of $x^{3} \equiv-1(\bmod 199)$ that is not $-1(\bmod 199)$.

[Hint: how are the complex numbers $\sqrt{-3}$ and $\sqrt[3]{-1}$ related?]

Paper 4, Section II, E

comment(a) What is the highest common factor of two positive integers $a$ and $b$ ? Show that the highest common factor may always be expressed in the form $\lambda a+\mu b$, where $\lambda$ and $\mu$ are integers.

Which positive integers $n$ have the property that, for any positive integers $a$ and $b$, if $n$ divides $a b$ then $n$ divides $a$ or $n$ divides $b$ ? Justify your answer.

Let $a, b, c, d$ be distinct prime numbers. Explain carefully why $a b$ cannot equal $c d$.

[No form of the Fundamental Theorem of Arithmetic may be assumed without proof.]

(b) Now let $S$ be the set of positive integers that are congruent to 1 mod 10 . We say that $x \in S$ is irreducible if $x>1$ and whenever $a, b \in S$ satisfy $a b=x$ then $a=1$ or $b=1$. Do there exist distinct irreducibles $a, b, c, d$ with $a b=c d ?$

Paper 2, Section I, F

commentWhat does it mean to say that events $A_{1}, \ldots, A_{n}$ are (i) pairwise independent, (ii) independent?

Consider pairwise disjoint events $B_{1}, B_{2}, B_{3}$ and $C$, with

$\mathbb{P}\left(B_{1}\right)=\mathbb{P}\left(B_{2}\right)=\mathbb{P}\left(B_{3}\right)=p \text { and } \mathbb{P}(C)=q, \text { where } 3 p+q \leqslant 1$

Let $0 \leqslant q \leqslant 1 / 16$. Prove that the events $B_{1} \cup C, B_{2} \cup C$ and $B_{3} \cup C$ are pairwise independent if and only if

$p=-q+\sqrt{q} .$

Prove or disprove that there exist $p>0$ and $q>0$ such that these three events are independent.

Paper 2, Section I, F

commentLet $X$ be a random variable taking non-negative integer values and let $Y$ be a random variable taking real values.

(a) Define the probability-generating function $G_{X}(s)$. Calculate it explicitly for a Poisson random variable with mean $\lambda>0$.

(b) Define the moment-generating function $M_{Y}(t)$. Calculate it explicitly for a normal random variable $\mathrm{N}(0,1)$.

(c) By considering a random sum of independent copies of $Y$, prove that, for general $X$ and $Y, G_{X}\left(M_{Y}(t)\right)$ is the moment-generating function of some random variable.

Paper 2, Section II, F

commentA circular island has a volcano at its central point. During an eruption, lava flows from the mouth of the volcano and covers a sector with random angle $\Phi$ (measured in radians), whose line of symmetry makes a random angle $\Theta$ with some fixed compass bearing.

The variables $\Theta$ and $\Phi$ are independent. The probability density function of $\Theta$ is constant on $(0,2 \pi)$ and the probability density function of $\Phi$ is of the form $A(\pi-\phi / 2)$ where $0<\phi<2 \pi$, and $A$ is a constant.

(a) Find the value of $A$. Calculate the expected value and the variance of the sector angle $\Phi$. Explain briefly how you would simulate the random variable $\Phi$ using a uniformly distributed random variable $U$.

(b) $H_{1}$ and $H_{2}$ are two houses on the island which are collinear with the mouth of the volcano, but on different sides of it. Find

(i) the probability that $H_{1}$ is hit by the lava;

(ii) the probability that both $H_{1}$ and $H_{2}$ are hit by the lava;

(iii) the probability that $H_{2}$ is not hit by the lava given that $H_{1}$ is hit.

Paper 2, Section II, F

commentI was given a clockwork orange for my birthday. Initially, I place it at the centre of my dining table, which happens to be exactly 20 units long. One minute after I place it on the table it moves one unit towards the left end of the table or one unit towards the right, each with probability 1/2. It continues in this manner at one minute intervals, with the direction of each move being independent of what has gone before, until it reaches either end of the table where it promptly falls off. If it falls off the left end it will break my Ming vase. If it falls off the right end it will land in a bucket of sand leaving the vase intact.

(a) Derive the difference equation for the probability that the Ming vase will survive, in terms of the current distance $k$ from the orange to the left end, where $k=1, \ldots, 19$.

(b) Derive the corresponding difference equation for the expected time when the orange falls off the table.

(c) Write down the general formula for the solution of each of the difference equations from (a) and (b). [No proof is required.]

(d) Based on parts (a)-(c), calculate the probability that the Ming vase will survive if, instead of placing the orange at the centre of the table, I place it initially 3 units from the right end of the table. Calculate the expected time until the orange falls off.

(e) Suppose I place the orange 3 units from the left end of the table. Calculate the probability that the orange will fall off the right end before it reaches a distance 1 unit from the left end of the table.

Paper 2, Section II, F

comment(a) State Markov's inequality.

(b) Let $r$ be a given positive integer. You toss an unbiased coin repeatedly until the first head appears, which occurs on the $H_{1}$ th toss. Next, I toss the same coin until I get my first tail, which occurs on my $T_{1}$ th toss. Then you continue until you get your second head with a further $H_{2}$ tosses; then I continue with a further $T_{2}$ tosses until my second tail. We continue for $r$ turns like this, and generate a sequence $H_{1}, T_{1}, H_{2}, T_{2}, \ldots, H_{r}$, $T_{r}$ of random variables. The total number of tosses made is $Y_{r}$. (For example, for $r=2$, a sequence of outcomes $t t h|t| t t t h \mid h h t$ gives $H_{1}=3, T_{1}=1, H_{2}=4, T_{2}=3$ and $Y_{2}=11$.)

Find the probability-generating functions of the random variables $H_{j}$ and $T_{j}$. Hence or otherwise obtain the mean values $\mathbb{E} H_{j}$ and $\mathbb{E} T_{j}$.

Obtain the probability-generating function of the random variable $Y_{r}$, and find the mean value $\mathbb{E} Y_{r}$.

Prove that, for $n \geqslant 2 r$,

$\mathbb{P}\left(Y_{r}=n\right)=\frac{1}{2^{n}}\left(\begin{array}{c} n-1 \\ 2 r-1 \end{array}\right)$

For $r=1$, calculate $\mathbb{P}\left(Y_{1} \geqslant 5\right)$, and confirm that it satisfies Markov's inequality.

Paper 2, Section II, F

comment(a) Let $B_{1}, \ldots, B_{n}$ be pairwise disjoint events such that their union $B_{1} \cup B_{2} \cup \ldots \cup B_{n}$ gives the whole set of outcomes, with $\mathbb{P}\left(B_{i}\right)>0$ for $1 \leqslant i \leqslant n$. Prove that for any event $A$ with $\mathbb{P}(A)>0$ and for any $i$

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

(b) A prince is equally likely to sleep on any number of mattresses from six to eight; on half the nights a pea is placed beneath the lowest mattress. With only six mattresses his sleep is always disturbed by the presence of a pea; with seven a pea, if present, is unnoticed in one night out of five; and with eight his sleep is undisturbed despite an offending pea in two nights out of five.

What is the probability that, on a given night, the prince's sleep was undisturbed?

On the morning of his wedding day, he announces that he has just spent the most peaceful and undisturbed of nights. What is the expected number of mattresses on which he slept the previous night?

Paper 3, Section I, C

commentState the value of $\partial x_{i} / \partial x_{j}$ and find $\partial r / \partial x_{j}$, where $r=|\mathbf{x}|$.

Vector fields $\mathbf{u}$ and $\mathbf{v}$ in $\mathbb{R}^{3}$ are given by $\mathbf{u}=r^{\alpha} \mathbf{x}$ and $\mathbf{v}=\mathbf{k} \times \mathbf{u}$, where $\alpha$ is a constant and $\mathbf{k}$ is a constant vector. Calculate the second-rank tensor $d_{i j}=\partial u_{i} / \partial x_{j}$, and deduce that $\boldsymbol{\nabla} \times \mathbf{u}=\mathbf{0}$ and $\boldsymbol{\nabla} \cdot \mathbf{v}=0$. When $\alpha=-3$, show that $\boldsymbol{\nabla} \cdot \mathbf{u}=0$ and

$\nabla \times \mathbf{v}=\frac{3(\mathbf{k} \cdot \mathbf{x}) \mathbf{x}-\mathbf{k} r^{2}}{r^{5}}$

Paper 3, Section I, C

commentCartesian coordinates $x, y, z$ and spherical polar coordinates $r, \theta, \phi$ are related by

$x=r \sin \theta \cos \phi, \quad y=r \sin \theta \sin \phi, \quad z=r \cos \theta$

Find scalars $h_{r}, h_{\theta}, h_{\phi}$ and unit vectors $\mathbf{e}_{r}, \mathbf{e}_{\theta}, \mathbf{e}_{\phi}$ such that

$\mathrm{d} \mathbf{x}=h_{r} \mathbf{e}_{r} \mathrm{~d} r+h_{\theta} \mathbf{e}_{\theta} \mathrm{d} \theta+h_{\phi} \mathbf{e}_{\phi} \mathrm{d} \phi$

Verify that the unit vectors are mutually orthogonal.

Hence calculate the area of the open surface defined by $\theta=\alpha, 0 \leqslant r \leqslant R$, $0 \leqslant \phi \leqslant 2 \pi$, where $\alpha$ and $R$ are constants.

Paper 3, Section II, C

commentThe vector fields $\mathbf{A}(\mathbf{x}, t)$ and $\mathbf{B}(\mathbf{x}, t)$ obey the evolution equations

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

where $\mathbf{u}$ is a given vector field and $\psi$ is a given scalar field. Use suffix notation to show that the scalar field $h=\mathbf{A} \cdot \mathbf{B}$ obeys an evolution equation of the form

$\frac{\partial h}{\partial t}=\mathbf{B} \cdot \nabla f-\mathbf{u} \cdot \nabla h$

where the scalar field $f$ should be identified.

Suppose that $\boldsymbol{\nabla} \cdot \mathbf{B}=0$ and $\boldsymbol{\nabla} \cdot \mathbf{u}=0$. Show that, if $\mathbf{u} \cdot \mathbf{n}=\mathbf{B} \cdot \mathbf{n}=0$ on the surface $S$ of a fixed volume $V$ with outward normal $\mathbf{n}$, then

$\frac{\mathrm{d} H}{\mathrm{~d} t}=0, \quad \text { where } H=\int_{V} h \mathrm{~d} V .$

Suppose that $\mathbf{A}=a r^{2} \sin \theta \mathbf{e}_{\theta}+r\left(a^{2}-r^{2}\right) \sin \theta \mathbf{e}_{\phi}$ with respect to spherical polar coordinates, and that $\mathbf{B}=\boldsymbol{\nabla} \times \mathbf{A}$. Show that

$h=a r^{2}\left(a^{2}+r^{2}\right) \sin ^{2} \theta$

and calculate the value of $H$ when $V$ is the sphere $r \leqslant a$.

$\left[\text { In spherical polar coordinates } \nabla \times \mathbf{F}=\frac{1}{r^{2} \sin \theta}\left|\begin{array}{ccc} \mathbf{e}_{r} & r \mathbf{e}_{\theta} & r \sin \theta \mathbf{e}_{\phi} \\ \partial / \partial r & \partial / \partial \theta & \partial / \partial \phi \\ F_{r} & r F_{\theta} & r \sin \theta F_{\phi} \end{array}\right|\right.$

Paper 3, Section II, C

commentThe electric field $\mathbf{E}(\mathbf{x})$ due to a static charge distribution with density $\rho(\mathbf{x})$ satisfies

$\mathbf{E}=-\boldsymbol{\nabla} \phi, \quad \boldsymbol{\nabla} \cdot \mathbf{E}=\frac{\rho}{\varepsilon_{0}},$

where $\phi(\mathbf{x})$ is the corresponding electrostatic potential and $\varepsilon_{0}$ is a constant.

(a) Show that the total charge $Q$ contained within a closed surface $S$ is given by Gauss' Law

$Q=\varepsilon_{0} \int_{S} \mathbf{E} \cdot \mathrm{d} \mathbf{S} .$

Assuming spherical symmetry, deduce the electric field and potential due to a point charge $q$ at the origin i.e. for $\rho(\mathbf{x})=q \delta(\mathbf{x})$.

(b) Let $\mathbf{E}_{1}$ and $\mathbf{E}_{2}$, with potentials $\phi_{1}$ and $\phi_{2}$ respectively, be the solutions to (1) arising from two different charge distributions with densities $\rho_{1}$ and $\rho_{2}$. Show that

$\frac{1}{\varepsilon_{0}} \int_{V} \phi_{1} \rho_{2} \mathrm{~d} V+\int_{\partial V} \phi_{1} \nabla \phi_{2} \cdot \mathrm{d} \mathbf{S}=\frac{1}{\varepsilon_{0}} \int_{V} \phi_{2} \rho_{1} \mathrm{~d} V+\int_{\partial V} \phi_{2} \nabla \phi_{1} \cdot \mathrm{d} \mathbf{S}$

for any region $V$ with boundary $\partial V$, where $\mathrm{d} \mathbf{S}$ points out of $V$.

(c) Suppose that $\rho_{1}(\mathbf{x})=0$ for $|\mathbf{x}| \leqslant a$ and that $\phi_{1}(\mathbf{x})=\Phi$, a constant, on $|\mathbf{x}|=a$. Use the results of (a) and (b) to show that

$\Phi=\frac{1}{4 \pi \varepsilon_{0}} \int_{r>a} \frac{\rho_{1}(\mathbf{x})}{r} \mathrm{~d} V$

[You may assume that $\phi_{1} \rightarrow 0$ as $|\mathbf{x}| \rightarrow \infty$ sufficiently rapidly that any integrals over the 'sphere at infinity' in (2) are zero.]

Paper 3, Section II, C

commentState the divergence theorem for a vector field $\mathbf{u}(\mathbf{x})$ in a region $V$ bounded by a piecewise smooth surface $S$ with outward normal $\mathbf{n}$.

Show, by suitable choice of $\mathbf{u}$, that

$\int_{V} \nabla f \mathrm{~d} V=\int_{S} f \mathrm{~d} \mathbf{S}$

for a scalar field $f(\mathbf{x})$.

Let $V$ be the paraboloidal region given by $z \geqslant 0$ and $x^{2}+y^{2}+c z \leqslant a^{2}$, where $a$ and $c$ are positive constants. Verify that $(*)$ holds for the scalar field $f=x z$.

Paper 3, Section II, C

commentWrite down the most general isotropic tensors of rank 2 and 3. Use the tensor transformation law to show that they are, indeed, isotropic.

Let $V$ be the sphere $0 \leqslant r \leqslant a$. Explain briefly why

$T_{i_{1} \ldots i_{n}}=\int_{V} x_{i_{1}} \ldots x_{i_{n}} \mathrm{~d} V$

is an isotropic tensor for any $n$. Hence show that

$\int_{V} x_{i} x_{j} \mathrm{~d} V=\alpha \delta_{i j}, \quad \int_{V} x_{i} x_{j} x_{k} \mathrm{~d} V=0 \quad \text { and } \int_{V} x_{i} x_{j} x_{k} x_{l} \mathrm{~d} V=\beta\left(\delta_{i j} \delta_{k l}+\delta_{i k} \delta_{j l}+\delta_{i l} \delta_{j k}\right)$

for some scalars $\alpha$ and $\beta$, which should be determined using suitable contractions of the indices or otherwise. Deduce the value of

$\int_{V} \mathbf{x} \times(\boldsymbol{\Omega} \times \mathbf{x}) \mathrm{d} V$

where $\boldsymbol{\Omega}$ is a constant vector.

[You may assume that the most general isotropic tensor of rank 4 is

$\lambda \delta_{i j} \delta_{k l}+\mu \delta_{i k} \delta_{j l}+\nu \delta_{i l} \delta_{j k}$

where $\lambda, \mu$ and $\nu$ are scalars.]

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

commentFor $z, a \in \mathbb{C}$ define the principal value of $\log z$ and hence of $z^{a}$. Hence find all solutions to (i) $z^{\mathrm{i}}=1$ (ii) $z^{\mathrm{i}}+\bar{z}^{\mathrm{i}}=2 \mathrm{i}$,

and sketch the curve $\left|z^{\mathrm{i}+1}\right|=1$.

Paper 1, Section I, A

commentThe matrix

$A=\left(\begin{array}{rr} 1 & -1 \\ 2 & 2 \\ -1 & 1 \end{array}\right)$

represents a linear map $\Phi: \mathbb{R}^{2} \rightarrow \mathbb{R}^{3}$ with respect to the bases

$B=\left\{\left(\begin{array}{l} 1 \\ 1 \end{array}\right),\left(\begin{array}{r} 1 \\ -1 \end{array}\right)\right\} \quad, \quad C=\left\{\left(\begin{array}{l} 1 \\ 1 \\ 0 \end{array}\right),\left(\begin{array}{l} 0 \\ 1 \\ 0 \end{array}\right),\left(\begin{array}{l} 0 \\ 1 \\ 1 \end{array}\right)\right\}$

Find the matrix $A^{\prime}$ that represents $\Phi$ with respect to the bases

$B^{\prime}=\left\{\left(\begin{array}{l} 0 \\ 2 \end{array}\right),\left(\begin{array}{l} 2 \\ 0 \end{array}\right)\right\} \quad, \quad C^{\prime}=\left\{\left(\begin{array}{r} 1 \\ 0 \\ -1 \end{array}\right),\left(\begin{array}{l} 0 \\ 1 \\ 0 \end{array}\right),\left(\begin{array}{l} 1 \\ 2 \\ 1 \end{array}\right)\right\}$

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

commentExplain why each of the equations

$\begin{aligned} &\mathbf{x}=\mathbf{a}+\lambda \mathbf{b} \\ &\mathbf{x} \times \mathbf{c}=\mathbf{d} \end{aligned}$

describes a straight line, where $\mathbf{a}, \mathbf{b}, \mathbf{c}$ and $\mathbf{d}$ are constant vectors in $\mathbb{R}^{3}, \mathbf{b}$ and $\mathbf{c}$ are non-zero, $\mathbf{c} \cdot \mathbf{d}=0$ and $\lambda$ is a real parameter. Describe the geometrical relationship of a, $\mathbf{b}, \mathbf{c}$ and $\mathbf{d}$ to the relevant line, assuming that $\mathbf{d} \neq \mathbf{0}$.

Show that the solutions of (2) satisfy an equation of the form (1), defining $\mathbf{a}, \mathbf{b}$ and $\lambda(\mathbf{x})$ in terms of $\mathbf{c}$ and $\mathbf{d}$ such that $\mathbf{a} \cdot \mathbf{b}=0$ and $|\mathbf{b}|=|\mathbf{c}|$. Deduce that the conditions on $\mathbf{c}$ and $\mathbf{d}$ are sufficient for (2) to have solutions.

For each of the lines described by (1) and (2), find the point $\mathbf{x}$ that is closest to a given fixed point $\mathbf{y}$.

Find the line of intersection of the two planes $\mathbf{x} \cdot \mathbf{m}=\mu$ and $\mathbf{x} \cdot \mathbf{n}=\nu$, where $\mathbf{m}$ and $\mathbf{n}$ are constant unit vectors, $\mathbf{m} \times \mathbf{n} \neq \mathbf{0}$ and $\mu$ and $\nu$ are constants. Express your answer in each of the forms (1) and (2), giving both $\mathbf{a}$ and $\mathbf{d}$ as linear combinations of $\mathbf{m}$ and $\mathbf{n}$.

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

commentThe map $\Phi(\mathbf{x})=\mathbf{n} \times(\mathbf{x} \times \mathbf{n})+\alpha(\mathbf{n} \cdot \mathbf{x}) \mathbf{n}$ is defined for $\mathbf{x} \in \mathbb{R}^{3}$, where $\mathbf{n}$ is a unit vector in $\mathbb{R}^{3}$ and $\alpha$ is a constant.

(a) Find the inverse map $\Phi^{-1}$, when it exists, and determine the values of $\alpha$ for which it does.

(b) When $\Phi$ is not invertible, find its image and kernel, and explain geometrically why these subspaces are perpendicular.

(c) Let $\mathbf{y}=\Phi(\mathbf{x})$. Find the components $A_{i j}$ of the matrix $A$ such that $y_{i}=A_{i j} x_{j}$. When $\Phi$ is invertible, find the components of the matrix $B$ such that $x_{i}=B_{i j} y_{j}$.

(d) Now let $A$ be as defined in (c) for the case $\mathbf{n}=\frac{1}{\sqrt{3}}(1,1,1)$, and let

$C=\frac{1}{3}\left(\begin{array}{rrr} 2 & 2 & -1 \\ -1 & 2 & 2 \\ 2 & -1 & 2 \end{array}\right)$

By analysing a suitable determinant, for all values of $\alpha$ find all vectors $\mathbf{x}$ such that $A \mathbf{x}=C \mathbf{x}$. Explain your results by interpreting $A$ and $C$ geometrically.

Paper 1, Section II, B

comment(a) Let $M$ be a real symmetric $n \times n$ matrix. Prove the following.

(i) Each eigenvalue of $M$ is real.

(ii) Each eigenvector can be chosen to be real.

(iii) Eigenvectors with different eigenvalues are orthogonal.

(b) Let $A$ be a real antisymmetric $n \times n$ matrix. Prove that each eigenvalue of $A^{2}$ is real and is less than or equal to zero.

If $-\lambda^{2}$ and $-\mu^{2}$ are distinct, non-zero eigenvalues of $A^{2}$, show that there exist orthonormal vectors $\mathbf{u}, \mathbf{u}^{\prime}, \mathbf{w}, \mathbf{w}^{\prime}$ with

$\begin{array}{rlr} A \mathbf{u}=\lambda \mathbf{u}^{\prime}, & A \mathbf{w}=\mu \mathbf{w}^{\prime} \\ A \mathbf{u}^{\prime}=-\lambda \mathbf{u}, & A \mathbf{w}^{\prime}=-\mu \mathbf{w} \end{array}$

Part IA, 2011 List of Questions

Paper 1, Section II, B

comment(a) Find the eigenvalues and eigenvectors of the matrix

$M=\left(\begin{array}{rrr} 2 & 0 & 1 \\ 1 & 1 & 1 \\ 2 & -2 & 3 \end{array}\right)$

(b) Under what conditions on the $3 \times 3$ matrix $A$ and the vector $\mathbf{b}$ in $\mathbb{R}^{3}$ does the equation

$A \mathbf{x}=\mathbf{b}$

have 0,1 , or infinitely many solutions for the vector $\mathbf{x}$ in $\mathbb{R}^{3}$ ? Give clear, concise arguments to support your answer, explaining why just these three possibilities are allowed.

(c) Using the results of $(\mathrm{a})$, or otherwise, find all solutions to $(*)$ when

$A=M-\lambda I \quad \text { and } \quad \mathbf{b}=\left(\begin{array}{l} 4 \\ 3 \\ 2 \end{array}\right)$

in each of the cases $\lambda=0,1,2$.