Part IA, 2005

Algebra and Geometry

• 1.I.1C

  Algebra and Geometry | Part IA, 2005

  Convert the following expressions from suffix notation (assuming the summation convention in three dimensions) into standard notation using vectors and/or matrices, where possible, identifying the one expression that is incorrectly formed:

  (i) $\delta_{i j}$,

  (ii) $\delta_{i i} \delta_{i j}$,

  (iii) $\delta_{l l} a_{i} b_{j} C_{i j} d_{k}-C_{i k} d_{i}$,

  (iv) $\epsilon_{i j k} a_{k} b_{j}$,

  (v) $\epsilon_{i j k} a_{j} a_{k}$.

  Write the vector triple product $\mathbf{a} \times(\mathbf{b} \times \mathbf{c})$ in suffix notation and derive an equivalent expression that utilises scalar products. Express the result both in suffix notation and in standard vector notation. Hence or otherwise determine $\mathbf{a} \times(\mathbf{b} \times \mathbf{c})$ when $\mathbf{a}$ and $\mathbf{b}$ are orthogonal and $\mathbf{c}=\mathbf{a}+\mathbf{b}+\mathbf{a} \times \mathbf{b}$.

  comment

• 1.I.2B

  Algebra and Geometry | Part IA, 2005

  Let $\mathbf{n} \in \mathbb{R}^{3}$ be a unit vector. Consider the operation

  $$\mathbf{x} \mapsto \mathbf{n} \times \mathbf{x}$$

  Write this in matrix form, i.e., find a $3 \times 3$ matrix $\mathbf{A}$ such that $\mathbf{A} \mathbf{x}=\mathbf{n} \times \mathbf{x}$ for all $\mathbf{x}$, and compute the eigenvalues of $\mathbf{A}$. In the case when $\mathbf{n}=(0,0,1)$, compute $\mathbf{A}^{2}$ and its eigenvalues and eigenvectors.

  comment

• 1.II.5C

  Algebra and Geometry | Part IA, 2005

  Give the real and imaginary parts of each of the following functions of $z=x+i y$, with $x, y$ real, (i) $e^{z}$, (ii) $\cos z$, (iii) $\log z$, (iv) $\frac{1}{z}+\frac{1}{\bar{z}}$, (v) $z^{3}+3 z^{2} \bar{z}+3 z \bar{z}^{2}+\bar{z}^{3}-\bar{z}$,

  where $\bar{z}$ is the complex conjugate of $z$.

  An ant lives in the complex region $R$ given by $|z-1| \leq 1$. Food is found at $z$ such that

  $$(\log z)^{2}=-\frac{\pi^{2}}{16} .$$

  Drink is found at $z$ such that

  $$\frac{z+\frac{1}{2} \bar{z}}{\left(z-\frac{1}{2} \bar{z}\right)^{2}}=3, \quad z \neq 0$$

  Identify the places within $R$ where the ant will find the food or drink.

  comment

• 1.II.6B

  Algebra and Geometry | Part IA, 2005

  Let $\mathbf{A}$ be a real $3 \times 3$ matrix. Define the rank of $\mathbf{A}$. Describe the space of solutions of the equation

  $$\tag{†} \mathbf{A x}=\mathbf{b},$$

  organizing your discussion with reference to the rank of $\mathbf{A}$.

  Write down the equation of the tangent plane at $(0,1,1)$ on the sphere $x_{1}^{2}+x_{2}^{2}+x_{3}^{2}=2$ and the equation of a general line in $\mathbb{R}^{3}$ passing through the origin $(0,0,0)$.

  Express the problem of finding points on the intersection of the tangent plane and the line in the form $(†)$. Find, and give geometrical interpretations of, the solutions.

  comment

• 1.II.7A

  Algebra and Geometry | Part IA, 2005

  Consider two vectors $\mathbf{a}$ and $\mathbf{b}$ in $\mathbb{R}^{n}$. Show that a may be written as the sum of two vectors: one parallel (or anti-parallel) to $\mathbf{b}$ and the other perpendicular to $\mathbf{b}$. By setting the former equal to $\cos \theta|\mathbf{a}| \hat{\mathbf{b}}$, where $\hat{\mathbf{b}}$ is a unit vector along $\mathbf{b}$, show that

  $$\cos \theta=\frac{\mathbf{a} \cdot \mathbf{b}}{|\mathbf{a}||\mathbf{b}|}$$

  Explain why this is a sensible definition of the angle $\theta$ between $\mathbf{a}$ and $\mathbf{b}$.

  Consider the $2^{n}$ vertices of a cube of side 2 in $\mathbb{R}^{n}$, centered on the origin. Each vertex is joined by a straight line through the origin to another vertex: the lines are the $2^{n-1}$ diagonals of the cube. Show that no two diagonals can be perpendicular if $n$ is odd.

  For $n=4$, what is the greatest number of mutually perpendicular diagonals? List all the possible angles between the diagonals.

  comment

• 1.II.8A

  Algebra and Geometry | Part IA, 2005

  Given a non-zero vector $v_{i}$, any $3 \times 3$ symmetric matrix $T_{i j}$ can be expressed as

  $$T_{i j}=A \delta_{i j}+B v_{i} v_{j}+\left(C_{i} v_{j}+C_{j} v_{i}\right)+D_{i j}$$

  for some numbers $A$ and $B$, some vector $C_{i}$ and a symmetric matrix $D_{i j}$, where

  $$C_{i} v_{i}=0, \quad D_{i i}=0, \quad D_{i j} v_{j}=0,$$

  and the summation convention is implicit.

  Show that the above statement is true by finding $A, B, C_{i}$ and $D_{i j}$ explicitly in terms of $T_{i j}$ and $v_{j}$, or otherwise. Explain why $A, B, C_{i}$ and $D_{i j}$ together provide a space of the correct dimension to parameterise an arbitrary symmetric $3 \times 3$ matrix $T_{i j}$.

  comment

• 3.I.1D

  Algebra and Geometry | Part IA, 2005

  Let $A$ be a real $3 \times 3$ symmetric matrix with eigenvalues $\lambda_{1}>\lambda_{2}>\lambda_{3}>0$. Consider the surface $S$ in $\mathbb{R}^{3}$ given by

  $$x^{T} A x=1$$

  Find the minimum distance between the origin and $S$. How many points on $S$ realize this minimum distance? Justify your answer.

  comment

• 3.I.2D

  Algebra and Geometry | Part IA, 2005

  Define what it means for a group to be cyclic. If $p$ is a prime number, show that a finite group $G$ of order $p$ must be cyclic. Find all homomorphisms $\varphi: C_{11} \rightarrow C_{14}$, where $C_{n}$ denotes the cyclic group of order $n$. [You may use Lagrange's theorem.]

  comment

• 3.II.5D

  Algebra and Geometry | Part IA, 2005

  Define the notion of an action of a group $G$ on a set $X$. Assuming that $G$ is finite, state and prove the Orbit-Stabilizer Theorem.

  Let $G$ be a finite group and $X$ the set of its subgroups. Show that $g(K)=g K g^{-1}$ $(g \in G, K \in X)$ defines an action of $G$ on $X$. If $H$ is a subgroup of $G$, show that the orbit of $H$ has at most $|G| /|H|$ elements.

  Suppose $H$ is a subgroup of $G$ and $H \neq G$. Show that there is an element of $G$ which does not belong to any subgroup of the form $g H g^{-1}$ for $g \in G$.

  comment

• 3.II.6D

  Algebra and Geometry | Part IA, 2005

  Let $\mathcal{M}$ be the group of Möbius transformations of $\mathbb{C} \cup\{\infty\}$ and let $S L(2, \mathbb{C})$ be the group of all $2 \times 2$ complex matrices with determinant 1 .

  Show that the map $\theta: S L(2, \mathbb{C}) \rightarrow \mathcal{M}$ given by

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

  is a surjective homomorphism. Find its kernel.

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

  Show that if $T \in \mathcal{M}$, then $T$ is the identity, or $T$ has one, or two, fixed points. Also show that if $T \in \mathcal{M}$ has only one fixed point $z_{0}$ then $T^{n} z \rightarrow z_{0}$ as $n \rightarrow \infty$ for any $z \in \mathbb{C} \cup\{\infty\} .$

  comment

• 3.II.7D

  Algebra and Geometry | Part IA, 2005

  Let $G$ be a group and let $Z(G)=\{h \in G: g h=h g$ for all $g \in G\}$. Show that $Z(G)$ is a normal subgroup of $G .$

  Let $H$ be the set of all $3 \times 3$ real matrices of the form

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

  with $x, y, z \in \mathbb{R}$. Show that $H$ is a subgroup of the group of invertible real matrices under multiplication.

  Find $Z(H)$ and show that $H / Z(H)$ is isomorphic to $\mathbb{R}^{2}$ with vector addition.

  comment

• 3.II.8D

  Algebra and Geometry | Part IA, 2005

  Let $A$ be a $3 \times 3$ real matrix such that $\operatorname{det}(A)=-1, A \neq-I$, and $A^{T} A=I$, where $A^{T}$ is the transpose of $A$ and $I$ is the identity.

  Show that the set $E$ of vectors $x$ for which $A x=-x$ forms a 1-dimensional subspace.

  Consider the plane $\Pi$ through the origin which is orthogonal to $E$. Show that $A$ maps $\Pi$ to itself and induces a rotation of $\Pi$ by angle $\theta$, where $\cos \theta=\frac{1}{2}(\operatorname{trace}(A)+1)$. Show that $A$ is a reflection in $\Pi$ if and only if $A$ has trace 1 . [You may use the fact that $\operatorname{trace}\left(B A B^{-1}\right)=\operatorname{trace}(A)$ for any invertible matrix B.]

  Prove that $\operatorname{det}(A-I)=4(\cos \theta-1)$.

  comment

Analysis

• 1.I.3F

  Analysis | Part IA, 2005

  Define the supremum or least upper bound of a non-empty set of real numbers.

  Let $A$ denote a non-empty set of real numbers which has a supremum but no maximum. Show that for every $\epsilon>0$ there are infinitely many elements of $A$ contained in the open interval

  $$(\sup A-\epsilon, \sup A) .$$

  Give an example of a non-empty set of real numbers which has a supremum and maximum and for which the above conclusion does not hold.

  comment

• 1.I.4D

  Analysis | Part IA, 2005

  Let $\sum_{n=0}^{\infty} a_{n} z^{n}$ be a power series in the complex plane with radius of convergence $R$. Show that $\left|a_{n} z^{n}\right|$ is unbounded in $n$ for any $z$ with $|z|>R$. State clearly any results on absolute convergence that are used.

  For every $R \in[0, \infty]$, show that there exists a power series $\sum_{n=0}^{\infty} a_{n} z^{n}$ with radius of convergence $R$.

  comment

• 1.II.10D

  Analysis | Part IA, 2005

  Explain what it means for a bounded function $f:[a, b] \rightarrow \mathbb{R}$ to be Riemann integrable.

  Let $f:[0, \infty) \rightarrow \mathbb{R}$ be a strictly decreasing continuous function. Show that for each $x \in(0, \infty)$, there exists a unique point $g(x) \in(0, x)$ such that

  $$\frac{1}{x} \int_{0}^{x} f(t) d t=f(g(x)) .$$

  Find $g(x)$ if $f(x)=e^{-x}$.

  Suppose now that $f$ is differentiable and $f^{\prime}(x)<0$ for all $x \in(0, \infty)$. Prove that $g$ is differentiable at all $x \in(0, \infty)$ and $g^{\prime}(x)>0$ for all $x \in(0, \infty)$, stating clearly any results on the inverse of $f$ you use.

  comment

• 1.II.11E

  Analysis | Part IA, 2005

  Prove that if $f$ is a continuous function on the interval $[a, b]$ with $f(a)<0<f(b)$ then $f(c)=0$ for some $c \in(a, b)$.

  Let $g$ be a continuous function on $[0,1]$ satisfying $g(0)=g(1)$. By considering the function $f(x)=g\left(x+\frac{1}{2}\right)-g(x)$ on $\left[0, \frac{1}{2}\right]$, show that $g\left(c+\frac{1}{2}\right)=g(c)$ for some $c \in\left[0, \frac{1}{2}\right]$. Show, more generally, that for any positive integer $n$ there exists a point $c_{n} \in\left[0, \frac{n-1}{n}\right]$ for which $g\left(c_{n}+\frac{1}{n}\right)=g\left(c_{n}\right)$.

  comment

• 1.II.12E

  Analysis | Part IA, 2005

  State and prove Rolle's Theorem.

  Prove that if the real polynomial $p$ of degree $n$ has all its roots real (though not necessarily distinct), then so does its derivative $p^{\prime}$. Give an example of a cubic polynomial $p$ for which the converse fails.

  comment

• 1.II.9F

  Analysis | Part IA, 2005

  Examine each of the following series and determine whether or not they converge.

  Give reasons in each case.

  $(i)$

  $(i i)$

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

  (iii)

  $$\sum_{n=1}^{\infty} \frac{n^{3}+(-1)^{n} 8 n^{2}+1}{n^{4}+(-1)^{n+1} n^{2}}$$

  $(i v)$

  $$\sum_{n=1}^{\infty} \frac{n^{3}}{e^{e^{n}}}$$

  comment

Differential Equations

• $2 . \mathrm{II} . 6 \mathrm{~B} \quad$

  Differential Equations | Part IA, 2005

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

  $$-W^{\prime \prime}+2 x W^{\prime}=E W,$$

  for $E$ a real constant.

  Impose the condition $W(0)=0$ and determine those values of $E$ for which your power series gives polynomial solutions (i.e., $a_{n}=0$ for $n$ sufficiently large). Give the values of $E$ for which the corresponding polynomials have degree less than 6 , and compute these polynomials.

  Hence, or otherwise, find a polynomial solution of

  $$-W^{\prime \prime}+2 x W^{\prime}=x-\frac{4}{3} x^{3}+\frac{4}{15} x^{5},$$

  satisfying $W(0)=0$.

  comment

• 2.I.1B

  Differential Equations | Part IA, 2005

  Solve the equation

  $$\frac{d y}{d x}+3 x^{2} y=x^{2}$$

  with $y(0)=a$, by use of an integrating factor or otherwise. Find $\lim _{x \rightarrow+\infty} y(x)$.

  comment

• 2.I.2B

  Differential Equations | Part IA, 2005

  Obtain the general solution of

  $$x^{2} \frac{d^{2} y}{d x^{2}}+x \frac{d y}{d x}+y=0$$

  by using the indicial equation.

  Introduce $z=\log x$ as a new independent variable and find an equivalent second order differential equation with constant coefficients. Determine the general solution of this new equation, and show that it is equivalent to the general solution of $(*)$ found previously.

  comment

• 2.II.5B

  Differential Equations | Part IA, 2005

  Find two linearly independent solutions of the difference equation

  $$X_{n+2}-2 \cos \theta X_{n+1}+X_{n}=0$$

  for all values of $\theta \in(0, \pi)$. What happens when $\theta=0$ ? Find two linearly independent solutions in this case.

  Find $X_{n}(\theta)$ which satisfy the initial conditions

  $$X_{1}=1, \quad X_{2}=2,$$

  for $\theta=0$ and for $\theta \in(0, \pi)$. For every $n$, show that $X_{n}(\theta) \rightarrow X_{n}(0)$ as $\theta \rightarrow 0$.

  comment

• 2.II.7B

  Differential Equations | Part IA, 2005

  The Cartesian coordinates $(x, y)$ of a point moving in $\mathbb{R}^{2}$ are governed by the system

  $$\begin{aligned} &\frac{d x}{d t}=-y+x\left(1-x^{2}-y^{2}\right), \\ &\frac{d y}{d t}=x+y\left(1-x^{2}-y^{2}\right) . \end{aligned}$$

  Transform this system of equations to polar coordinates $(r, \theta)$ and hence find all periodic solutions (i.e., closed trajectories) which satisfy $r=$ constant.

  Discuss the large time behaviour of an arbitrary solution starting at initial point $\left(x_{0}, y_{0}\right)=\left(r_{0} \cos \theta_{0}, r_{0} \sin \theta_{0}\right)$. Summarize the motion using a phase plane diagram, and comment on the nature of any critical points.

  comment

• 2.II.8B

  Differential Equations | Part IA, 2005

  Define the Wronskian $W\left[u_{1}, u_{2}\right]$ for two solutions $u_{1}, u_{2}$ of the equation

  $$\frac{d^{2} u}{d x^{2}}+p(x) \frac{d u}{d x}+q(x) u=0$$

  and obtain a differential equation which exhibits its dependence on $x$. Explain the relevance of the Wronskian to the linear independence of $u_{1}$ and $u_{2}$.

  Consider the equation

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

  and determine the dependence on $x$ of the Wronskian $W\left[y_{1}, y_{2}\right]$ of two solutions $y_{1}$ and $y_{2}$. Verify that $y_{1}(x)=x^{2}$ is a solution of $(*)$ and use the Wronskian to obtain a second linearly independent solution.

  comment

Dynamics

• 4.I.3C

  Dynamics | Part IA, 2005

  Planetary Explorers Ltd. want to put a communications satellite of mass $m$ into geostationary orbit around the spherical planet Zog (i.e. with the satellite always above the same point on the surface of Zog). The mass of Zog is $M$, the length of its day is $T$ and $G$ is the gravitational constant.

  Write down the equations of motion for a general orbit of the satellite and determine the radius and speed of the geostationary orbit.

  Describe briefly how the orbit is modified if the satellite is released at the correct radius and on the correct trajectory for a geostationary orbit, but with a little too much speed. Comment on how the satellite's speed varies around such an orbit.

  comment

• 4.I.4C

  Dynamics | Part IA, 2005

  A car of mass $M$ travelling at speed $U$ on a smooth, horizontal road attempts an emergency stop. The car skids in a straight line with none of its wheels able to rotate.

  Calculate the stopping distance and time on a dry road where the dry friction coefficient between the tyres and the road is $\mu$.

  At high speed on a wet road the grip of each of the four tyres changes from dry friction to a lubricated drag equal to $\frac{1}{4} \lambda u$ for each tyre, where $\lambda$ is the drag coefficient and $u$ the instantaneous speed of the car. However, the tyres regain their dry-weather grip when the speed falls below $\frac{1}{4} U$. Calculate the stopping distance and time under these conditions.

  comment

• 4.II.10C

  Dynamics | Part IA, 2005

  A keen cyclist wishes to analyse her performance on training rollers. She decides that the key components are her bicycle's rear wheel and the roller on which the wheel sits. The wheel, of radius $R$, has its mass $M$ entirely at its outer edge. The roller, which is driven by the wheel without any slippage, is a solid cylinder of radius $S$ and mass $M / 2$. The angular velocities of the wheel and roller are $\omega$ and $\sigma$, respectively.

  Determine $I$ and $J$, the moments of inertia of the wheel and roller, respectively. Find the ratio of the angular velocities of the wheel and roller. Show that the combined total kinetic energy of the wheel and roller is $\frac{1}{2} K \omega^{2}$, where

  $$K=\frac{5}{4} M R^{2}$$

  is the effective combined moment of inertia of the wheel and roller.

  Why should $K$ be used instead of just $I$ or $J$ in the equation connecting torque with angular acceleration? The cyclist believes the torque she can produce at the back wheel is $T=Q(1-\omega / \Omega)$ where $Q$ and $\Omega$ are dimensional constants. Determine the angular velocity of the wheel, starting from rest, as a function of time.

  In an attempt to make the ride more realistic, the cyclist adds a fan (of negligible mass) to the roller. The fan imposes a frictional torque $-\gamma \sigma^{2}$ on the roller, where $\gamma$ is a dimensional constant. Determine the new maximum speed for the wheel.

  comment

• 4.II.11C

  Dynamics | Part IA, 2005

  A puck of mass $m$ located at $\mathbf{r}=(x, y)$ slides without friction under the influence of gravity on a surface of height $z=h(x, y)$. Show that the equations of motion can be approximated by

  $$\ddot{\mathbf{r}}=-g \nabla h,$$

  where $g$ is the gravitational acceleration and the small slope approximation $\sin \phi \approx \tan \phi$ is used.

  Determine the motion of the puck when $h(x, y)=\alpha x^{2}$.

  Sketch the surface

  $$h(x, y)=h(r)=\frac{1}{r^{2}}-\frac{1}{r}$$

  as a function of $r$, where $r^{2}=x^{2}+y^{2}$. Write down the equations of motion of the puck on this surface in polar coordinates $\mathbf{r}=(r, \theta)$ under the assumption that the small slope approximation can be used. Show that $L$, the angular momentum per unit mass about the origin, is conserved. Show also that the initial kinetic energy per unit mass of the puck is $E_{0}=\frac{1}{2} L^{2} / r_{0}^{2}$ if the puck is released at radius $r_{0}$ with negligible radial velocity. Determine and sketch $\dot{r}^{2}$ as a function of $r$ for this release condition. What condition relating $L, r_{0}$ and $g$ must be satisfied for the orbit to be bounded?

  comment

• 4.II.12C

  Dynamics | Part IA, 2005

  In an experiment a ball of mass $m$ is released from a height $h_{0}$ above a flat, horizontal plate. Assuming the gravitational acceleration $g$ is constant and the ball falls through a vacuum, find the speed $u_{0}$ of the ball on impact.

  Determine the speed $u_{1}$ at which the ball rebounds if the coefficient of restitution for the collision is $\gamma$. What fraction of the impact energy is dissipated during the collision? Determine also the maximum height $h_{n}$ the ball reaches after the $n^{\text {th }}$bounce, and the time $T_{n}$ between the $n^{t h}$ and $(n+1)^{t h}$ bounce. What is the total distance travelled by the ball before it comes to rest if $\gamma<1$ ?

  If the experiment is repeated in an atmosphere then the ball experiences a drag force $D=-\alpha|u| u$, where $\alpha$ is a dimensional constant and $u$ the instantaneous velocity of the ball. Write down and solve the modified equation for $u(t)$ before the ball first hits the plate.

  comment

• 4.II.9C

  Dynamics | Part IA, 2005

  A particle of mass $m$ and charge $q$ moving in a vacuum through a magnetic field $\mathbf{B}$ and subject to no other forces obeys

  $$m \ddot{\mathbf{r}}=q \dot{\mathbf{r}} \times \mathbf{B}$$

  where $\mathbf{r}(t)$ is the location of the particle.

  For $\mathbf{B}=(0,0, B)$ with constant $B$, and using cylindrical polar coordinates $\mathbf{r}=$ $(r, \theta, z)$, or otherwise, determine the motion of the particle in the $z=0$ plane if its initial speed is $u_{0}$ with $\dot{z}=0$. [Hint: Choose the origin so that $\dot{r}=0$ and $\ddot{r}=0$ at $t=0$.]

  Due to a leak, a small amount of gas enters the system, causing the particle to experience a drag force $\mathbf{D}=-\mu \dot{\mathbf{r}}$, where $\mu \ll q B$. Write down the new governing equations and show that the speed of the particle decays exponentially. Sketch the path followed by the particle. [Hint: Consider the equations for the velocity in Cartesian coordinates; you need not apply any initial conditions.]

  comment

Numbers and Sets

• 4.I.1E

  Numbers and Sets | Part IA, 2005

  Find the unique positive integer $a$ with $a \leq 19$, for which

  $$17 ! \cdot 3^{16} \equiv a(\bmod 19) \text {. }$$

  Results used should be stated but need not be proved.

  Solve the system of simultaneous congruences

  $$\begin{aligned} &x \equiv 1(\bmod 2), \\ &x \equiv 1(\bmod 3) \\ &x \equiv 3(\bmod 4) \\ &x \equiv 4(\bmod 5) \end{aligned}$$

  Explain very briefly your reasoning.

  comment

• 4.I.2E

  Numbers and Sets | Part IA, 2005

  Give a combinatorial definition of the binomial coefficient $\left(\begin{array}{l}n \\ m\end{array}\right)$ for any non-negative integers $n, m$.

  Prove that $\left(\begin{array}{c}n \\ m\end{array}\right)=\left(\begin{array}{c}n \\ n-m\end{array}\right)$ for $0 \leq m \leq n$.

  Prove the identities

  $$\left(\begin{array}{l} n \\ k \end{array}\right)\left(\begin{array}{l} k \\ l \end{array}\right)=\left(\begin{array}{l} n \\ l \end{array}\right)\left(\begin{array}{l} n-l \\ k-l \end{array}\right)$$

  and

  $$\sum_{i=0}^{k}\left(\begin{array}{c} m \\ i \end{array}\right)\left(\begin{array}{c} n \\ k-i \end{array}\right)=\left(\begin{array}{c} n+m \\ k \end{array}\right)$$

  comment

• 4.II $. 7 \mathrm{E} \quad$

  Numbers and Sets | Part IA, 2005

  State and prove the Principle of Inclusion and Exclusion.

  Use the Principle to show that the Euler totient function $\phi$ satisfies

  $$\phi\left(p_{1}^{c_{1}} \cdots p_{r}^{c_{r}}\right)=p_{1}^{c_{1}-1}\left(p_{1}-1\right) \cdots p_{r}^{c_{r}-1}\left(p_{r}-1\right) .$$

  Deduce that if $a$ and $b$ are coprime integers, then $\phi(a b)=\phi(a) \phi(b)$, and more generally, that if $d$ is any divisor of $n$ then $\phi(d)$ divides $\phi(n)$.

  Show that if $\phi(n)$ divides $n$ then $n=2^{c} 3^{d}$ for some non-negative integers $c, d$.

  comment

• 4.II.5E

  Numbers and Sets | Part IA, 2005

  What does it mean for a set to be countable? Show that $\mathbb{Q} \times \mathbb{Q}$ is countable, and $\mathbb{R}$ is not countable.

  Let $D$ be any set of non-trivial discs in a plane, any two discs being disjoint. Show that $D$ is countable.

  Give an example of a set $C$ of non-trivial circles in a plane, any two circles being disjoint, which is not countable.

  comment

• 4.II.6E

  Numbers and Sets | Part IA, 2005

  Let $R$ be a relation on the set $S$. What does it mean for $R$ to be an equivalence relation on $S$ ? Show that if $R$ is an equivalence relation on $S$, the set of equivalence classes forms a partition of $S$.

  Let $G$ be a group, and let $H$ be a subgroup of $G$. Define a relation $R$ on $G$ by $a R b$ if $a^{-1} b \in H$. Show that $R$ is an equivalence relation on $G$, and that the equivalence classes are precisely the left cosets $g H$ of $H$ in $G$. Find a bijection from $H$ to any other coset $g H$. Deduce that if $G$ is finite then the order of $H$ divides the order of $G$.

  Let $g$ be an element of the finite group $G$. The order $o(g)$ of $g$ is the least positive integer $n$ for which $g^{n}=1$, the identity of $G$. If $o(g)=n$, then $G$ has a subgroup of order $n$; deduce that $g^{|G|}=1$ for all $g \in G$.

  Let $m$ be a natural number. Show that the set of integers in $\{1,2, \ldots, m\}$ which are prime to $m$ is a group under multiplication modulo $m$. [You may use any properties of multiplication and divisibility of integers without proof, provided you state them clearly.]

  Deduce that if $a$ is any integer prime to $m$ then $a^{\phi(m)} \equiv 1(\bmod \mathrm{m})$, where $\phi$ is the Euler totient function.

  comment

• 4.II.8E

  Numbers and Sets | Part IA, 2005

  The Fibonacci numbers are defined by the equations $F_{0}=0, F_{1}=1$ and $F_{n+1}=F_{n}+F_{n-1}$ for any positive integer $n$. Show that the highest common factor $\left(F_{n+1}, F_{n}\right)$ is $1 .$

  Let $n$ be a natural number. Prove by induction on $k$ that for all positive integers $k$,

  $$F_{n+k}=F_{k} F_{n+1}+F_{k-1} F_{n} .$$

  Deduce that $F_{n}$ divides $F_{n l}$ for all positive integers $l$. Deduce also that if $m \geq n$ then

  $$\left(F_{m}, F_{n}\right)=\left(F_{m-n}, F_{n}\right) .$$

  comment

Probability

• 2.I.3F

  Probability | Part IA, 2005

  Suppose $c \geqslant 1$ and $X_{c}$ is a positive real-valued random variable with probability density

  $$f_{c}(t)=A_{c} t^{c-1} e^{-t^{c}},$$

  for $t>0$, where $A_{c}$ is a constant.

  Find the constant $A_{c}$ and show that, if $c>1$ and $s, t>0$,

  $$\mathbb{P}\left[X_{c} \geqslant s+t \mid X_{c} \geqslant t\right]<\mathbb{P}\left[X_{c} \geqslant s\right]$$

  [You may assume the inequality $(1+x)^{c}>1+x^{c}$ for all $x>0, c>1$.]

  comment

• 2.I.4F

  Probability | Part IA, 2005

  Describe the Poisson distribution characterised by parameter $\lambda>0$. Calculate the mean and variance of this distribution in terms of $\lambda$.

  Show that the sum of $n$ independent random variables, each having the Poisson distribution with $\lambda=1$, has a Poisson distribution with $\lambda=n$.

  Use the central limit theorem to prove that

  $$e^{-n}\left(1+\frac{n}{1 !}+\frac{n^{2}}{2 !}+\ldots+\frac{n^{n}}{n !}\right) \rightarrow 1 / 2 \quad \text { as } \quad n \rightarrow \infty$$

  comment

• 2.II $. 9 \mathrm{~F} \quad$

  Probability | Part IA, 2005

  Given a real-valued random variable $X$, we define $\mathbb{E}\left[e^{i X}\right]$ by

  $$\mathbb{E}\left[e^{i X}\right] \equiv \mathbb{E}[\cos X]+i \mathbb{E}[\sin X]$$

  Consider a second real-valued random variable $Y$, independent of $X$. Show that

  $$\mathbb{E}\left[e^{i(X+Y)}\right]=\mathbb{E}\left[e^{i X}\right] \mathbb{E}\left[e^{i Y}\right]$$

  You gamble in a fair casino that offers you unlimited credit despite your initial wealth of 0 . At every game your wealth increases or decreases by $£ 1$ with equal probability $1 / 2$. Let $W_{n}$ denote your wealth after the $n^{t h}$ game. For a fixed real number $u$, compute $\phi(u)$ defined by

  $$\phi(u)=\mathbb{E}\left[e^{i u W_{n}}\right]$$

  Verify that the result is real-valued.

  Show that for $n$ even,

  $$\mathbb{P}\left[W_{n}=0\right]=\gamma \int_{0}^{\pi / 2}[\cos u]^{n} d u$$

  for some constant $\gamma$, which you should determine. What is $\mathbb{P}\left[W_{n}=0\right]$ for $n$ odd?

  comment

• 2.II.10F

  Probability | Part IA, 2005

  Alice and Bill fight a paint-ball duel. Nobody has been hit so far and they are both left with one shot. Being exhausted, they need to take a breath before firing their last shot. This takes $A$ seconds for Alice and $B$ seconds for Bill. Assume these times are exponential random variables with means $1 / \alpha$ and $1 / \beta$, respectively.

  Find the distribution of the (random) time that passes by before the next shot is fired. What is its standard deviation? What is the probability that Alice fires the next shot?

  Assume Alice has probability $1 / 2$ of hitting whenever she fires whereas Bill never misses his target. If the next shot is a hit, what is the probability that it was fired by Alice?

  comment

• 2.II.11F

  Probability | Part IA, 2005

  Let $(S, T)$ be uniformly distributed on $[-1,1]^{2}$ and define $R=\sqrt{S^{2}+T^{2}}$. Show that, conditionally on

  $$R \leqslant 1,$$

  the vector $(S, T)$ is uniformly distributed on the unit disc. Let $(R, \Theta)$ denote the point $(S, T)$ in polar coordinates and find its probability density function $f(r, \theta)$ for $r \in[0,1], \theta \in[0,2 \pi)$. Deduce that $R$ and $\Theta$ are independent.

  Introduce the new random variables

  $$X=\frac{S}{R} \sqrt{-2 \log \left(R^{2}\right)}, \quad Y=\frac{T}{R} \sqrt{-2 \log \left(R^{2}\right)}$$

  noting that under the above conditioning, $(S, T)$ are uniformly distributed on the unit disc. The pair $(X, Y)$ may be viewed as a (random) point in $\mathbb{R}^{2}$ with polar coordinates $(Q, \Psi)$. Express $Q$ as a function of $R$ and deduce its density. Find the joint density of $(Q, \Psi)$. Hence deduce that $X$ and $Y$ are independent normal random variables with zero mean and unit variance.

  comment

• 2.II.12F

  Probability | Part IA, 2005

  Let $a_{1}, a_{2}, \ldots, a_{n}$ be a ranking of the yearly rainfalls in Cambridge over the next $n$ years: assume $a_{1}, a_{2}, \ldots, a_{n}$ is a random permutation of $1,2, \ldots, n$. Year $k$ is called a record year if $a_{i}>a_{k}$ for all $i<k$ (thus the first year is always a record year). Let $Y_{i}=1$ if year $i$ is a record year and 0 otherwise.

  Find the distribution of $Y_{i}$ and show that $Y_{1}, Y_{2}, \ldots, Y_{n}$ are independent and calculate the mean and variance of the number of record years in the next $n$ years.

  Find the probability that the second record year occurs at year $i$. What is the expected number of years until the second record year occurs?

  comment

Vector Calculus

• 3.I.3A

  Vector Calculus | Part IA, 2005

  Let $\mathbf{A}(t, \mathbf{x})$ and $\mathbf{B}(t, \mathbf{x})$ be time-dependent, continuously differentiable vector fields on $\mathbb{R}^{3}$ satisfying

  $$\frac{\partial \mathbf{A}}{\partial t}=\nabla \times \mathbf{B} \quad \text { and } \quad \frac{\partial \mathbf{B}}{\partial t}=-\nabla \times \mathbf{A}$$

  Show that for any bounded region $V$,

  $$\frac{d}{d t}\left[\frac{1}{2} \int_{V}\left(\mathbf{A}^{2}+\mathbf{B}^{2}\right) d V\right]=-\int_{S}(\mathbf{A} \times \mathbf{B}) \cdot d \mathbf{S}$$

  where $S$ is the boundary of $V$.

  comment

• 3.I.4A

  Vector Calculus | Part IA, 2005

  Given a curve $\gamma(s)$ in $\mathbb{R}^{3}$, parameterised such that $\left\|\gamma^{\prime}(s)\right\|=1$ and with $\gamma^{\prime \prime}(s) \neq 0$, define the tangent $\mathbf{t}(s)$, the principal normal $\mathbf{p}(s)$, the curvature $\kappa(s)$ and the binormal $\mathbf{b}(s)$.

  The torsion $\tau(s)$ is defined by

  $$\tau=-\mathbf{b}^{\prime} \cdot \mathbf{p}$$

  Sketch a circular helix showing $\mathbf{t}, \mathbf{p}, \mathbf{b}$ and $\mathbf{b}^{\prime}$ at a chosen point. What is the sign of the torsion for your helix? Sketch a second helix with torsion of the opposite sign.

  comment

• 3.II.11A

  Vector Calculus | Part IA, 2005

  Explain, with justification, the significance of the eigenvalues of the Hessian in classifying the critical points of a function $f: \mathbb{R}^{n} \rightarrow \mathbb{R}$. In what circumstances are the eigenvalues inconclusive in establishing the character of a critical point?

  Consider the function on $\mathbb{R}^{2}$,

  $$f(x, y)=x y e^{-\alpha\left(x^{2}+y^{2}\right)}$$

  Find and classify all of its critical points, for all real $\alpha$. How do the locations of the critical points change as $\alpha \rightarrow 0$ ?

  comment

• 3.II.12A

  Vector Calculus | Part IA, 2005

  Express the integral

  $$I=\int_{0}^{\infty} d x \int_{0}^{1} d y \int_{0}^{x} d z x e^{-A x / y-B x y-C y z}$$

  in terms of the new variables $\alpha=x / y, \beta=x y$, and $\gamma=y z$. Hence show that

  $$I=\frac{1}{2 A(A+B)(A+B+C)}$$

  You may assume $A, B$ and $C$ are positive. [Hint: Remember to calculate the limits of the integral.]

  comment

• 3.II.9A

  Vector Calculus | Part IA, 2005

  Let $V$ be a bounded region of $\mathbb{R}^{3}$ and $S$ be its boundary. Let $\phi$ be the unique solution to $\nabla^{2} \phi=0$ in $V$, with $\phi=f(\mathbf{x})$ on $S$, where $f$ is a given function. Consider any smooth function $w$ also equal to $f(\mathbf{x})$ on $S$. Show, by using Green's first theorem or otherwise, that

  $$\int_{V}|\nabla w|^{2} d V \geqslant \int_{V}|\nabla \phi|^{2} d V$$

  [Hint: Set $w=\phi+\delta .]$

  Consider the partial differential equation

  $$\frac{\partial}{\partial t} w=\nabla^{2} w$$

  for $w(t, \mathbf{x})$, with initial condition $w(0, \mathbf{x})=w_{0}(\mathbf{x})$ in $V$, and boundary condition $w(t, \mathbf{x})=$ $f(\mathbf{x})$ on $S$ for all $t \geqslant 0$. Show that

  $$\frac{\partial}{\partial t} \int_{V}|\nabla w|^{2} d V \leqslant 0$$

  with equality holding only when $w(t, \mathbf{x})=\phi(\mathbf{x})$.

  Show that $(*)$ remains true with the boundary condition

  $$\frac{\partial w}{\partial t}+\alpha(\mathbf{x}) \frac{\partial w}{\partial n}=0$$

  on $S$, provided $\alpha(\mathbf{x}) \geqslant 0$.

  3/II/10A Vector Calculus

  Write down Stokes' theorem for a vector field $\mathbf{B}(\mathbf{x})$ on $\mathbb{R}^{3}$.

  Consider the bounded surface $S$ defined by

  $$z=x^{2}+y^{2}, \quad \frac{1}{4} \leqslant z \leqslant 1$$

  Sketch the surface and calculate the surface element $d \mathbf{S}$. For the vector field

  $$\mathbf{B}=\left(-y^{3}, x^{3}, z^{3}\right)$$

  calculate $I=\int_{S}(\nabla \times \mathbf{B}) \cdot d \mathbf{S}$ directly.

  Show using Stokes' theorem that $I$ may be rewritten as a line integral and verify this yields the same result.

  comment