Part IA, 2016

Analysis I

• Paper 1, Section I, D

  Analysis I | Part IA, 2016

  What does it mean to say that a sequence of real numbers $\left(x_{n}\right)$ converges to $x$ ? Suppose that $\left(x_{n}\right)$ converges to $x$. Show that the sequence $\left(y_{n}\right)$ given by

  $$y_{n}=\frac{1}{n} \sum_{i=1}^{n} x_{i}$$

  also converges to $x$.

  comment

• Paper 1, Section I, F

  Analysis I | Part IA, 2016

  Let $a_{n}$ be the number of pairs of integers $(x, y) \in \mathbb{Z}^{2}$ such that $x^{2}+y^{2} \leqslant n^{2}$. What is the radius of convergence of the series $\sum_{n=0}^{\infty} a_{n} z^{n}$ ? [You may use the comparison test, provided you state it clearly.]

  comment

• Paper 1, Section II, 12F

  Analysis I | Part IA, 2016

  Let $f:[0,1] \rightarrow \mathbb{R}$ satisfy $|f(x)-f(y)| \leqslant|x-y|$ for all $x, y \in[0,1]$.

  Show that $f$ is continuous and that for all $\varepsilon>0$, there exists a piecewise constant function $g$ such that

  $$\sup _{x \in[0,1]}|f(x)-g(x)| \leqslant \varepsilon .$$

  For all integers $n \geqslant 1$, let $u_{n}=\int_{0}^{1} f(t) \cos (n t) d t$. Show that the sequence $\left(u_{n}\right)$ converges to 0 .

  comment

• Paper 1, Section II, D

  Analysis I | Part IA, 2016

  If $\left(x_{n}\right)$ and $\left(y_{n}\right)$ are sequences converging to $x$ and $y$ respectively, show that the sequence $\left(x_{n}+y_{n}\right)$ converges to $x+y$.

  If $x_{n} \neq 0$ for all $n$ and $x \neq 0$, show that the sequence $\left(\frac{1}{x_{n}}\right)$ converges to $\frac{1}{x}$.

  (a) Find $\lim _{n \rightarrow \infty}\left(\sqrt{n^{2}+n}-n\right)$.

  (b) Determine whether $\sum_{n=1}^{\infty} \frac{\sqrt{n+1}-\sqrt{n}}{\sqrt{n}}$ converges.

  Justify your answers.

  comment

• Paper 1, Section II, E

  Analysis I | Part IA, 2016

  Let $f: \mathbb{R} \rightarrow \mathbb{R}$. We say that $x \in \mathbb{R}$ is a real root of $f$ if $f(x)=0$. Show that if $f$ is differentiable and has $k$ distinct real roots, then $f^{\prime}$ has at least $k-1$ real roots. [Rolle's theorem may be used, provided you state it clearly.]

  Let $p(x)=\sum_{i=1}^{n} a_{i} x^{d_{i}}$ be a polynomial in $x$, where all $a_{i} \neq 0$ and $d_{i+1}>d_{i}$. (In other words, the $a_{i}$ are the nonzero coefficients of the polynomial, arranged in order of increasing power of $x$.) The number of sign changes in the coefficients of $p$ is the number of $i$ for which $a_{i} a_{i+1}<0$. For example, the polynomial $x^{5}-x^{3}-x^{2}+1$ has 2 sign changes. Show by induction on $n$ that the number of positive real roots of $p$ is less than or equal to the number of sign changes in its coefficients.

  comment

• Paper 1, Section II, E

  Analysis I | Part IA, 2016

  State the Bolzano-Weierstrass theorem. Use it to show that a continuous function $f:[a, b] \rightarrow \mathbb{R}$ attains a global maximum; that is, there is a real number $c \in[a, b]$ such that $f(c) \geqslant f(x)$ for all $x \in[a, b]$.

  A function $f$ is said to attain a local maximum at $c \in \mathbb{R}$ if there is some $\varepsilon>0$ such that $f(c) \geqslant f(x)$ whenever $|x-c|<\varepsilon$. Suppose that $f: \mathbb{R} \rightarrow \mathbb{R}$ is twice differentiable, and that $f^{\prime \prime}(x)<0$ for all $x \in \mathbb{R}$. Show that there is at most one $c \in \mathbb{R}$ at which $f$ attains a local maximum.

  If there is a constant $K<0$ such that $f^{\prime \prime}(x)<K$ for all $x \in \mathbb{R}$, show that $f$ attains a global maximum. [Hint: if $g^{\prime}(x)<0$ for all $x \in \mathbb{R}$, then $g$ is decreasing.]

  Must $f: \mathbb{R} \rightarrow \mathbb{R}$ attain a global maximum if we merely require $f^{\prime \prime}(x)<0$ for all $x \in \mathbb{R} ?$ Justify your answer.

  comment

Differential Equations

• Paper 2, Section $I$, A

  Differential Equations | Part IA, 2016

  (a) For each non-negative integer $n$ and positive constant $\lambda$, let

  $$I_{n}(\lambda)=\int_{0}^{\infty} x^{n} e^{-\lambda x} d x$$

  By differentiating $I_{n}$ with respect to $\lambda$, find its value in terms of $n$ and $\lambda$.

  (b) By making the change of variables $x=u+v, y=u-v$, transform the differential equation

  $$\frac{\partial^{2} f}{\partial x \partial y}=1$$

  into a differential equation for $g$, where $g(u, v)=f(x, y)$.

  comment

• Paper 2, Section I, A

  Differential Equations | Part IA, 2016

  (a) Find the solution of the differential equation

  $$y^{\prime \prime}-y^{\prime}-6 y=0$$

  that is bounded as $x \rightarrow \infty$ and satisfies $y=1$ when $x=0$.

  (b) Solve the difference equation

  $$\left(y_{n+1}-2 y_{n}+y_{n-1}\right)-\frac{h}{2}\left(y_{n+1}-y_{n-1}\right)-6 h^{2} y_{n}=0 .$$

  Show that if $0<h \ll 1$, the solution that is bounded as $n \rightarrow \infty$ and satisfies $y_{0}=1$ is approximately $(1-2 h)^{n}$.

  (c) By setting $x=n h$, explain the relation between parts (a) and (b).

  comment

• Paper 2, Section II, $6 A$

  Differential Equations | Part IA, 2016

  (a) The function $y(x)$ satisfies

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

  (i) Define the Wronskian $W(x)$ of two linearly independent solutions $y_{1}(x)$ and $y_{2}(x)$. Derive a linear first-order differential equation satisfied by $W(x)$.

  (ii) Suppose that $y_{1}(x)$ is known. Use the Wronskian to write down a first-order differential equation for $y_{2}(x)$. Hence express $y_{2}(x)$ in terms of $y_{1}(x)$ and $W(x)$.

  (b) Verify that $y_{1}(x)=\cos \left(x^{\gamma}\right)$ is a solution of

  $$a x^{\alpha} y^{\prime \prime}+b x^{\alpha-1} y^{\prime}+y=0,$$

  where $a, b, \alpha$ and $\gamma$ are constants, provided that these constants satisfy certain conditions which you should determine.

  Use the method that you described in part (a) to find a solution which is linearly independent of $y_{1}(x)$.

  comment

• Paper 2, Section II, A

  Differential Equations | Part IA, 2016

  (a) Find and sketch the solution of

  $$y^{\prime \prime}+y=\delta(x-\pi / 2)$$

  where $\delta$ is the Dirac delta function, subject to $y(0)=1$ and $y^{\prime}(0)=0$.

  (b) A bowl of soup, which Sam has just warmed up, cools down at a rate equal to the product of a constant $k$ and the difference between its temperature $T(t)$ and the temperature $T_{0}$ of its surroundings. Initially the soup is at temperature $T(0)=\alpha T_{0}$, where $\alpha>2$.

  (i) Write down and solve the differential equation satisfied by $T(t)$.

  (ii) At time $t_{1}$, when the temperature reaches half of its initial value, Sam quickly adds some hot water to the soup, so the temperature increases instantaneously by $\beta$, where $\beta>\alpha T_{0} / 2$. Find $t_{1}$ and $T(t)$ for $t>t_{1}$.

  (iii) Sketch $T(t)$ for $t>0$.

  (iv) Sam wants the soup to be at temperature $\alpha T_{0}$ at time $t_{2}$, where $t_{2}>t_{1}$. What value of $\beta$ should Sam choose to achieve this? Give your answer in terms of $\alpha$, $k, t_{2}$ and $T_{0}$.

  comment

• Paper 2, Section II, A

  Differential Equations | Part IA, 2016

  (a) By considering eigenvectors, find the general solution of the equations

  $$\tag{†} \begin{aligned} &\frac{d x}{d t}=2 x+5 y \\ &\frac{d y}{d t}=-x-2 y \end{aligned}$$

  and show that it can be written in the form

  $$\left(\begin{array}{l} x \\ y \end{array}\right)=\alpha\left(\begin{array}{c} 5 \cos t \\ -2 \cos t-\sin t \end{array}\right)+\beta\left(\begin{array}{c} 5 \sin t \\ \cos t-2 \sin t \end{array}\right)$$

  where $\alpha$ and $\beta$ are constants.

  (b) For any square matrix $M$, $\exp (M)$ is defined by

  $$\exp (M)=\sum_{n=0}^{\infty} \frac{M^{n}}{n !}$$

  Show that if $M$ has constant elements, the vector equation $\frac{d \mathbf{x}}{d t}=M \mathbf{x}$ has a solution $\mathbf{x}=\exp (M t) \mathbf{x}_{0}$, where $\mathbf{x}_{0}$ is a constant vector. Hence solve $(†)$ and show that your solution is consistent with the result of part (a).

  comment

• Paper 2, Section II, A

  Differential Equations | Part IA, 2016

  The function $y(x)$ satisfies

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

  What does it mean to say that the point $x=0$ is (i) an ordinary point and (ii) a regular singular point of this differential equation? Explain what is meant by the indicial equation at a regular singular point. What can be said about the nature of the solutions in the neighbourhood of a regular singular point in the different cases that arise according to the values of the roots of the indicial equation?

  State the nature of the point $x=0$ of the equation

  $$x y^{\prime \prime}+(x-m+1) y^{\prime}-(m-1) y=0$$

  Set $y(x)=x^{\sigma} \sum_{n=0}^{\infty} a_{n} x^{n}$, where $a_{0} \neq 0$, and find the roots of the indicial equation.

  (a) Show that one solution of $(*)$ with $m \neq 0,-1,-2, \cdots$ is

  $$y(x)=x^{m}\left(1+\sum_{n=1}^{\infty} \frac{(-1)^{n} x^{n}}{(m+n)(m+n-1) \cdots(m+1)}\right)$$

  and find a linearly independent solution in the case when $m$ is not an integer.

  (b) If $m$ is a positive integer, show that $(*)$ has a polynomial solution.

  (c) What is the form of the general solution of $(*)$ in the case $m=0$ ? [You do not need to find the general solution explicitly.]

  comment

Dynamics and Relativity

• Paper 4, Section $I$, B

  Dynamics and Relativity | Part IA, 2016

  The radial equation of motion of a particle moving under the influence of a central force is

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

  where $h$ is the angular momentum per unit mass of the particle, $n$ is a constant, and $k$ is a positive constant.

  Show that circular orbits with $r=a$ are possible for any positive value of $a$, and that they are stable to small perturbations that leave $h$ unchanged if $n>-3$.

  comment

• Paper 4, Section I, B

  Dynamics and Relativity | Part IA, 2016

  With the help of definitions or equations of your choice, determine the dimensions, in terms of mass $(M)$, length $(L)$, time $(T)$ and charge $(Q)$, of the following quantities:

  (i) force;

  (ii) moment of a force (i.e. torque);

  (iii) energy;

  (iv) Newton's gravitational constant $G$;

  (v) electric field $\mathbf{E}$;

  (vi) magnetic field $\mathbf{B}$;

  (vii) the vacuum permittivity $\epsilon_{0}$.

  comment

• Paper 4, Section II, B

  Dynamics and Relativity | Part IA, 2016

  State what the vectors $\mathbf{a}, \mathbf{r}, \mathbf{v}$ and $\boldsymbol{\omega}$ represent in the following equation:

  $$\mathbf{a}=\mathbf{g}-2 \boldsymbol{\omega} \times \mathbf{v}-\boldsymbol{\omega} \times(\boldsymbol{\omega} \times \mathbf{r})$$

  where $\mathbf{g}$ is the acceleration due to gravity.

  Assume that the radius of the Earth is $6 \times 10^{6} \mathrm{~m}$, that $|\mathrm{g}|=10 \mathrm{~ms}^{-2}$, and that there are $9 \times 10^{4}$ seconds in a day. Use these data to determine roughly the order of magnitude of each term on the right hand side of $(*)$ in the case of a particle dropped from a point at height $20 \mathrm{~m}$ above the surface of the Earth.

  Taking again $|\mathbf{g}|=10 \mathrm{~ms}^{-2}$, find the time $T$ of the particle's fall in the absence of rotation.

  Use a suitable approximation scheme to show that

  $$\mathbf{R} \approx \mathbf{R}_{0}-\frac{1}{3} \boldsymbol{\omega} \times \mathbf{g} T^{3}-\frac{1}{2} \boldsymbol{\omega} \times\left(\boldsymbol{\omega} \times \mathbf{R}_{0}\right) T^{2},$$

  where $\mathbf{R}$ is the position vector of the point at which the particle lands, and $\mathbf{R}_{0}$ is the position vector of the point at which the particle would have landed in the absence of rotation.

  The particle is dropped at latitude $45^{\circ}$. Find expressions for the approximate northerly and easterly displacements of $\mathbf{R}$ from $\mathbf{R}_{0}$ in terms of $\omega, g, R_{0}$ (the magnitudes of $\boldsymbol{\omega}, \mathbf{g}$ and $\mathbf{R}_{0}$, respectively), and $T$. You should ignore the curvature of the Earth's surface.

  comment

• Paper 4, Section II, B

  Dynamics and Relativity | Part IA, 2016

  (a) Alice travels at constant speed $v$ to Alpha Centauri, which is at distance $d$ from Earth. She then turns around (taking very little time to do so), and returns at speed $v$. Bob stays at home. By how much has Bob aged during the journey? By how much has Alice aged? [No justification is required.]

  Briefly explain what is meant by the twin paradox in this context. Why is it not a paradox?

  (b) Suppose instead that Alice's world line is given by

  $$-c^{2} t^{2}+x^{2}=c^{2} t_{0}^{2},$$

  where $t_{0}$ is a positive constant. Bob stays at home, at $x=\alpha c t_{0}$, where $\alpha>1$. Alice and Bob compare their ages on both occasions when they meet. By how much does Bob age? Show that Alice ages by $2 t_{0} \cosh ^{-1} \alpha$.

  comment

• Paper 4, Section II, B

  Dynamics and Relativity | Part IA, 2016

  A particle of unit mass moves with angular momentum $h$ in an attractive central force field of magnitude $\frac{k}{r^{2}}$, where $r$ is the distance from the particle to the centre and $k$ is a constant. You may assume that the equation of its orbit can be written in plane polar coordinates in the form

  $$r=\frac{\ell}{1+e \cos \theta}$$

  where $\ell=\frac{h^{2}}{k}$ and $e$ is the eccentricity. Show that the energy of the particle is

  $$\frac{h^{2}\left(e^{2}-1\right)}{2 \ell^{2}}$$

  A comet moves in a parabolic orbit about the Sun. When it is at its perihelion, a distance $d$ from the Sun, and moving with speed $V$, it receives an impulse which imparts an additional velocity of magnitude $\alpha V$ directly away from the Sun. Show that the eccentricity of its new orbit is $\sqrt{1+4 \alpha^{2}}$, and sketch the two orbits on the same axes.

  comment

• Paper 4, Section II, B

  Dynamics and Relativity | Part IA, 2016

  (a) A rocket, moving non-relativistically, has speed $v(t)$ and mass $m(t)$ at a time $t$ after it was fired. It ejects mass with constant speed $u$ relative to the rocket. Let the total momentum, at time $t$, of the system (rocket and ejected mass) in the direction of the motion of the rocket be $P(t)$. Explain carefully why $P(t)$ can be written in the form

  $$\tag{*} P(t)=m(t) v(t)-\int_{0}^{t}(v(\tau)-u) \frac{d m(\tau)}{d \tau} d \tau$$

  If the rocket experiences no external force, show that

  $$\tag{†} m \frac{d v}{d t}+u \frac{d m}{d t}=0$$

  Derive the expression corresponding to $(*)$ for the total kinetic energy of the system at time $t$. Show that kinetic energy is not necessarily conserved.

  (b) Explain carefully how $(*)$ should be modified for a rocket moving relativistically, given that there are no external forces. Deduce that

  $$\frac{d(m \gamma v)}{d t}=\left(\frac{v-u}{1-u v / c^{2}}\right) \frac{d(m \gamma)}{d t}$$

  where $\gamma=\left(1-v^{2} / c^{2}\right)^{-\frac{1}{2}}$ and hence that

  $$\tag{‡} m \gamma^{2} \frac{d v}{d t}+u \frac{d m}{d t}=0$$

  (c) Show that $(†)$ and $(‡)$ agree in the limit $c \rightarrow \infty$. Briefly explain the fact that kinetic energy is not conserved for the non-relativistic rocket, but relativistic energy is conserved for the relativistic rocket.

  comment

Groups

• Paper 3, Section I, D

  Groups | Part IA, 2016

  State and prove Lagrange's theorem.

  Let $p$ be an odd prime number, and let $G$ be a finite group of order $2 p$ which has a normal subgroup of order 2 . Show that $G$ is a cyclic group.

  comment

• Paper 3, Section I, D

  Groups | Part IA, 2016

  Let $G$ be a group, and let $H$ be a subgroup of $G$. Show that the following are equivalent.

  (i) $a^{-1} b^{-1} a b \in H$ for all $a, b \in G$.

  (ii) $H$ is a normal subgroup of $G$ and $G / H$ is abelian.

  Hence find all abelian quotient groups of the dihedral group $D_{10}$ of order 10 .

  comment

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

  Groups | Part IA, 2016

  State and prove the orbit-stabiliser theorem.

  Let $p$ be a prime number, and $G$ be a finite group of order $p^{n}$ with $n \geqslant 1$. If $N$ is a non-trivial normal subgroup of $G$, show that $N \cap Z(G)$ contains a non-trivial element.

  If $H$ is a proper subgroup of $G$, show that there is a $g \in G \backslash H$ such that $g^{-1} H g=H$.

  [You may use Lagrange's theorem, provided you state it clearly.]

  comment

• Paper 3, Section II, D

  Groups | Part IA, 2016

  Define the Möbius group $\mathcal{M}$ and its action on the Riemann sphere $\mathbb{C}_{\infty}$. [You are not required to verify the group axioms.] Show that there is a surjective group homomorphism $\phi: S L_{2}(\mathbb{C}) \rightarrow \mathcal{M}$, and find the kernel of $\phi .$

  Show that if a non-trivial element of $\mathcal{M}$ has finite order, then it fixes precisely two points in $\mathbb{C}_{\infty}$. Hence show that any finite abelian subgroup of $\mathcal{M}$ is either cyclic or isomorphic to $C_{2} \times C_{2}$.

  [You may use standard properties of the Möbius group, provided that you state them clearly.]

  comment

• Paper 3, Section II, D

  Groups | Part IA, 2016

  Define the sign, $\operatorname{sgn}(\sigma)$, of a permutation $\sigma \in S_{n}$ and prove that it is well defined. Show that the function $\operatorname{sgn}: S_{n} \rightarrow\{1,-1\}$ is a homomorphism.

  Show that there is an injective homomorphism $\psi: G L_{2}(\mathbb{Z} / 2 \mathbb{Z}) \rightarrow S_{4}$ such that $\operatorname{sgn} \circ \psi$ is non-trivial.

  Show that there is an injective homomorphism $\phi: S_{n} \rightarrow G L_{n}(\mathbb{R})$ such that $\operatorname{det}(\phi(\sigma))=\operatorname{sgn}(\sigma) .$

  comment

• Paper 3, Section II, D

  Groups | Part IA, 2016

  For each of the following, either give an example or show that none exists.

  (i) A non-abelian group in which every non-trivial element has order $2 .$

  (ii) A non-abelian group in which every non-trivial element has order 3 .

  (iii) An element of $S_{9}$ of order 18 .

  (iv) An element of $S_{9}$ of order 20 .

  (v) A finite group which is not isomorphic to a subgroup of an alternating group.

  comment

Numbers and Sets

• Paper 4, Section I, E

  Numbers and Sets | Part IA, 2016

  Explain the meaning of the phrase least upper bound; state the least upper bound property of the real numbers. Use the least upper bound property to show that a bounded, increasing sequence of real numbers converges.

  Suppose that $a_{n}, b_{n} \in \mathbb{R}$ and that $a_{n} \geqslant b_{n}>0$ for all $n$. If $\sum_{n=1}^{\infty} a_{n}$ converges, show that $\sum_{n=1}^{\infty} b_{n}$ converges.

  comment

• Paper 4, Section I, E

  Numbers and Sets | Part IA, 2016

  Find a pair of integers $x$ and $y$ satisfying $17 x+29 y=1$. What is the smallest positive integer congruent to $17^{138}$ modulo 29 ?

  comment

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

  Numbers and Sets | Part IA, 2016

  Suppose that $a, b \in \mathbb{Z}$ and that $b=b_{1} b_{2}$, where $b_{1}$ and $b_{2}$ are relatively prime and greater than 1. Show that there exist unique integers $a_{1}, a_{2}, n \in \mathbb{Z}$ such that $0 \leqslant a_{i}<b_{i}$ and

  $$\frac{a}{b}=\frac{a_{1}}{b_{1}}+\frac{a_{2}}{b_{2}}+n$$

  Now let $b=p_{1}^{n_{1}} \cdots p_{k}^{n_{k}}$ be the prime factorization of $b$. Deduce that $\frac{a}{b}$ can be written uniquely in the form

  $$\frac{a}{b}=\frac{q_{1}}{p_{1}^{n_{1}}}+\cdots+\frac{q_{k}}{p_{k}^{n_{k}}}+n$$

  where $0 \leqslant q_{i}<p_{i}^{n_{i}}$ and $n \in \mathbb{Z}$. Express $\frac{a}{b}=\frac{1}{315}$ in this form.

  comment

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

  Numbers and Sets | Part IA, 2016

  State the inclusion-exclusion principle.

  Let $A=\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ be a string of $n$ digits, where $a_{i} \in\{0,1, \ldots, 9\}$. We say that the string $A$ has a run of length $k$ if there is some $j \leqslant n-k+1$ such that either $a_{j+i} \equiv a_{j}+i(\bmod 10)$ for all $0 \leqslant i<k$ or $a_{j+i} \equiv a_{j}-i(\bmod 10)$ for all $0 \leqslant i<k$. For example, the strings

  $$(\underline{0,1,2}, 8,4,9),(3, \underline{9,8,7}, 4,8) \text { and }(3, \underline{1,0,9}, 4,5)$$

  all have runs of length 3 (underlined), but no run in $(3,1,2,1,1,2)$ has length $>2$. How many strings of length 6 have a run of length $\geqslant 3$ ?

  comment

• Paper 4, Section II, 8E

  Numbers and Sets | Part IA, 2016

  Define the binomial coefficient $\left(\begin{array}{c}n \\ m\end{array}\right)$. Prove directly from your definition that

  $$(1+z)^{n}=\sum_{m=0}^{n}\left(\begin{array}{c} n \\ m \end{array}\right) z^{m}$$

  for any complex number $z$.

  (a) Using this formula, or otherwise, show that

  $$\sum_{k=0}^{3 n}(-3)^{k}\left(\begin{array}{l} 6 n \\ 2 k \end{array}\right)=2^{6 n}$$

  (b) By differentiating, or otherwise, evaluate $\sum_{m=0}^{n} m\left(\begin{array}{c}n \\ m\end{array}\right)$.

  Let $S_{r}(n)=\sum_{m=0}^{n}(-1)^{m} m^{r}\left(\begin{array}{c}n \\ m\end{array}\right)$, where $r$ is a non-negative integer. Show that $S_{r}(n)=0$ for $r<n$. Evaluate $S_{n}(n)$.

  comment

• Paper 4, Section II, E

  Numbers and Sets | Part IA, 2016

  (a) Let $S$ be a set. Show that there is no bijective map from $S$ to the power set of $S$. Let $\mathcal{T}=\left\{\left(x_{n}\right) \mid x_{i} \in\{0,1\}\right.$ for all $\left.i \in \mathbb{N}\right\}$ be the set of sequences with entries in $\{0,1\} .$ Show that $\mathcal{T}$ is uncountable.

  (b) Let $A$ be a finite set with more than one element, and let $B$ be a countably infinite set. Determine whether each of the following sets is countable. Justify your answers.

  (i) $S_{1}=\{f: A \rightarrow B \mid f$ is injective $\}$.

  (ii) $S_{2}=\{g: B \rightarrow A \mid g$ is surjective $\}$.

  (iii) $S_{3}=\{h: B \rightarrow B \mid h$ is bijective $\}$.

  comment

Probability

• Paper 2, Section I, $4 \mathrm{~F}$

  Probability | Part IA, 2016

  Define the moment-generating function $m_{Z}$ of a random variable $Z$. Let $X_{1}, \ldots, X_{n}$ be independent and identically distributed random variables with distribution $\mathcal{N}(0,1)$, and let $Z=X_{1}^{2}+\cdots+X_{n}^{2}$. For $\theta<1 / 2$, show that

  $$m_{Z}(\theta)=(1-2 \theta)^{-n / 2} .$$

  comment

• Paper 2, Section I, F

  Probability | Part IA, 2016

  Let $X_{1}, \ldots, X_{n}$ be independent random variables, all with uniform distribution on $[0,1]$. What is the probability of the event $\left\{X_{1}>X_{2}>\cdots>X_{n-1}>X_{n}\right\}$ ?

  comment

• Paper 2, Section II, F

  Probability | Part IA, 2016

  A random graph with $n$ nodes $v_{1}, \ldots, v_{n}$ is drawn by placing an edge with probability $p$ between $v_{i}$ and $v_{j}$ for all distinct $i$ and $j$, independently. A triangle is a set of three distinct nodes $v_{i}, v_{j}, v_{k}$ that are all connected: there are edges between $v_{i}$ and $v_{j}$, between $v_{j}$ and $v_{k}$ and between $v_{i}$ and $v_{k}$.

  (a) Let $T$ be the number of triangles in this random graph. Compute the maximum value and the expectation of $T$.

  (b) State the Markov inequality. Show that if $p=1 / n^{\alpha}$, for some $\alpha>1$, then $\mathbb{P}(T=0) \rightarrow 1$ when $n \rightarrow \infty$

  (c) State the Chebyshev inequality. Show that if $p$ is such that $\operatorname{Var}[T] / \mathbb{E}[T]^{2} \rightarrow 0$ when $n \rightarrow \infty$, then $\mathbb{P}(T=0) \rightarrow 0$ when $n \rightarrow \infty$

  comment

• Paper 2, Section II, F

  Probability | Part IA, 2016

  Let $X$ be a non-negative random variable such that $\mathbb{E}\left[X^{2}\right]>0$ is finite, and let $\theta \in[0,1]$.

  (a) Show that

  $$\mathbb{E}[X \mathbb{I}[\{X>\theta \mathbb{E}[X]\}]] \geqslant(1-\theta) \mathbb{E}[X]$$

  (b) Let $Y_{1}$ and $Y_{2}$ be random variables such that $\mathbb{E}\left[Y_{1}^{2}\right]$ and $\mathbb{E}\left[Y_{2}^{2}\right]$ are finite. State and prove the Cauchy-Schwarz inequality for these two variables.

  (c) Show that

  $$\mathbb{P}(X>\theta \mathbb{E}[X]) \geqslant(1-\theta)^{2} \frac{\mathbb{E}[X]^{2}}{\mathbb{E}\left[X^{2}\right]}$$

  comment

• Paper 2, Section II, F

  Probability | Part IA, 2016

  We randomly place $n$ balls in $m$ bins independently and uniformly. For each $i$ with $1 \leqslant i \leqslant m$, let $B_{i}$ be the number of balls in bin $i$.

  (a) What is the distribution of $B_{i}$ ? For $i \neq j$, are $B_{i}$ and $B_{j}$ independent?

  (b) Let $E$ be the number of empty bins, $C$ the number of bins with two or more balls, and $S$ the number of bins with exactly one ball. What are the expectations of $E, C$ and $S$ ?

  (c) Let $m=a n$, for an integer $a \geqslant 2$. What is $\mathbb{P}(E=0)$ ? What is the limit of $\mathbb{E}[E] / m$ when $n \rightarrow \infty$ ?

  (d) Instead, let $n=d m$, for an integer $d \geqslant 2$. What is $\mathbb{P}(C=0)$ ? What is the limit of $\mathbb{E}[C] / m$ when $n \rightarrow \infty$ ?

  comment

• Paper 2, Section II, F

  Probability | Part IA, 2016

  For any positive integer $n$ and positive real number $\theta$, the Gamma distribution $\Gamma(n, \theta)$ has density $f_{\Gamma}$ defined on $(0, \infty)$ by

  $$f_{\Gamma}(x)=\frac{\theta^{n}}{(n-1) !} x^{n-1} e^{-\theta x} .$$

  For any positive integers $a$ and $b$, the Beta distribution $B(a, b)$ has density $f_{B}$ defined on $(0,1)$ by

  $$f_{B}(x)=\frac{(a+b-1) !}{(a-1) !(b-1) !} x^{a-1}(1-x)^{b-1}$$

  Let $X$ and $Y$ be independent random variables with respective distributions $\Gamma(n, \theta)$ and $\Gamma(m, \theta)$. Show that the random variables $X /(X+Y)$ and $X+Y$ are independent and give their distributions.

  comment

Vector Calculus

• Paper 3, Section I, C

  Vector Calculus | Part IA, 2016

  If $\mathbf{v}=\left(v_{1}, v_{2}, v_{3}\right)$ and $\mathbf{w}=\left(w_{1}, w_{2}, w_{3}\right)$ are vectors in $\mathbb{R}^{3}$, show that $T_{i j}=v_{i} w_{j}$ defines a rank 2 tensor. For which choices of the vectors $\mathbf{v}$ and $\mathbf{w}$ is $T_{i j}$ isotropic?

  Write down the most general isotropic tensor of rank 2 .

  Prove that $\epsilon_{i j k}$ defines an isotropic rank 3 tensor.

  comment

• Paper 3, Section I, C

  Vector Calculus | Part IA, 2016

  State the chain rule for the derivative of a composition $t \mapsto f(\mathbf{X}(t))$, where $f: \mathbb{R}^{n} \rightarrow \mathbb{R}$ and $\mathbf{X}: \mathbb{R} \rightarrow \mathbb{R}^{n}$ are smooth $.$

  Consider parametrized curves given by

  $$\mathbf{x}(t)=(x(t), y(t))=(a \cos t, a \sin t) .$$

  Calculate the tangent vector $\frac{d \mathbf{x}}{d t}$ in terms of $x(t)$ and $y(t)$. Given that $u(x, y)$ is a smooth function in the upper half-plane $\left\{(x, y) \in \mathbb{R}^{2} \mid y>0\right\}$ satisfying

  $$x \frac{\partial u}{\partial y}-y \frac{\partial u}{\partial x}=u$$

  deduce that

  $$\frac{d}{d t} u(x(t), y(t))=u(x(t), y(t))$$

  If $u(1,1)=10$, find $u(-1,1)$.

  comment

• Paper 3, Section II, C

  Vector Calculus | Part IA, 2016

  (a) Let

  $$\mathbf{F}=(z, x, y)$$

  and let $C$ be a circle of radius $R$ lying in a plane with unit normal vector $(a, b, c)$. Calculate $\nabla \times \mathbf{F}$ and use this to compute $\oint_{C} \mathbf{F} \cdot d \mathbf{x}$. Explain any orientation conventions which you use.

  (b) Let $\mathbf{F}: \mathbb{R}^{3} \rightarrow \mathbb{R}^{3}$ be a smooth vector field such that the matrix with entries $\frac{\partial F_{j}}{\partial x_{i}}$ is symmetric. Prove that $\oint_{C} \mathbf{F} \cdot d \mathbf{x}=0$ for every circle $C \subset \mathbb{R}^{3}$.

  (c) Let $\mathbf{F}=\frac{1}{r}(x, y, z)$, where $r=\sqrt{x^{2}+y^{2}+z^{2}}$ and let $C$ be the circle which is the intersection of the sphere $(x-5)^{2}+(y-3)^{2}+(z-2)^{2}=1$ with the plane $3 x-5 y-z=2$. Calculate $\oint_{C} \mathbf{F} \cdot d \mathbf{x}$.

  (d) Let $\mathbf{F}$ be the vector field defined, for $x^{2}+y^{2}>0$, by

  $$\mathbf{F}=\left(\frac{-y}{x^{2}+y^{2}}, \frac{x}{x^{2}+y^{2}}, z\right)$$

  Show that $\nabla \times \mathbf{F}=\mathbf{0}$. Let $C$ be the curve which is the intersection of the cylinder $x^{2}+y^{2}=1$ with the plane $z=x+200$. Calculate $\oint_{C} \mathbf{F} \cdot d \mathbf{x}$.

  comment

• Paper 3, Section II, C

  Vector Calculus | Part IA, 2016

  (a) For smooth scalar fields $u$ and $v$, derive the identity

  $$\nabla \cdot(u \nabla v-v \nabla u)=u \nabla^{2} v-v \nabla^{2} u$$

  and deduce that

  $$\begin{aligned} \int_{\rho \leqslant|\mathbf{x}| \leqslant r}\left(v \nabla^{2} u-u \nabla^{2} v\right) d V=\int_{|\mathbf{x}|=r}\left(v \frac{\partial u}{\partial n}-u \frac{\partial v}{\partial n}\right) d S \\ &-\int_{|\mathbf{x}|=\rho}\left(v \frac{\partial u}{\partial n}-u \frac{\partial v}{\partial n}\right) d S \end{aligned}$$

  Here $\nabla^{2}$ is the Laplacian, $\frac{\partial}{\partial n}=\mathbf{n} \cdot \nabla$ where $\mathbf{n}$ is the unit outward normal, and $d S$ is the scalar area element.

  (b) Give the expression for $(\nabla \times \mathbf{V})_{i}$ in terms of $\epsilon_{i j k}$. Hence show that

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

  (c) Assume that if $\nabla^{2} \varphi=-\rho$, where $\varphi(\mathbf{x})=O\left(|\mathbf{x}|^{-1}\right)$ and $\nabla \varphi(\mathbf{x})=O\left(|\mathbf{x}|^{-2}\right)$ as $|\mathbf{x}| \rightarrow \infty$, then

  $$\varphi(\mathbf{x})=\int_{\mathbb{R}^{3}} \frac{\rho(\mathbf{y})}{4 \pi|\mathbf{x}-\mathbf{y}|} d V .$$

  The vector fields $\mathbf{B}$ and $\mathbf{J}$ satisfy

  $$\nabla \times \mathbf{B}=\mathbf{J}$$

  Show that $\nabla \cdot \mathbf{J}=0$. In the case that $\mathbf{B}=\nabla \times \mathbf{A}$, with $\nabla \cdot \mathbf{A}=0$, show that

  $$\mathbf{A}(\mathbf{x})=\int_{\mathbb{R}^{3}} \frac{\mathbf{J}(\mathbf{y})}{4 \pi|\mathbf{x}-\mathbf{y}|} d V$$

  and hence that

  $$\mathbf{B}(\mathbf{x})=\int_{\mathbb{R}^{3}} \frac{\mathbf{J}(\mathbf{y}) \times(\mathbf{x}-\mathbf{y})}{4 \pi|\mathbf{x}-\mathbf{y}|^{3}} d V$$

  Verify that $\mathbf{A}$ given by $(*)$ does indeed satisfy $\nabla \cdot \mathbf{A}=0$. [It may be useful to make a change of variables in the right hand side of $(*)$.]

  comment

• Paper 3, Section II, C

  Vector Calculus | Part IA, 2016

  Define the Jacobian $J[\mathbf{u}]$ of a smooth mapping $\mathbf{u}: \mathbb{R}^{3} \rightarrow \mathbb{R}^{3}$. Show that if $\mathbf{V}$ is the vector field with components

  $$V_{i}=\frac{1}{3 !} \epsilon_{i j k} \epsilon_{a b c} \frac{\partial u_{a}}{\partial x_{j}} \frac{\partial u_{b}}{\partial x_{k}} u_{c}$$

  then $J[\mathbf{u}]=\nabla \cdot \mathbf{V}$. If $\mathbf{v}$ is another such mapping, state the chain rule formula for the derivative of the composition $\mathbf{w}(\mathbf{x})=\mathbf{u}(\mathbf{v}(\mathbf{x}))$, and hence give $J[\mathbf{w}]$ in terms of $J[\mathbf{u}]$ and $J[\mathbf{v}]$.

  Let $\mathbf{F}: \mathbb{R}^{3} \rightarrow \mathbb{R}^{3}$ be a smooth vector field. Let there be given, for each $t \in \mathbb{R}$, a smooth mapping $\mathbf{u}_{t}: \mathbb{R}^{3} \rightarrow \mathbb{R}^{3}$ such that $\mathbf{u}_{t}(\mathbf{x})=\mathbf{x}+t \mathbf{F}(\mathbf{x})+o(t)$ as $t \rightarrow 0$. Show that

  $$J\left[\mathbf{u}_{t}\right]=1+t Q(x)+o(t)$$

  for some $Q(x)$, and express $Q$ in terms of $\mathbf{F}$. Assuming now that $\mathbf{u}_{t+s}(\mathbf{x})=\mathbf{u}_{t}\left(\mathbf{u}_{s}(\mathbf{x})\right)$, deduce that if $\nabla \cdot \mathbf{F}=0$ then $J\left[\mathbf{u}_{t}\right]=1$ for all $t \in \mathbb{R}$. What geometric property of the mapping $\mathbf{x} \mapsto \mathbf{u}_{t}(\mathbf{x})$ does this correspond to?

  comment

• Paper 3, Section II, C

  Vector Calculus | Part IA, 2016

  What is a conservative vector field on $\mathbb{R}^{n}$ ?

  State Green's theorem in the plane $\mathbb{R}^{2}$.

  (a) Consider a smooth vector field $\mathbf{V}=(P(x, y), Q(x, y))$ defined on all of $\mathbb{R}^{2}$ which satisfies

  $$\frac{\partial Q}{\partial x}-\frac{\partial P}{\partial y}=0$$

  By considering

  $$F(x, y)=\int_{0}^{x} P\left(x^{\prime}, 0\right) d x^{\prime}+\int_{0}^{y} Q\left(x, y^{\prime}\right) d y^{\prime}$$

  or otherwise, show that $\mathbf{V}$ is conservative.

  (b) Now let $\mathbf{V}=(1+\cos (2 \pi x+2 \pi y), 2+\cos (2 \pi x+2 \pi y))$. Show that there exists a smooth function $F(x, y)$ such that $\mathbf{V}=\nabla F$.

  Calculate $\int_{C} \mathbf{V} \cdot d \mathbf{x}$, where $C$ is a smooth curve running from $(0,0)$ to $(m, n) \in \mathbb{Z}^{2}$. Deduce that there does not exist a smooth function $F(x, y)$ which satisfies $\mathbf{V}=\nabla F$ and which is, in addition, periodic with period 1 in each coordinate direction, i.e. $F(x, y)=F(x+1, y)=F(x, y+1)$.

  comment

Vectors and Matrices

• Paper 1, Section I, A

  Vectors and Matrices | Part IA, 2016

  Let $z \in \mathbb{C}$ be a solution of

  $$z^{2}+b z+1=0$$

  where $b \in \mathbb{R}$ and $|b| \leqslant 2$. For which values of $b$ do the following hold?

  (i) $\left|e^{z}\right|<1$.

  (ii) $\left|e^{i z}\right|=1$.

  (iii) $\operatorname{Im}(\cosh z)=0$.

  comment

• Paper 1, Section I, C

  Vectors and Matrices | Part IA, 2016

  Write down the general form of a $2 \times 2$ rotation matrix. Let $R$ be a real $2 \times 2$ matrix with positive determinant such that $|R \mathbf{x}|=|\mathbf{x}|$ for all $\mathbf{x} \in \mathbb{R}^{2}$. Show that $R$ is a rotation matrix.

  Let

  $$J=\left(\begin{array}{cc} 0 & -1 \\ 1 & 0 \end{array}\right)$$

  Show that any real $2 \times 2$ matrix $A$ which satisfies $A J=J A$ can be written as $A=\lambda R$, where $\lambda$ is a real number and $R$ is a rotation matrix.

  comment

• Paper 1, Section II, $8 \mathbf{C}$

  Vectors and Matrices | Part IA, 2016

  (a) Show that the equations

  $$\begin{array}{r} 1+s+t=a \\ 1-s+t=b \\ 1-2 t=c \end{array}$$

  determine $s$ and $t$ uniquely if and only if $a+b+c=3$.

  Write the following system of equations

  $$\begin{aligned} &5 x+2 y-z=1+s+t \\ &2 x+5 y-z=1-s+t \\ &-x-y+8 z=1-2 t \end{aligned}$$

  in matrix form $A \mathbf{x}=\mathbf{b}$. Use Gaussian elimination to solve the system for $x, y$, and $z$. State a relationship between the rank and the kernel of a matrix. What is the rank and what is the kernel of $A$ ?

  For which values of $x, y$, and $z$ is it possible to solve the above system for $s$ and $t$ ?

  (b) Define a unitary $n \times n$ matrix. Let $A$ be a real symmetric $n \times n$ matrix, and let $I$ be the $n \times n$ identity matrix. Show that $|(A+i I) \mathbf{x}|^{2}=|A \mathbf{x}|^{2}+|\mathbf{x}|^{2}$ for arbitrary $\mathbf{x} \in \mathbb{C}^{n}$, where $|\mathbf{x}|^{2}=\sum_{j=1}^{n}\left|x_{j}\right|^{2}$. Find a similar expression for $|(A-i I) \mathbf{x}|^{2}$. Prove that $(A-i I)(A+i I)^{-1}$ is well-defined and is a unitary matrix.

  comment

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

  Vectors and Matrices | Part IA, 2016

  The $n \times n$ real symmetric matrix $M$ has eigenvectors of unit length $\mathbf{e}_{1}, \mathbf{e}_{2}, \ldots, \mathbf{e}_{n}$, with corresponding eigenvalues $\lambda_{1}, \lambda_{2}, \ldots, \lambda_{n}$, where $\lambda_{1}>\lambda_{2}>\cdots>\lambda_{n}$. Prove that the eigenvalues are real and that $\mathbf{e}_{a} \cdot \mathbf{e}_{b}=\delta_{a b}$.

  Let $\mathbf{x}$ be any (real) unit vector. Show that

  $$\mathbf{x}^{\mathrm{T}} M \mathrm{x} \leqslant \lambda_{1}$$

  What can be said about $\mathbf{x}$ if $\mathbf{x}^{\mathrm{T}} M \mathbf{x}=\lambda_{1} ?$

  Let $S$ be the set of all (real) unit vectors of the form

  $$\mathbf{x}=\left(0, x_{2}, \ldots, x_{n}\right)$$

  Show that $\alpha_{1} \mathbf{e}_{1}+\alpha_{2} \mathbf{e}_{2} \in S$ for some $\alpha_{1}, \alpha_{2} \in \mathbb{R}$. Deduce that

  $$\underset{\mathbf{x} \in S}{\operatorname{Max}} \mathbf{x}^{\mathrm{T}} M \mathbf{x} \geqslant \lambda_{2}$$

  The $(n-1) \times(n-1)$ matrix $A$ is obtained by removing the first row and the first column of $M$. Let $\mu$ be the greatest eigenvalue of $A$. Show that

  $$\lambda_{1} \geqslant \mu \geqslant \lambda_{2}$$

  comment

• Paper 1, Section II, A

  Vectors and Matrices | Part IA, 2016

  (a) Use suffix notation to prove that

  $$\mathbf{a} \cdot(\mathbf{b} \times \mathbf{c})=\mathbf{c} \cdot(\mathbf{a} \times \mathbf{b})$$

  (b) Show that the equation of the plane through three non-colinear points with position vectors $\mathbf{a}, \mathbf{b}$ and $\mathbf{c}$ is

  $$\mathbf{r} \cdot(\mathbf{a} \times \mathbf{b}+\mathbf{b} \times \mathbf{c}+\mathbf{c} \times \mathbf{a})=\mathbf{a} \cdot(\mathbf{b} \times \mathbf{c})$$

  where $\mathbf{r}$ is the position vector of a point in this plane.

  Find a unit vector normal to the plane in the case $\mathbf{a}=(2,0,1), \mathbf{b}=(0,4,0)$ and $\mathbf{c}=(1,-1,2)$.

  (c) Let $\mathbf{r}$ be the position vector of a point in a given plane. The plane is a distance $d$ from the origin and has unit normal vector $\mathbf{n}$, where $\mathbf{n} \cdot \mathbf{r} \geqslant 0$. Write down the equation of this plane.

  This plane intersects the sphere with centre at $\mathbf{p}$ and radius $q$ in a circle with centre at $\mathbf{m}$ and radius $\rho$. Show that

  $$\mathbf{m}-\mathbf{p}=\gamma \mathbf{n}$$

  Find $\gamma$ in terms of $q$ and $\rho$. Hence find $\rho$ in terms of $\mathbf{n}, d, \mathbf{p}$ and $q$.

  comment

• Paper 1, Section II, B

  Vectors and Matrices | Part IA, 2016

  What does it mean to say that a matrix can be diagonalised? Given that the $n \times n$ real matrix $M$ has $n$ eigenvectors satisfying $\mathbf{e}_{a} \cdot \mathbf{e}_{b}=\delta_{a b}$, explain how to obtain the diagonal form $\Lambda$ of $M$. Prove that $\Lambda$ is indeed diagonal. Obtain, with proof, an expression for the trace of $M$ in terms of its eigenvalues.

  The elements of $M$ are given by

  $$M_{i j}= \begin{cases}0 & \text { for } i=j \\ 1 & \text { for } i \neq j\end{cases}$$

  Determine the elements of $M^{2}$ and hence show that, if $\lambda$ is an eigenvalue of $M$, then

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

  Assuming that $M$ can be diagonalised, give its diagonal form.

  comment