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

Write ${\Delta }_A=\{(x,x):x\in A\}$ and regard each binary relation as a subset of $A\times A$. Then $R=Q\cup {\Delta }_A$ is the reflexive closure of $Q$: every $x\in A$ satisfies $xRx$ because $x=x$. The relation $S=R\cup R^{-1}$ is its symmetric closure. It is a reflexive relation since it contains $R$, and $xSy$ means either $xRy$ or $yRx$, either of which also gives $ySx$.

For $T$, a one-step chain $(x,x)$ is allowed because $xSx$, so $xTx$. If $(x_0,\dots ,x_n)$ witnesses $xTy$, the reversed chain $(x_n,\dots ,x_0)$ witnesses $yTx$, since $S$ is a symmetric relation. Finally, concatenate a chain from $x$ to $y$ with a chain from $y$ to $z$ to obtain a positive-length chain from $x$ to $z$. Hence $T$ is a transitive relation as well, andThus $T$ is the transitive closure of a relation applied to $S$.

Now suppose $E$ is an equivalence relation containing $Q$. Its reflexivity implies ${\Delta }_A\subseteq E$, hence $R\subseteq E$. Its symmetry then implies $R^{-1}\subseteq E$, hence $S\subseteq E$. Along a chain witnessing $xTy$, every consecutive pair is $E$-related. Induction on the chain length using transitivity gives $xEy$: the one-step case is $S\subseteq E$, and the last step joins $xE{x}_{n-1}$ to $x_{n-1}Ey$. ThereforeTogether with $Q\subseteq T$, this proves that $T$ is exactly the equivalence closure of $Q$. The reasoning also covers an empty $A$, where all assertions about elements are vacuous.

Eliminate $x$ by twice the first modular congruence minus three times the second. This givesThe modular inverse of $3$ is $16$, because $3\cdot 16=48\equiv 1$. Hence $y\equiv 16\cdot 13\equiv 20$. Substitution into the second modular congruence gives $6x\equiv 14-7(20)\equiv 15$, and $6^{-1}\equiv 8$, so $x\equiv 8\cdot 15\equiv 26$. ThusIn particular, $(x,y)=(26,20)$ works: $9(26)+12(20)=474=10(47)+4$ and $6(26)+7(20)=296=6(47)+14$. The elimination is reversible because $3$ and $6$ have modular inverses, so the displayed classes contain all solutions.

The integer $137$ is prime: none of the primes $2,3,5,7,11$ below $\sqrt{137}$ divides it. Since $43\not\equiv 0(\mathrm{mod}137)$, Fermat's little theorem gives $43^{136}\equiv 1$. Therefore $43^{135}$ is the modular inverse of $43$. The extended Euclidean algorithm yieldsand back-substitution gives $1=51(43)-16(137)$. ConsequentlyIndeed, $43\cdot 51=2193=16\cdot 137+1$, directly checking the required modular inverse.

Take upward as positive and let $dm<0$ be the change in rocket mass during $dt$. The exhaust emitted has mass $-dm$ and, to first order, upward velocity $v-U$. The linear momentum of the rocket and just-emitted gas changes byThe external gravitational impulse is $-mgdt$ to first order. Applying the momentum balance to this material system, rather than applying a fixed-mass formula to the rocket alone, gives the rocket equationThe term $-U\dot{m}$ is the upward thrust.

For the specified mass loss and exhaust law, $\dot{m}=-\alpha$ andThus the condition for strictly positive upward acceleration at launch isAt equality the initial thrust just balances the weight; under this particular exhaust law the acceleration becomes positive immediately afterwards. If the initial thrust is smaller than the weight and the rocket initially rests on a launch surface, a nonzero supporting force persists until a later lift-off, so the free-flight equation does not describe its earlier supported motion.

For immediate free flight, integrate the rocket equation with $v(0)=0$:This applies while $0\le t<m_0/\alpha$ and the nonrelativistic approximation remains valid. The formal divergence as the model's remaining mass approaches zero is not a prediction within that approximation.

For dimensional analysis, write the mass, length and time dimensions as $\mathsf{M},\mathsf{L},\mathsf{T}$. Then $[m_0]=[m]=\mathsf{M}$, $[\alpha ]=\mathsf{M}{\mathsf{T}}^{-1}$, $[t]=\mathsf{T}$, $[U_0]=[U]=[v]=\mathsf{L}{\mathsf{T}}^{-1}$, and $[g]=\mathsf{L}{\mathsf{T}}^{-2}$. Both $m_0$ and $\alpha t$ have mass dimension, so $\alpha t/(m_0-\alpha t)$ is dimensionless; both terms in the boxed velocity have dimension $\mathsf{L}{\mathsf{T}}^{-1}$. The launch inequality compares two forces, each of dimension $\mathsf{ML}{\mathsf{T}}^{-2}$.

A central force acts along the line joining the particle to a fixed centre. Taking that centre as the origin, its usual position-dependent form isPositive $f$ gives an outward force and negative $f$ an inward one. For a conventional central force the magnitude depends only on distance from the centre, not on direction. The angular-momentum conclusions below require only that the force remain radial about that fixed centre.

The particle's angular momentum about the force centre is $\mathbf{L}=m\mathbf{r}\times \dot{\mathbf{r}}$. A central force exerts zero torque about that centre, soBy conservation of angular momentum, $\mathbf{L}$ is a constant vector. If it is nonzero, the identity $\mathbf{r}\cdot \mathbf{L}=0$ places every point of the orbit in the fixed plane through the centre perpendicular to $\mathbf{L}$:If $\mathbf{L}=0$, position and velocity are parallel. Away from the force centre, ${\dot{\mathbf{e}}}_r=(\dot{\mathbf{r}}-\dot{r}{\mathbf{e}}_r)/r=0$, so the motion is radial along a fixed line, which lies in any plane containing that line. Thus the zero-angular-momentum case also gives planar motion. As usual, these assertions apply while the force law supplies a regular orbit; continuation through a singular force centre is a separate issue.

With the Sun fixed, its gravitational force on the planet is a central force. In the fixed orbital plane, the transverse acceleration in polar coordinates therefore vanishes:During $dt$, the position vector sweeps an infinitesimal sector of area $dA=\frac{1}{2}{r}^{2}d\theta$. Hence the areal velocity isIntegrating over any two equal time intervals gives equal swept areas, proving Kepler's second law. Here $L$ is the signed component of angular momentum normal to the orbital plane. The argument uses conservation of angular momentum; an inverse-square dependence is not needed for this particular law, only a central force.

A left inverse of $f$ is a function $\ell :B\to A$ satisfying $\ell \circ f={\mathrm{id}}_A$. If such $\ell$ exists and $f(a)=f(a^{\prime })$, applying $\ell$ gives $a=a^{\prime }$, so $f$ is an injection. Conversely, suppose $f$ is an injection and fix $a_0\in A$, possible because $A$ is nonempty. DefineThe first value is unique by injectivity, and $\ell (f(a))=a$ for every $a$. ThusNo choice from a family of nonempty sets is needed here: each preimage in the first case is unique, and the second case uses one fixed element.

A right inverse is a function $r:B\to A$ with $f\circ r={\mathrm{id}}_B$. Its existence makes every $b$ the image of $r(b)$, proving that $f$ is a surjection. Conversely, if $f$ is a surjection, every fiber of a function $f^{-1}(\{b\})$ is nonempty. Using the usual axiom of choice for arbitrary sets, choose $r(b)\in f^{-1}(\{b\})$ for each $b$. Then $f(r(b))=b$, givingThe converse in this second equivalence is the right-inverse characterization of the axiom of choice; it is not an unrestricted choice-free theorem about arbitrary sets.

Choose a right inverse $s:A\to B$ of the surjection $f$, so $f(s(a))=a$, and defineFor each $a$, the element $b=s(a)$ then witnesses both $f(b)=a$ and $g(b)=h(a)$. As in part (a), arbitrary simultaneous choices use the axiom of choice. If $A$ is empty, surjectivity and the existence of $f:B\to A$ force $B$ to be empty, and the unique empty function $h:A\to C$ already meets the requirement.

Suppose $g$ is constant on each fiber of a function of $f$. Since every fiber is nonempty, $h(a)$ must be its common $g$-value: any witness $b$ in that fiber gives that value. This defines exactly one $h$ and yields $g=h\circ f$, an instance of factorization through a surjection.

Conversely, suppose a fiber contains $b,b^{\prime }$ with $f(b)=f(b^{\prime })=a_0$ but $g(b)\ne g(b^{\prime })$. Starting with any admissible $h$, define $h_1,h_2$ to agree with it away from $a_0$, but put $h_1(a_0)=g(b)$ and $h_2(a_0)=g(b^{\prime })$. Both remain admissible, witnessed at $a_0$ by $b$ and $b^{\prime }$ respectively, yet they are distinct. HenceThe distinction is important: the original existence property asks only for one witness in each fiber. Only when $g$ is fiberwise constant does that property force $g=h\circ f$ for every $b$.

For finite sets $X_1,\dots ,X_N$, the inclusion-exclusion principle statesTo prove it, fix an element belonging to exactly $s\ge 1$ of these sets. At level $r$ it is counted in precisely $\left(\genfrac{}{}{0ex}{}{s}{r}\right)$ intersections, so its total multiplicity on the right isby the binomial theorem. An element in no set contributes zero. Summing these equal multiplicities over the finite union proves inclusion-exclusion. This also explains why pairwise subtraction alone is insufficient: elements in triple and higher intersections must receive the alternating corrections.

Use the universe $\Omega =\{B\subseteq A:|B|=k\}$ and define the exact-occupancy events $E_i=\{B\in \Omega :|B\cap A_i|=3\}$. The desired collection is ${\bigcup }_{i=1}^k{E}_i$, so apply inclusion-exclusion to these events.

Fix $r$ distinct block indices. For $B$ to belong to the intersection of their events, it must contain exactly three elements in each selected block. There are ${\left(\genfrac{}{}{0ex}{}{m}{3}\right)}^r$ ways to make those choices. None of the other elements in these selected blocks may be included; the remaining $k-3r$ elements must come from the $n-rm$ elements outside the selected blocks. ThusThere are $\left(\genfrac{}{}{0ex}{}{k}{r}\right)$ choices of block indices, and the intersection is empty when $3r>k$. Substitution into inclusion-exclusion givesHere binomial coefficients with a lower argument exceeding a nonnegative upper argument are zero. In particular, when $m<3$ every event is empty, and when $k<3$ the sum is empty; both give the correct answer zero. The subtraction of entire selected blocks, not merely the $3r$ chosen elements, is what enforces exact rather than at-least-three occupancy. This is inclusion-exclusion for exact block occupancy with the number of blocks and subset size both equal to $k$.

If $A$ is nonempty, take $a\in A$. The stated implication repeatedly gives $a+jt\in A$ for $j=0,1,\dots ,p-1$. These residues are all distinct: equality of two would give $(j-\ell )t=0$ in the prime field ${\mathbb{Z}}_p$, and the nonzero $t$ can be cancelled. They therefore exhaust the field. ThusEquivalently, a nonzero element generates the additive cyclic group of prime order.

Now assume $0<k<p$. If $A+s=A+t$ with $s\ne t$, translating by $-s$ gives $A=A+(t-s)$, contradicting the preceding result. Hence all $p$ translates are distinct. Translation defines equivalence classes on the collection of all $k$-element subsets: two subsets are equivalent if one is a translate of the other, and each class contains exactly $p$ subsets. Since there are $\left(\genfrac{}{}{0ex}{}{p}{k}\right)$ such subsets, their partition into classes givesThis is the free translation action on nontrivial subsets of a prime cyclic group.

The binomial theorem now gives, in the prime field,Starting with $0^p=0$ and applying this identity successively to the representatives $0,1,\dots ,p-1$ proves $a^p=a$ for every residue $a$. For nonzero $a$, cancellation giveswhich is Fermat's little theorem, or $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$ and $a^{p-1}\equiv 1$ when $p\nmid a$.

The same vanishing of intermediate binomial coefficients proves $(R+S{)}^p=R^p+S^p$ for any commuting elements in a ring whose ring characteristic is $p$, in particular for polynomials over ${\mathbb{Z}}_p$. Applying this repeatedly to the terms of $Q$, and applying Fermat's little theorem to each coefficient, gives the Frobenius endomorphism identityThis is an equality of formal polynomials. It does not assert $x^p=x$ as a polynomial; that latter equality holds only after evaluating at elements of ${\mathbb{Z}}_p$.

Suppose all infinite binary sequences could be listed as ${ϵ}^{(1)},{ϵ}^{(2)},\dots$, where ${ϵ}^{(j)}=({ϵ}_1^{(j)},{ϵ}_2^{(j)},\dots )$. Define another binary sequence by $d_j=1-{ϵ}_j^{(j)}$. It differs from the $j$th listed sequence at its $j$th entry, so it is absent from the list. This contradiction is Cantor's diagonal argument, proving thatTo transfer this result to $[0,1]$, map a binary sequence toThis lies in $[0,1]$ because ${\sum }_{j\ge 1}2/3^j=1$. If two sequences first differ at index $j$, with ${ϵ}_j=1$ and ${\eta }_j=0$, thenThus $f$ is an injection, avoiding the ambiguous expansions that would arise from unrestricted binary digits in base two. An injection from an uncountable set into $[0,1]$ proves that $\boxed{[0,1]\text{ is uncountable}}$.

For $\Sigma (\mathbb{Z})$, a nondecreasing sequence bounded above can take only finitely many integer values, all lying between its first term and an integer upper bound. Every strict increase raises its value by at least one, so only finitely many strict increases occur. It is therefore eventually constant. Every such sequence has the formfor some finite list of integers. The set of finite integer lists is a countable set: at stage $j$, list the tuples of length at most $j$ whose entries have absolute value at most $j$, omitting earlier duplicates. Each stage is finite and every finite tuple occurs at some stage. Constant sequences give an injection of $\mathbb{Z}$ into the collection, soThis is the discrete-order phenomenon that bounded nondecreasing integer sequences are eventually constant.

For $\Sigma (\mathbb{Q})$, use a different encoding, into rational partial sums:Each $s_n$ is a rational number, the sequence is nondecreasing, and $s_n\le 1/2$. If two binary inputs first differ at $j$, their $j$th partial sums differ by $3^{-j}$, so their output sequences differ. This defines an injection of the uncountable binary-sequence set into $\Sigma (\mathbb{Q})$. Thus bounded nondecreasing rational sequences are uncountable. Finally, every such rational sequence is also an admissible real sequence, so inclusion into $\Sigma (\mathbb{R})$ is injective. ConsequentlyBoundedness and monotonicity force eventual constancy for integer values, but not for rational or real values; countability of the set of possible individual terms does not imply countability of all infinite sequences of those terms.

Use signed velocities in Skaro's inertial frame; the returning velocity $w$ must be negative. For the first two rockets, the Lorentz transformation of infinitesimal separations is $dx={\gamma }_u(d{x}^{\prime }+ud{t}^{\prime })$, $dt={\gamma }_u(d{t}^{\prime }+ud{x}^{\prime }/c^2)$. Dividing with $d{x}^{\prime }/d{t}^{\prime }=v^{\prime }$ gives the relativistic velocity-addition formulaFor the third rocket, its signed velocity in the second frame is $-w^{\prime \prime }$, so another application givesSince $0<v<c$ and $0<w^{\prime \prime }<c$, the denominator $1-v{w}^{\prime \prime }/c^2$ is positive. The third rocket returns from positive $x$ to Skaro if and only if $w<0$, henceEquality leaves it stationary in Skaro's frame, so it never returns from $x=2L$; a smaller $w^{\prime \prime }$ leaves it travelling outward.

Let $O$ denote departure, $A$ boarding the second rocket, $B$ boarding the third, and $C$ reunion with Skaro. In coordinates $(t,x)$, their positions on the worldline areIndeed, the first two coordinate durations are $L/u$ and $L/v$, and the returning leg has duration $-2L/w>0$. Equivalently, their $(ct,x)$ coordinates are obtained by multiplying each displayed time by $c$; these are the coordinates used for the spacetime diagram.

The diagram uses representative velocities satisfying the return condition; its event labels apply to the general formulas above. Skaro's elapsed time isOn a constant-velocity leg the traveller's proper time is $\Delta t/{\gamma }_V=\Delta t\sqrt{1-V^2/c^2}$, by time dilation. Neglecting the specified brief accelerations, Davros therefore ages byEvery contribution is positive because $w<0$. Each square-root factor is smaller than one, so $\Delta \tau <T$: Davros returns younger than a companion who remained on Skaro. The elapsed times compare the same departure and reunion events; they cannot be obtained by applying one time-dilation factor to the whole journey, whose worldline has three different velocities.

For $|\mathbf{v}|<c$, define the Lorentz factor $\gamma =(1-|\mathbf{v}{|}^2/c^2{)}^{-1/2}$. A particle of rest mass $m$ hasThese expressions give the relativistic energy-momentum relation directly:so $\boxed{E^2=c^2\mathbf{p}\cdot \mathbf{p}+m^2{c}^4}$.

The four-momentum iswhere $U^{\mu }$ is the four-velocity, the proper-time derivative of $(ct,\mathbf{x})$. It is a four-vector, so its Minkowski metric norm is invariant under Lorentz transformations. Choose metric signature $(+,-,-,-)$; in the particle's rest frame, $P^{\mu }=(mc,0)$ and $P_{\mu }{P}^{\mu }=m^2{c}^2$. In any frame the same norm is $E^2/c^2-|\mathbf{p}{|}^2$. Equating the two yields the same relativistic energy-momentum relation. With the opposite metric convention both norm expressions change sign, leaving the energy relation unchanged.

The two incoming particles have equal energies and opposite momenta, so their total four-momentum in this frame isIt is already a centre-of-momentum frame. By four-momentum conservation, the final spatial momenta sum to zero and their energies sum to $2E$. Each product has energySumming gives the necessary relativistic collision mass thresholdFor massive products the equality threshold has all of them at rest in this frame. Above it, multiple products can carry balancing momenta and relative kinetic energy. The displayed condition is necessary, as requested; a single final particle must instead have exactly the incoming invariant mass, and additional physical conservation laws could further restrict a real reaction.

Let the incoming projectile momentum be ${\mathbf{p}}_1$. The stationary target has four-momentum $(m_{2}c,0)$, so the total incoming norm isHere the relativistic energy-momentum relation eliminated $|{\mathbf{p}}_1{|}^2$. Write $W$ for the total energy in the centre-of-momentum frame; then $W^2=c^2{P}_{\mathrm{in}}^2$. If $M_f={\sum }_i{\mu }_i$, the relativistic collision mass threshold gives $W\ge M_f{c}^2$. Squaring and rearranging with $m_2>0$ yields the fixed-target production thresholdThe actual incident total energy also obeys $E_1\ge m_1{c}^2$. Thus a negative algebraic reaction bound would not allow a negative-energy projectile.

For a photon, $m_1=0$ and $E_1=h\nu$, where $h$ is the Planck constant. The necessary bound becomesIn the usual massive multi-product channel with $M_f>m_2$, conservation alone permits the threshold configuration in which all products are at rest relative to one another in the centre-of-momentum frame. Boosting that configuration supplies the required laboratory momentum. Hence the photon fixed-target production threshold isFor a multi-product channel with $M_f\le m_2$, there is no positive mass threshold: the lower limit of allowed positive frequencies is zero. The compact expression for that lower limit is $\boxed{{\nu }_{\inf }=\max \{0,M_f^2-m_2^2\}{c}^2/(2m_{2}h)}$; it need not correspond to a zero-frequency incident photon.

For completeness, if the only product is one particle of mass ${\mu }_1$, its invariant mass must match exactly. A positive incident frequency is possible only when ${\mu }_1>m_2$, and is then fixed at $\nu =({\mu }_1^2-m_2^2)c^2/(2m_{2}h)$; frequencies above that value do not produce the same single particle while conserving four-momentum. If a multi-product channel includes massless particles, an all-products-at-rest configuration is impossible for those particles with nonzero energy, so the nominal massive threshold may be only an infimum. These qualifications distinguish the requested necessary inequalities from unrestricted claims of sufficiency.

For the complete uniform disc, the surface density is $\sigma =M/(\pi a^2)$. An annular strip of radius $r$ and thickness $dr$ has mass $dm=2\pi \sigma rdr$, so its contribution to the axial moment of inertia is $r^{2}dm$. HenceThis derives the moment of inertia of a uniform disc rather than assuming it.

Removing a concentric disc of radius $a/2$ at the same density removes mass $M/4$ and inertia $\frac{1}{2}(M/4)(a/2{)}^2=M{a}^2/32$. The remaining annulus therefore has mass $m_A=3M/4$ andThe moment of inertia of a uniform annulus gives the same value directly.

Let $A_c$ be the downhill centre-of-mass acceleration and let $F$ denote the magnitude of the uphill static friction. Translation, rotation about the centre, and rolling without slipping giveThus $F=I_A{A}_c/a^2=(5/8)m_A{A}_c$. Eliminating $F$ gives the rolling acceleration with rotational inertiaSubstitution gives the contact forcesThe normal force balances the perpendicular component of gravity because the centre remains at a constant distance from the plane. Although the annulus accelerates downhill, friction must act uphill to supply the torque that increases its rolling angular speed. For a plane with $0\le \alpha <\pi /2$, the assumed no-slip motion requires a coefficient of static friction satisfying ${\mu }_s\ge F/N=(5/13)\tan \alpha$. With that condition, contact friction does no work because the instantaneous contact point is stationary; it redistributes the gravitational energy between translational and rotational kinetic energy.

With no electric field, the Lorentz force isFor nonrelativistic motion, the work-energy theorem givesConsequently $\boxed{K(t)=K(0)}$. The reason is geometric: magnetic forces do no work because they are perpendicular to the instantaneous velocity. They can change its direction but not its magnitude. The same energy conclusion holds relativistically, using $dE/dt=\mathbf{F}\cdot \mathbf{v}$ and subtracting the constant rest energy to obtain kinetic energy.

Place the four fixed charges at $(sa,ta)$ with $s,t\in \{-1,1\}$, and write the moving particle's position as $(x,y)$. Introduce its mass $m>0$, which is needed for an oscillation frequency but is not named in the question. Let $C=Qq/(4\pi {ϵ}_0)>0$. By Coulomb's law and superposition, the moving particle's potential energy isThe electrostatic potential itself is $V/q$. Put $r^2=x^2+y^2$ and ${\delta }_{st}=-(sx+ty)/a+r^2/(2a^2)$. Near the centre, a Taylor expansion givesOn summing over the four corners, linear terms cancel. To quadratic order, $\sum {\delta }_{st}=2r^2/a^2$ and $\sum {\delta }_{st}^2=4r^2/a^2+O(r^4/a^4)$, since $\sum st=0$. Reflection symmetry removes all odd-degree terms. HencewhereThus the centre has zero planar force and a positive-definite planar Hessian matrix $\kappa I_2$. It is a strict local minimum of the constrained potential energy, so it is a stable equilibrium. More explicitly, conservation of the total energy confines sufficiently small-energy motions within a small neighbourhood of this isolated local minimum.

Keeping only the quadratic potential, the two coordinates obey independent small oscillations:Both planar modes have the same angular frequency, and the ordinary frequency isThe planar constraint is essential to this constrained electrostatic equilibrium. Along the perpendicular axis, $V(0,0,z)=4C/(2a^2+z^2{)}^{1/2}=V(0,0)-C{z}^2/(\sqrt{2}{a}^3)+O(z^4)$, so the same stationary point is unstable to unconstrained normal displacements. That also checks the cancellation of the three-dimensional Hessian trace required by Laplace's equation away from charges; it does not contradict the positive-definite restriction to the given plane.