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

The extended Euclidean algorithm givesBack-substituting in these equations produces the Bezout identityThus one integer solution is $\boxed{x=12,y=-7}$. In fact, subtracting this Bezout identity from any other solution and using that $17$ and $29$ are coprime integers gives all solutions: $x=12+29t$, $y=-7-17t$, where $t\in \mathbb{Z}$.

For the modular arithmetic calculation, $29$ is a prime number and $17$ is coprime to it, so Fermat little theorem gives $17^{28}\equiv 1(\mathrm{mod}29)$. Since $138=5\cdot 28-2$, and the preceding Bezout identity identifies $12$ as the modular multiplicative inverse of $17$, we obtainConsequently the least positive representative is $\boxed{28}$.

For a nonempty set $S\subseteq \mathbb{R}$, an upper bound in a partially ordered set is a real number $u$ such that $s\le u$ for every $s\in S$. Its supremum, or least upper bound, is an upper bound $L$ with $L\le u$ for every upper bound $u$. The least-upper-bound property asserts that every nonempty set of real numbers bounded above has a real supremum.

Let $(x_n)$ be a bounded, increasing sequence; here increasing allows $x_{n+1}=x_n$. Apply the least-upper-bound property to its set of terms and put $L=\sup \{x_n:n\ge 1\}$. Given $\epsilon >0$, the number $L-\epsilon$ cannot be an upper bound, so some $x_N$ satisfies $x_N>L-\epsilon$. The monotone sequence property then givesHence $|x_n-L|<\epsilon$ for all $n\ge N$. This proves the monotone bounded sequence result, with limit $\boxed{x_n⟶L}$.

For the two series, define their partial sums $A_N={\sum }_{n=1}^N{a}_n$ and $B_N={\sum }_{n=1}^N{b}_n$. Positivity makes both partial-sum sequences increasing, and termwise comparison gives $0<B_N\le A_N$. Since $(A_N)$ is a convergent sequence, it is bounded above, and therefore so is $(B_N)$. Applying the monotone bounded sequence result already proved shows that $(B_N)$ converges. By the definition of a convergent series, ${\sum }_{n=1}^{\infty }{b}_n$ converges. This is the comparison test for series for positive terms.

Use Newton's second law, $F=ma$. Acceleration has physical dimension $L{T}^{-2}$, so multiplying by mass gives the dimension of forceThe bracket notation records a physical dimension, rather than the numerical value or the choice of units.

The torque about an origin is $\mathbf{\tau }=\mathbf{r}\times \mathbf{F}$. A cross product multiplies the dimensions of its factors, so torque has the physical dimension of length times force:

The work done by a force is $W=\int \mathbf{F}\cdot d\mathbf{r}$. By the work-energy theorem, this has the same physical dimension as energy. ThusAlthough torque and energy have the same physical dimension, they represent different physical quantities.

From Newton's law of universal gravitation, $F=G{m}_1{m}_2/r^2$, the gravitational constant has physical dimensionHere the two factors of mass and the inverse square of the separation determine the powers of $M$ and $L$.

An electric field is defined through the electric force on a stationary electric charge: $\mathbf{F}=q\mathbf{E}$. Therefore the electric-field dimension is

For the magnetic part of the Lorentz force, $\mathbf{F}=q\mathbf{v}\times \mathbf{B}$. Since velocity has physical dimension $L{T}^{-1}$, the magnetic field has dimension

Use Coulomb's law in vacuum, $F=q_1{q}_2/(4\pi {ϵ}_0{r}^2)$. The constant $4\pi$ is dimensionless, so the vacuum-permittivity dimension isThus the physical dimension of vacuum permittivity follows directly from the dimensions of electric charge, force, and separation.

In a circular orbit, $r=a$ is constant, so the radial acceleration vanishes. The radial equation requiresFor every $a>0$, this equation permits a real nonzero specific angular momentum, $h=\pm \sqrt{k{a}^{n+3}}$, and hence a circular orbit. This chooses $h$ for the desired radius; it does not claim that one prescribed value of $h$ permits every radius.

To test circular-orbit stability for a power-law central force, keep that chosen specific angular momentum fixed and write $r=a+\rho$, with $|\rho |\ll a$. The radial equation becomesExpanding to first order and using $h^2=k{a}^{n+3}$ givesFor $n>-3$, the linearized equation is the harmonic oscillator equation, withThe radial disturbance undergoes bounded small oscillations, rather than growing. Equivalently, the effective potential has a strict local minimum: its second derivative at $a$ is $(n+3)k{a}^{n-1}>0$. By the effective potential stability criterion, sufficiently small radial disturbances remain small, proving stability for $n>-3$. For comparison, $n<-3$ gives exponential growth. At $n=-3$, the balancing value $h^2=k$ makes the radial acceleration identically zero, so a small radial velocity produces drift rather than a restoring oscillation.

Suppose $f:S\to \mathcal{P}(S)$ were a surjective function. Form the subsetSince $D$ belongs to the power set, surjectivity would give $D=f(d)$ for some $d\in S$. But then $d\in D$ holds if and only if $d\notin f(d)=D$, a contradiction. Thus no such function is surjective, and in particular there is no bijection from $S$ to its power set. This is Cantor theorem; the argument also applies when $S$ is empty.

For infinite binary sequences, use the bijectionwith $\mathcal{P}(\mathbb{N})$, taking $\mathbb{N}=\{1,2,\dots \}$. Conversely, a subset determines its sequence of membership indicators. The power set is infinite, since it contains all singletons, and Cantor theorem rules out a bijection with $\mathbb{N}$. Hence it is an uncountable set, as is the set of infinite binary sequences. Equivalently, a proposed enumeration $(x_n^{(j)}{)}_{n\ge 1}$ is defeated by the sequence $y_j=1-x_j^{(j)}$, which differs from its $j$th listed sequence at position $j$. This is the Cantor diagonal argument.

Write $A=\{a_1,\dots ,a_m\}$ and enumerate $B=\{b_1,b_2,\dots \}$. Each injective function $f:A\to B$ is determined by the finite tuple $(f(a_1),\dots ,f(a_m))$. Thus these functions form a subset of the finite Cartesian product $B^m$. A finite Cartesian power of a countable set is countable: for example, group the index tuples by the maximum of their coordinates, obtaining a countable union of countable sets consisting of finite groups.

There are also infinitely many such injective functions, sincedefines pairwise distinct examples. Therefore $S_1$ is a countably infinite set.

Again let $A=\{a_1,\dots ,a_m\}$ with $m>1$, and enumerate $B=\{b_1,b_2,\dots \}$. For each infinite binary sequence $x=(x_j{)}_{j\ge 1}$, define a function $g_x$ byThe first $m$ values make every $g_x$ a surjective function, while the remaining values recover $x$ uniquely. Hence $x\mapsto g_x$ is an injective function from the uncountable set of binary sequences into $S_2$. This proves $S_2$ is an uncountable set, an instance of uncountability of surjections onto a nontrivial finite set.

Partition the enumeration of $B$ into the pairs $\{b_{2j-1},b_{2j}\}$, for $j\ge 1$. An infinite binary sequence $x$ determines a bijection $h_x:B\to B$: leave the $j$th pair fixed when $x_j=0$, and interchange its two elements when $x_j=1$. Each element stays in its own pair, so this function is a bijection, indeed its own inverse.

Different binary sequences give different bijections, since a changed bit changes the action on the corresponding pair. We have therefore embedded an uncountable set into $S_3$. Hence $S_3$ is uncountable, proving uncountability of permutations of a countably infinite set.

Multiplying the desired representation by $b_1{b}_2$ turns it into the integer equationSince $b_1$ and $b_2$ are coprime integers, the necessary modular multiplicative inverses exist. Choose the unique representativesThen $a-a_1{b}_2-a_2{b}_1$ is divisible by both $b_1$ and $b_2$, hence by their product, because they are coprime. Definingtherefore gives an integer and proves existence. Any other representation, reduced modulo $b_1$ and $b_2$, must have the same $a_1$ and $a_2$, since their allowed ranges contain exactly one representative of each residue. The integer equation then forces the same $n$. This proves uniqueness.

For the prime-power fraction decomposition, put $d_i=p_i^{n_i}$ and $B_i=b/d_i$. The distinct prime-power factors $d_i$ are pairwise coprime, and $B_i$ has a modular multiplicative inverse modulo $d_i$. DefineEvery term $q_j{B}_j$ with $j\ne i$ is divisible by $d_i$, while $q_i{B}_i\equiv a(\mathrm{mod}{d}_i)$. Thus $a-{\sum }_i{q}_i{B}_i$ is divisible by all the pairwise coprime $d_i$ and therefore by $b$. With $n=(a-{\sum }_i{q}_i{B}_i)/b$, division by $b$ yields the required representation. Reducing any such representation modulo each $d_i$ proves uniqueness exactly as above. This is the residue-solving mechanism of the Chinese remainder theorem.

For $315=9\cdot 5\cdot 7$, the complementary factors are $35,63,45$. The required modular inverses givebecause $35\cdot 8\equiv 1(\mathrm{mod}9)$, $63\cdot 2\equiv 1(\mathrm{mod}5)$, and $45\cdot 5\equiv 1(\mathrm{mod}7)$. Their numerator sum is $280+126+225=631=1+2\cdot 315$. Thus the unique decomposition is

For finite sets $E_1,\dots ,E_s$, the inclusion-exclusion principle statesIt counts each element once: an element in exactly $q$ of the sets contributes ${\sum }_{j=1}^q(-1{)}^{j+1}(\genfrac{}{}{0ex}{}{q}{j})=1$, by the binomial theorem.

For the cyclic digit run problem, let $E_j$ mean that the three digits starting at position $j$ form a run, for $j=1,2,3,4$. Every run of length at least three contains one of these triples, so we need $|E_1\cup E_2\cup E_3\cup E_4|$. Introduce the five differencesA starting digit and these five residues determine a unique string, including runs that cross $9$ and $0$. In these coordinates $E_j$ requires $(d_j,d_{j+1})=(1,1)$ or $(-1,-1)$.

Each single event fixes two differences, with two choices of sign; the initial digit and the other three differences are free. Thus $|E_j|=10\cdot 2\cdot 10^3=20000$. For intersections of two events, adjacent starting positions force three consecutive differences to have the same sign, giving $10\cdot 2\cdot 10^2=2000$. There are three such pairs. The other three pairs have disjoint constrained difference positions, with independent signs and one free difference, giving $10\cdot 4\cdot 10=400$ each. Consequently the sum of pair-intersection sizes is $3\cdot 2000+3\cdot 400=7200$.

For triple intersections, $E_1\cap E_2\cap E_3$ and $E_2\cap E_3\cap E_4$ each force four consecutive differences to have the same sign, leaving one free difference, and each has size $10\cdot 2\cdot 10=200$. The other two triples, $E_1\cap E_2\cap E_4$ and $E_1\cap E_3\cap E_4$, divide the five differences into two blocks with independent signs; each has size $10\cdot 4=40$. The triple-intersection sum is therefore $480$. Finally, all four events force all five differences to have the same sign, giving $20$ strings.

The inclusion-exclusion principle now gives the number of stringsUsing differences makes the overlap conditions explicit and prevents double-counting long cyclic digit runs.

First establish the binomial theorem needed throughout this question. For integers $0\le m\le n$, define the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ to be the number of $m$-element subsets of an $n$-element set. Counting ordered selections and then forgetting their order giveswith the factorial convention $0!=1$. In the product of $n$ factors $(1+z)$, choose $z$ from exactly $m$ factors and $1$ from the others. Each choice contributes $z^m$, and there are $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ choices. The distributive law therefore provesfor every complex number $z$, including $n=0$ by the empty-product convention.

To evaluate the even-indexed sum, use the even part of a polynomial: averaging the binomial theorem at $z$ and $-z$ cancels the odd powers. For $z=i\sqrt{3}$,The two complex numbers satisfy $1\pm i\sqrt{3}=2e^{\pm i\pi /3}$. Their $6n$th powers are both $2^{6n}$, since $e^{\pm 2\pi in}=1$. Thus the sum is

Differentiate the finite binomial theorem and set $z=1$. For $n\ge 1$ this givesFor $n=0$ the sum is $0$ directly.

For the alternating binomial moments, it is useful to differentiate in a form that introduces falling factorials. Write $(m{)}_j=m(m-1)\cdots (m-j+1)$, with $(m{)}_0=1$. Differentiating the binomial theorem $j$ times and multiplying by $z^j$ yields, for $0\le j\le n$,At $z=-1$, the right side vanishes when $j<n$, and equals $(-1{)}^{n}n!$ when $j=n$.

The polynomials $(X{)}_0,\dots ,(X{)}_r$ have degrees $0,\dots ,r$ and leading coefficient $1$, so successive cancellation of leading terms expresses $X^r$ as a linear combination of them. If $r<n$, every falling-factorial term has index $j<n$ and hence its alternating sum vanishes. If $r=n$, the coefficient of $(X{)}_n$ is $1$, and all lower-index terms still vanish. Therefore the alternating moments areFor $n=0$, the latter identity uses the constant polynomial $X^0=1$, so its value at $X=0$ is $1$; thus $S_0(0)=1$ as well. This makes the edge-case convention explicit rather than treating $0^0$ as an unrelated numerical expression.

Work in one fixed inertial frame, and take positive velocity in the rocket's direction. During $d\tau$, the rocket ejects the positive amount of mass $-m^{\prime }(\tau )d\tau$. Its exhaust has inertial velocity $v(\tau )-u$, by the Galilean transformation of velocities. Once expelled, that material retains its velocity because it experiences no external force. The system's momentum is therefore the rocket momentum plus the sum of all these exhaust momenta:The minus sign comes from the positive expelled mass being $-m^{\prime }(\tau )d\tau$.

Differentiate, applying the product rule to the rocket momentum and the fundamental theorem of calculus to the integral:The momentum conservation law thus gives the nonrelativistic rocket equation

The same bookkeeping for kinetic energy givesIts derivative iswhere the rocket equation cancels the first two terms. Thus kinetic energy increases during mass ejection, with $\boxed{K^{\prime }=-u^2{m}^{\prime }/2>0}$ when $u>0$ and $m^{\prime }<0$. This does not violate conservation of energy: the increase comes from stored internal energy.

Now $m$ denotes the instantaneous rest mass of the rocket, including its fuel and stored internal energy, and $v$ is measured in a fixed inertial frame. Assume the exhaust is expelled backwards with speed $0<u<c$ in the rocket's instantaneous rest frame. By the relativistic velocity-addition formula, material emitted at time $\tau$ has inertial velocityIt coasts at this velocity after emission.

The crucial change is that the expelled material's rest mass is not simply $-dm$: some of the rocket's rest energy becomes exhaust motion. Instead, use conservation of relativistic energy. Put $q(t)=m(t)\gamma (t)$, so the rocket's energy is $c^{2}q(t)$. The exhaust emitted during $d\tau$ carries energy $-c^2{q}^{\prime }(\tau )d\tau$. For material moving at velocity $w$, the relativistic energy-momentum relation gives momentum $wE/c^2$, since $E={\gamma }_{\mathrm{ex}}\mu c^2$ and $p={\gamma }_{\mathrm{ex}}\mu w$. Hence the modified total momentum isMeanwhile the total relativistic energy is $c^2[q(t)-{\int }_0^t{q}^{\prime }(\tau )d\tau ]=c^{2}q(0)$. These expressions consistently account for both energy and momentum of the expelled material.

Differentiate the momentum formula. The momentum conservation law givesTo simplify it, useMultiplying by ${\gamma }^2(1-uv/c^2)$, the equation becomesThe two terms containing $uv/c^2$ cancel. Dividing by $\gamma >0$ proves the relativistic rocket equation

For fixed finite velocities, the nonrelativistic limit $c\to \infty$ gives ${\gamma }^2=(1-v^2/c^2{)}^{-1}\to 1$. Hence the relativistic rocket equation reduces towhich is the nonrelativistic rocket equation.

The conserved quantities called energy in the two calculations include different contributions. The nonrelativistic calculation considered only kinetic energy, which increases as fuel releases internal energy; total energy including that internal reservoir is still conserved. Relativistic energy includes rest energy, and therefore includes the fuel's stored internal energy through the rocket's rest mass. That rest mass decreases as energy is transferred into the exhaust. Thus conservation of relativistic energy and the nonconservation of kinetic energy express the same physical conversion.

For unit mass, the inverse-square force has potential energy $-k/r$, with zero potential at infinity. Conservation of angular momentum gives $r^2\dot{\theta }=h$. Differentiate the polar equation of the Kepler orbit:Consequently the total mechanical energy iswhere $k=h^2/\ell$. This also explains the sign distinction between an elliptic orbit, a parabolic Kepler orbit, and a hyperbolic Kepler orbit.

At the original periapsis, the parabolic Kepler orbit has $e=1$, $r=d=\ell /2$, and purely tangential speed $V$. ThusThe outward radial impulse has zero moment about the Sun, so it preserves angular momentum and hence $\ell$. Its additional velocity is perpendicular to the original velocity, so the new mechanical energy is $E^{\prime }={\alpha }^2{V}^2/2$. Applying the energy formula givesFor $\alpha >0$, the new orbit is a hyperbolic Kepler orbit; $\alpha =0$ leaves the parabola unchanged.

To fix the orientation of the sketch, put the Sun at the origin, the impulse point at $(d,0)$, and take the original motion there upwards. The new velocity is $(\alpha V,V)$. The eccentricity vector isIt points towards the new periapsis, which is rotated clockwise through $\beta =\arctan (2\alpha )$ from the original periapsis direction. Thus, measured using the original polar angle $\theta$, the new orbit isIn particular, the impulse point is already on the outgoing part of the new orbit and is not its new periapsis. The old parabola satisfies $x=d-y^2/(4d)$. Both orbits pass through $(d,0)$ and have the same focus, but the hyperbola's new periapsis axis is tilted.

In the Earth inertial frame, the return journey takes $2d/v$. Bob is at rest in this frame, while Alice's proper time is reduced by the Lorentz factor $\gamma =(1-v^2/c^2{)}^{-1/2}$. Neglecting the short turnaround interval, their increases in age are

The twin paradox is the apparent contradiction from applying reciprocal time dilation to claim that each twin must be younger than the other. Alice changes inertial frames at the turnaround, so a single comoving inertial frame cannot describe her whole journey; Bob uses one inertial frame throughout. The twins follow different world lines, and integrating proper time along those world lines gives the displayed, consistent ages. The change in Alice's notion of simultaneity at turnaround removes the apparent contradiction. Acceleration distinguishes the paths; its magnitude is not an additional local rule for aging.

The meetings occur where Bob's constant position $x=\alpha c{t}_0$ intersects Alice's positive-$x$ branch of the hyperbolic motion:Bob is at rest in this inertial frame, so his elapsed proper time is

Parametrize Alice's world line bySince $t$ increases with $\eta$, the proper time element isAt the meetings, $\cosh \eta =\alpha$, giving endpoints $\eta =\pm \mathrm{arcosh}\alpha$. Thus Alice's elapsed proper time isHere $\mathrm{arcosh}$ is the nonnegative real inverse hyperbolic cosine. As a check, if $\alpha =\cosh {\eta }_{\ast }$ with ${\eta }_{\ast }>0$, then Bob ages by $2t_0\sinh {\eta }_{\ast }$ and Alice by $2t_0{\eta }_{\ast }$; $\sinh {\eta }_{\ast }>{\eta }_{\ast }$ confirms that Bob again ages more.

Use an Earth-centred rotating reference frame, with Earth's constant angular velocity vector $\mathbf{\omega }$. The vectors $\mathbf{r}$, $\mathbf{v}$, and $\mathbf{a}$ are the particle's position, velocity, and acceleration measured in that rotating frame. The vector $\mathbf{g}$ is the gravitational acceleration due to the actual gravitational force, expressed in the same axes; it excludes the separate centrifugal acceleration. The remaining term $-2\mathbf{\omega }\times \mathbf{v}$ is the Coriolis acceleration. A constant rotation axis and an unaccelerated Earth-centred origin account for the absence of an Euler term or a translational-origin term.

For the size estimates, Earth's angular speed isWith drop height $H=20\mathrm{m}$, unperturbed free fall gives the fall timeand final speed $gT=20{\mathrm{m}\mathrm{s}}^{-1}$. Thus the gravitational term has size $10{\mathrm{m}\mathrm{s}}^{-2}$, the Coriolis acceleration is at most about $2\omega gT\approx 2.8\times 10^{-3}{\mathrm{m}\mathrm{s}}^{-2}$, and the centrifugal acceleration is at most ${\omega }^2{R}_0\approx 2.9\times 10^{-2}{\mathrm{m}\mathrm{s}}^{-2}$. These are characteristic sizes $10^1$, $10^{-3}$, and $10^{-2}$ in acceleration units; geometric factors can reduce them, and the Coriolis term is zero at release.

For a suitable approximation to the rotational deflection of a falling body, take $\mathbf{g}$ constant over the short fall, start at rest relative to Earth, and use the zeroth-order velocity ${\mathbf{v}}^{(0)}(t)=\mathbf{g}t$ inside the small Coriolis term. In the centrifugal term replace $\mathbf{r}$ by ${\mathbf{R}}_0$, because $H/R_0\ll 1$. Integrating the resulting acceleration twice, with initial position ${\mathbf{r}}_{\mathrm{i}}$, givesSince ${\mathbf{r}}_{\mathrm{i}}+\mathbf{g}{T}^2/2={\mathbf{R}}_0$, evaluating at the unperturbed fall time yields the printed first-iterate estimate

The approximation keeps the leading Coriolis contribution and the leading centrifugal contribution enhanced by Earth's large radius. Feeding the Coriolis velocity correction back into the equation produces terms of size ${\omega }^{2}g{T}^4$, smaller than the retained centrifugal displacement by a factor of order $H/R_0$. Replacing $\mathbf{r}$ by ${\mathbf{R}}_0$ in that term has the same relative error. Here $\omega T\approx 1.4\times 10^{-4}$ and $H/R_0\approx 3.3\times 10^{-6}$, so both approximations are well controlled. Strictly, the displayed vector is the position at time $T$: its small upward component is removed by the slightly longer actual fall time. That arrival-time correction changes the retained horizontal displacements only at higher order. Thus the horizontal components of the printed estimate give the landing point on the locally flat surface; its vertical component should not be interpreted as a landing above the ground.

Let ${\hat{\mathbf{e}}}_E,{\hat{\mathbf{e}}}_N,{\hat{\mathbf{e}}}_U$ point east, north, and vertically upwards. They form a right-handed basis, with ${\hat{\mathbf{e}}}_N\times {\hat{\mathbf{e}}}_U={\hat{\mathbf{e}}}_E$. At latitude $\lambda$, in the spherical-Earth approximation,The required cross products areAt $\lambda =45^{\circ }$, the northerly and easterly displacements are thereforeThe negative northerly component means a southward displacement. With the supplied values, these are approximately $2.9\mathrm{cm}$ south and $1.3\mathrm{mm}$ east. The eastward effect comes from Coriolis acceleration, while the leading southward effect here comes from centrifugal acceleration.