Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 4

The Euclidean algorithm givesBack-substitution supplies the Bezout identityThus one solution is $(x,y)=(-5,2)$. If $(x,y)$ is any solution, subtraction gives $7(x+5)+18(y-2)=0$. Since $7$ and $18$ are coprime, $18$ divides $x+5$. Write $x+5=18t$; substitution then gives $y-2=-7t$. Conversely these values satisfy the equation for every integer $t$. Hence all solutions are

Factor the expression as $n^3-n=(n-1)n(n+1)$. One of three consecutive integers is divisible by $3$, so $3\mid n^3-n$. If $n$ is odd, its neighbours $n-1$ and $n+1$ are consecutive even integers. One is divisible by $4$ and the other by $2$, so their product is divisible by $8$. Since $3$ and $8$ are coprime integers, their product divides the expression:The argument also includes negative odd integers and the zero product at $n=\pm 1$.

Define the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ as the number of $k$-element subsets of an $n$-element set. Equivalently it is $n!/[k!(n-k)!]$: there are $n(n-1)\cdots (n-k+1)$ ordered lists of $k$ distinct elements, and each subset gives $k!$ such lists. The empty subset gives $\left(\genfrac{}{}{0ex}{}{n}{0}\right)=1$.

Distinguish one element of the set. A $k$-element subset either omits it, giving $\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$ possibilities, or contains it and chooses its other $k-1$ elements from the remaining set, giving $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ possibilities. These cases are disjoint and exhaustive, proving Pascal's identity:For the requested sum, fix $n\ge 0$ and use mathematical induction on $k$. At $k=0$, both sides equal one. If the assertion holds at $k$, adding the next summand giveswhere the last equality is Pascal's identity. Thus the induction proves the hockey-stick identity for all nonnegative $n,k$:

Take upward velocity as positive, and consider the closed material system consisting of the rocket and the fuel it ejects during a short interval $dt$. Initially its mass and momentum are $m$ and $mv$. Let $\delta m>0$ be the ejected mass, so the rocket's mass change is $dm=-\delta m$. At the end its velocity is $v+dv$, while the ejected gas has inertial velocity $v-u$ to first order; its downward relative velocity need not be downward in the inertial frame.

The final total momentum, to first order, isNeglect air resistance and take the gravitational acceleration $g$ constant. The external gravitational impulse on this material system is $-mgdt$ to first order. Newton's second law therefore gives $mdv-u\delta m=-mgdt$, orThe positive thrust is $-u\dot{m}$ because fuel loss makes $\dot{m}<0$. Applying $d(mv)/dt$ to the rocket alone without accounting for the escaping momentum would give the wrong equation.

For constant $u$ and positive mass, divide by $m$ and integrate from release at $t=0$:Thus the gravity-corrected rocket equation is equivalent to

The potential factors as $V=x^2(3-2x)$, so its zeros are $0$ and $3/2$, with a double zero at the origin. Its derivatives are $V^{\prime }=6x(1-x)$ and $V^{\prime \prime }=6-12x$. Thus there is a local minimum $(0,0)$, a local maximum $(1,1)$ and an inflection at $(1/2,1/2)$. The potential tends to $+\infty$ on the far left and $-\infty$ on the far right. These features determine the left-hand sketch.

Put $v=\dot{x}$. Newton's second law gives the phase plane system $\dot{x}=v$, $\dot{v}=-V^{\prime }=6x(x-1)$. Its conserved mechanical energy and trajectories areThe linearization at $(0,0)$ has eigenvalues $\pm i\sqrt{6}$, and the surrounding energy curves are closed, so it is a center equilibrium. At $(1,0)$ the eigenvalues are $\pm \sqrt{6}$, giving a saddle equilibrium. The figure shows the cubic potential barrier phase portrait; arrows point right when $v>0$ and left when $v<0$.

For $0<E<1$, there are three turning-point roots of $V(x)=E$. The two leftmost enclose a closed orbit around the origin: the particle oscillates between them. There is also a separate open component to the right of the third root, where an incoming particle turns and escapes to $+\infty$. The closed orbits run clockwise in the $(x,v)$ plane.

For $E=1$, the factorization $1-V(x)=(x-1{)}^2(2x+1)$ gives the separatrixThe branch with $-1/2\le x<1$ is a homoclinic orbit: it leaves the saddle asymptotically, turns at $x=-1/2$ and returns asymptotically. On $x>1$, one branch approaches the saddle and the other departs towards infinity. Approaching the saddle takes infinite time. The saddle itself is also an equilibrium trajectory.

For $E>1$, the particle can cross the barrier. There is one left turning point below $-1/2$; an incoming particle passes through the well, turns on the left and escapes to the right. For $E<0$, only a right-hand open component exists, with its turning point beyond $3/2$. At $E=0$, the stationary centre coexists with a right-hand open trajectory turning at $3/2$. Thus negative energy does not imply trapping here: the cubic potential is unbounded below on the right.

For finite sets $A_1,\dots ,A_s$, the inclusion-exclusion principle statesTo prove it, consider an element belonging to exactly $d$ of the sets. If $d=0$, it contributes zero to both sides. If $d>0$, its contribution on the right iswhich is its contribution to the union. Summing these contributions proves the formula.

For the keypad, a first digit zero cannot be entered. Define four families of valid codes: $A$ consists of all codes with no zero; $B$ consists of codes beginning with $2$; $C$ consists of $110b$ with $b\in \{1,\dots ,9\}$; and $D$ consists of $a110$ with $a\in \{1,\dots ,9\}$. They cover every valid code. Indeed, if the first digit is not $2$, a zero in the second position is impossible; a zero in the third requires the prefix $11$; a zero in the fourth requires the middle pair $11$. In the third-position case the last digit cannot also be zero. Hence the only remaining zero-containing possibilities are exactly $C$ and $D$.

Their cardinalities areThe only nonempty pairwise intersections are $A\cap B$, with $9^3=729$ codes, and $B\cap D=\{2110\}$, with one code. All triple and fourfold intersections are empty. Applying inclusion-exclusion therefore givesThe restriction concerns actual preceding keypresses. It cannot license two successive zeros unless the first-key condition is already satisfied.

We use these countability facts: the integers are countable; a finite Cartesian product of countable sets is countable; a countable union of countable sets is countable; and every subset of a countable set is countable. Finite products can be enumerated by listing index tuples in increasing maximum coordinate, and countable unions by diagonal enumeration of pairs of indices.

Fix $d\ge 1$. For each degree bound $D$, there are finitely many monomials $X_1^{{\alpha }_1}\cdots X_d^{{\alpha }_d}$ with ${\alpha }_1+\cdots +{\alpha }_d\le D$. An integer polynomial of total degree at most $D$ is specified by an integer coefficient for each of them, so these polynomials form a finite Cartesian product of copies of $\mathbb{Z}$ and are countable. Every polynomial has some finite degree bound. Taking the union over $D=0,1,2,\dots$ proves the countability of integer polynomial rings:It is infinite because it contains all integer constant polynomials.

For $d=1$, each nonzero polynomial has only finitely many real roots: repeated application of the factor theorem bounds their number by its degree. The real algebraic numbers are the union of these finite root sets over the countably many nonzero integer polynomials. Thus they are countable. If the real transcendental numbers were countable too, their union with the algebraic numbers would make $\mathbb{R}$ countable, contrary to the allowed uncountability assumption. Hence there are uncountably many real transcendental numbers.

To construct an algebraically independent real sequence, choose $x_1$ outside the algebraic numbers. Suppose $x_1,\dots ,x_d$ already satisfy the required nonvanishing condition. For each nonzero $P\in \mathbb{Z}[X_1,\dots ,X_d,T]$, writeAt least one coefficient polynomial $P_j$ is nonzero, and the inductive hypothesis makes its value at $(x_1,\dots ,x_d)$ nonzero. Consequently $P(x_1,\dots ,x_d,T)$ is a nonzero one-variable polynomial and has only finitely many real roots. There are countably many choices of $P$, so the union of all these forbidden roots is countable. Choose $x_{d+1}$ outside it, which is possible because $\mathbb{R}$ is uncountable. This extends the nonvanishing condition to $d+1$. Recursion therefore givesIn particular the chosen numbers are distinct, since a relation $X_i-X_j$ is forbidden. Clearing rational denominators shows that every finite initial segment consists of algebraically independent elements over $\mathbb{Q}$.

A real sequence $x_n$ converges to $l$ if, for every $\epsilon >0$, there is an integer $N$ such that $|x_n-l|<\epsilon$ for every $n\ge N$. A convergent series ${\sum }_{n=1}^{\infty }{x}_n$ is one whose partial sums $s_N={\sum }_{n=1}^N{x}_n$ converge to a finite real limit.

If $s_N\to s$, then $x_N=s_N-s_{N-1}\to s-s=0$. This necessary condition is the term test for divergence. Its converse fails: the harmonic series has terms $1/n\to 0$ but diverges. For a direct proof, each block from $n=2^{j-1}+1$ to $2^j$ contains $2^{j-1}$ terms each at least $2^{-j}$, so contributes at least $1/2$. Infinitely many such blocks make the partial sums unbounded.

For the positive sequences in the final request, the inequality makes $y_n$ decreasing and bounded below by zero. The bounded monotone sequence theorem gives $y_n\to l\ge 0$. Summing the decrements givesSuppose $l>0$. Since $y_n\ge l$, this impliesBut clipping preserves divergence of a positive series: if infinitely many $x_n\ge l$, the clipped series has infinitely many terms equal to $l$; otherwise its tail equals the divergent tail of $\sum x_n$. Either case contradicts the displayed bound. Hence the only possible limit isThis proves the minimum-decrement convergence criterion without assuming that the divergent positive sequence $x_n$ itself tends to zero.

If the prime $p$ does not divide $x$, then $\gcd (p,x)=1$. The Bezout identity gives integers $a,b$ with $ap+bx=1$. Multiplying by $y$ gives $apy+bxy=y$. If $p\mid xy$, both terms on the left are divisible by $p$, so $p\mid y$. Thus Euclid lemma holds:For completeness, existence in the fundamental theorem of arithmetic follows by strong induction on a positive integer $n>1$. If $n$ is prime there is nothing to prove; otherwise $n=ab$ with $1<a,b<n$, and the inductive prime factorizations of $a,b$ give one for $n$. The integer $1$ has the empty factorization.

For uniqueness, suppose $p_1\cdots p_r=q_1\cdots q_s$ are two prime factorizations. Repeated application of Euclid lemma shows that $p_1$ divides some $q_j$. Both are primes, so they are equal. Reorder the second list, cancel this equal factor, and repeat. All factors must be matched, including their multiplicities. Thus prime factorization exists and is unique up to the order of its factors. For nonzero negative integers one also records the sign.

The Fermat-Euler theorem states that, for a positive integer $q$ and an integer $a$ coprime to $q$, $a^{\phi (q)}\equiv 1(\mathrm{mod}q)$, where the Euler totient function $\phi (q)$ counts residue classes coprime to $q$. The case $q=1$ is trivial. For $q>1$, let $r_1,\dots ,r_{\phi (q)}$ be a reduced residue system. Multiplication by $a$ permutes it: equality of two resulting residues can be cancelled using the modular inverse of $a$, and the products remain coprime to $q$. Multiplying the residues before and after the permutation givesEvery factor on the right is a unit, so its product can be cancelled. This provesThe integer $359$ is prime: none of the primes $2,3,5,7,11,13,17$ up to $\sqrt{359}<19$ divides it. Therefore $\phi (359)=358$. Apply the theorem to $60$ and use the supplied congruence:To connect this to individual digits rather than merely assert periodicity, use long-division remainders $r_0=1$ andInduction gives $r_n\equiv 10^n(\mathrm{mod}359)$. Since $10$ is coprime to $359$, no remainder is zero. The congruence above therefore implies $r_{n+179}=r_n$ for every $n\ge 0$, using the unique representative in $1,\dots ,358$. In particularHenceThis is the mechanism of decimal period from multiplicative order: the period divides $179$.

The relevant parameters are $a,h,g$ and the ring mass $m$, with dimensions length, length, length/time${}^2$ and mass. The wire is fixed and smooth, so there is no additional friction parameter. Because $m$ is the only parameter carrying a mass dimension, it cannot enter a dimensionless group governing the period. Using $a$ and $g$ as the length and time scales, the independent dimensionless variables are $T\sqrt{g/a}$ and $h/a$. Dimensional analysis therefore givesThe physical mass cancellation also follows from the energy equation in part (ii), since kinetic and gravitational potential energy are both proportional to $m$.

Along the holonomic constraint $z=x^2/(4a)$, we have $\dot{z}=x\dot{x}/(2a)$ and hence speed squared $(1+x^2/(4a^2)){\dot{x}}^2$. The smooth wire's normal reaction is perpendicular to the permitted velocity and does no work. Conservation of mechanical energy, with release from rest at height $h$, givesThe turning points are $x=\pm x_0$ with $x_0=2\sqrt{ah}$. One full oscillation has twice the travel time between them:Set $x=x_{0}u$ and $\beta =h/a$. After cancelling the scale factors,so the bead on a parabolic wire hasFor $\beta \ll 1$, expand the numerator uniformly on $[-1,1]$:The integrable endpoint weight gives ${\int }_{-1}^1(1-u^2{)}^{-1/2}du=\pi$ and ${\int }_{-1}^1{u}^2(1-u^2{)}^{-1/2}du=\pi /2$, for example by $u=\sin \theta$. Therefore the requested small-oscillation period isThe leading frequency is $\sqrt{g/(2a)}$, and the first finite-amplitude correction increases the period. At $h=0$ the ring is stationary; the expression is the limiting period of nonzero small oscillations.

Dot Newton's second law with $\dot{\mathbf{r}}$. The magnetic cross-product term is perpendicular to this velocity, soThusorThe two halves are the kinetic energy and the isotropic spring's potential energy. The expression in the question is twice their sum. The Lorentz force changes the direction of motion but supplies no power, because it is perpendicular to velocity; this explains why the magnetic field does not appear in the conserved mechanical energy. The sign corresponds to charge $-e$.

Write $\mathbf{v}=\dot{\mathbf{r}}$. The original PDF contains the cross product $\dot{\mathbf{r}}\times \mathbf{r}$; the TeX aid drops its velocity dot. Since $\mathbf{v}\times \mathbf{v}=0$, differentiation and the equation of motion giveThe radial restoring force contributes no torque. The vector triple-product identity yieldsMeanwhileThe derivatives cancel, provingThis is the magnetic axial angular-momentum invariant. Its first term is the negative of the ordinary angular momentum projected on $\mathbf{B}$; retaining that sign is essential.

Let $q(t)=\mathbf{r}(t)\cdot \mathbf{B}$. Since the field is constant, dotting the equation of motion with $\mathbf{B}$ eliminates the magnetic term:This is a harmonic oscillator with frequency $\omega =\sqrt{k/m}$. Initially $q(0)={\mathbf{r}}_0\cdot \mathbf{B}$ and $\dot{q}(0)=0$, because the particle starts at rest. ThereforeThe magnetic force modifies the transverse motion but not this projection. The formula also holds trivially when $\mathbf{B}=0$.

For a fixed central gravitational source, the radial and transverse components of Newton's second law in polar coordinates areThe second equation gives $r^2\dot{\theta }=h$, the constant specific angular momentum. Take $h>0$ by choosing the orientation of $\theta$, and put $u=1/r$. Writing $u^{\prime }$ and $u^{\prime \prime }$ for derivatives with respect to $\theta$,Substituting into the radial equation and dividing by $-h^2{u}^2$ proves the Binet equationAt perihelion the velocity is tangential. The escape velocity is $v_0=\sqrt{2GM/r_0}$, so $h=r_0{v}_0$ and $h^2=2GM{r}_0$. Consequently $k=1/(2r_0)$. The initial conditions are $u(0)=1/r_0$ and $u^{\prime }(0)=0$. Solving the linear ordinary differential equation gives the parabolic Kepler orbitUsing angular momentum conservation again,On the outgoing branch $r=2r_0$ is first reached at $\theta =\pi /2$. Integrate from release at perihelion, using $w=\tan (\theta /2)$:More generally the same integral gives $t=(2r_0^2/h)(w+w^3/3)$, the Barker equation for this parabolic orbit.

For constant particle masses define the centre of mass by $M\mathbf{X}={\sum }_i{m}_i{\mathbf{r}}_i$, with $M={\sum }_i{m}_i$. Summing Newton's second law over all particles givesEach pair of internal forces cancels by Newton's third law. HenceOnly the action-reaction condition is needed for this translation law; centrality of the internal forces is needed for the angular momentum result in part (ii).

About a fixed inertial origin, the total angular momentum is $\mathbf{L}={\sum }_i{m}_i{\mathbf{r}}_i\times {\dot{\mathbf{r}}}_i$. Differentiation givesbecause ${\dot{\mathbf{r}}}_i\times {\dot{\mathbf{r}}}_i=0$. Separate the external and internal contributions. The combined torque of an internal pair isThe first equality uses Newton's third law, and the second uses the given central-force condition. All internal torques therefore cancel, leavingAn equal-and-opposite pair which is not central need not have zero combined torque; this explains why both internal-force hypotheses matter.

Write ${\mathbf{r}}_i=\mathbf{X}+{\mathbf{r}}_i^{\prime }$ and ${\mathbf{v}}_i=\mathbf{V}+{\mathbf{v}}_i^{\prime }$, where $\mathbf{V}=\dot{\mathbf{X}}$. The definition of the centre of mass and its derivative giveExpand the total angular momentum:The two middle terms vanish. Thus the angular momentum decomposition about the centre of mass isThe first term is orbital angular momentum of the centre; the second is angular momentum about the centre of mass.

Let $r=|{\mathbf{r}}_1-{\mathbf{r}}_2|$ and $\hat{\mathbf{r}}=({\mathbf{r}}_1-{\mathbf{r}}_2)/r$. A differentiable central potential energy gives the internal forcesThere are no external forces. Differentiating the total kinetic energy and using Newton's second law therefore givesSince $\dot{r}=\hat{\mathbf{r}}\cdot ({\mathbf{v}}_1-{\mathbf{v}}_2)$, the last expression is $-U^{\prime }(r)\dot{r}=-dU/dt$. ThusThis conserves total mechanical energy, including the kinetic energy of centre-of-mass motion, not merely the relative kinetic energy.