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

False. Take $A=\{0\}$ and $B=C=\{0,1\}$, with $f(0)=0$ and $g={\mathrm{id}}_B$. Then $f$ is an injection and $g$ is a surjection, but the function composition $g\circ f$ has image of a function $\{0\}$, so it is not a surjection onto $C$.

True. The function composition $j=g\circ f$ is an injection: $j(a)=j(a^{\prime })$ first implies $f(a)=f(a^{\prime })$ by the injectivity of $g$, then $a=a^{\prime }$ by the injectivity of $f$. Fix one $a_0\in A$, using the given nonemptiness, and defineThe first case is well defined because $j$ is an injection. For every $a\in A$, $h(j(a))=a$. Thus this left inverse satisfies $\boxed{h\circ g\circ f={\mathrm{id}}_A}$, the identity function on $A$.

False. Take $A=\{0,1\}$, $B=\{0\}$ and the constant function $f(a)=0$. For the subsets $X=\{0\}$ and $Y=\{1\}$, the intersection $X\cap Y$ is empty, so $f(X\cap Y)=\varnothing$, whereas the intersection of their images of a function is $f(X)\cap f(Y)=\{0\}$. In general the inclusion $f(X\cap Y)\subseteq f(X)\cap f(Y)$ holds, but a common image value can arise from different points of $X$ and $Y$.

True. For each $a\in A$, the definition of preimage givesThus $\boxed{f^{-1}(Z\cap W)=f^{-1}(Z)\cap f^{-1}(W)}$. Unlike the corresponding statement for images of a function, this intersection identity requires no injectivity.

The equivalence class of $x\in X$ is $[x]=\{y\in X:y\sim x\}$. By the reflexivity of the equivalence relation, $x\in [x]$, so every equivalence class is nonempty and their union is $X$.

Suppose $[x]\cap [z]\ne \varnothing$, and choose $w$ in this intersection. We have $w\sim x$ and $w\sim z$. Symmetry and transitivity give $x\sim z$. If $y\in [x]$, then $y\sim x\sim z$, so $y\in [z]$; interchanging $x,z$ proves the reverse inclusion. Thus two equivalence classes are either identical or disjoint. The distinct equivalence classes therefore form a set partition of $X$. This also covers $X=\varnothing$, whose family of equivalence classes is empty.

For positive integers, $m/m=2^0$, establishing reflexivity. If $m/n=2^k$, then $n/m=2^{-k}$, establishing symmetry. If also $n/\ell =2^j$, then $m/\ell =2^{k+j}$, establishing transitivity. Hence this is an equivalence relation.

Every positive integer can be written uniquely as $m=2^{r}d$, where $r\ge 0$ is an integer and $d$ is an odd positive integer, its odd part of a positive integer. Existence follows by repeatedly dividing by two while the result is even; the process terminates because the positive integers strictly decrease. For uniqueness, $2^{r}d=2^{s}e$ with $d,e$ odd would make one of $d,e$ even if $r\ne s$; therefore $r=s$ and $d=e$.

Multiplying by a power of two preserves the odd part of a positive integer, and two positive integers with the same odd part have ratio a power of two. The equivalence class indexed by odd $d$ is consequently $\{2^{r}d:r\ge 0\}$. The required representative set is $\boxed{A=\{1,3,5,\dots \}}$.

Put $M=m_1+m_2$ and let $\mathbf{R}=(m_1{\mathbf{r}}_1+m_2{\mathbf{r}}_2)/M$ be the center of mass. Applying Newton's second law separately to the two point masses givesThus the center of mass has constant velocity, $\mathbf{R}(t)=\mathbf{R}(0)+t\dot{\mathbf{R}}(0)$. For the relative position $\mathbf{r}={\mathbf{r}}_1-{\mathbf{r}}_2$, subtraction givesHere $\mu$ is the reduced mass; it converts the relative motion into a one-body equation of motion.

For the given linear force, the relative position obeys simple harmonic motion, $\ddot{\mathbf{r}}+{\Omega }^2\mathbf{r}=0$, where ${\Omega }^2=k/\mu$. The initial rest condition givesFor $d>0$, collision first occurs when the relative position vanishes, namely when $\Omega t=\pi /2$. ThereforeThe separation $d$ cancels because the frequency of this simple harmonic motion is independent of its amplitude.

Introduce $v=\dot{x}$. The phase plane system for the damped pendulum isAt an equilibrium point, $v=0$ and $\sin x=0$, so all equilibrium points are $\boxed{(x,v)=(n\pi ,0),n\in \mathbb{Z}}$. Angles identified modulo $2\pi$ give one downward and one upward equilibrium point.

The linearization of a dynamical system at $(n\pi ,0)$ has Jacobian matrix and eigenvaluesWhen $n$ is even and $k>\omega$, both eigenvalues are real and strictly negative, since $0<\sqrt{k^2-{\omega }^2}<k$. These downward equilibrium points are stable nodes. When $n$ is even and $k<\omega$, the eigenvalues are $-k\pm i\sqrt{{\omega }^2-k^2}$, so the downward equilibrium points are stable foci, approached with decaying oscillations.

When $n$ is odd, $\sqrt{k^2+{\omega }^2}>k$, so one eigenvalue is positive and one is negative in either parameter range. Every upward equilibrium point is consequently an unstable saddle equilibrium. All these equilibrium points are hyperbolic equilibria in the two requested cases, so their linearization of a dynamical system gives their local nonlinear classification.

A set is countable if it admits an injection into the natural numbers; this includes finite sets and the empty set. Use ${\mathbb{N}}_0=\{0,1,2,\dots \}$ for the enumeration. The Cantor pairing functionis a bijection ${\mathbb{N}}_0^2\to {\mathbb{N}}_0$. Indeed, on the diagonal $i+j=s$, its values are the consecutive integers from $s(s+1)/2$ through $s(s+1)/2+s$. These intervals are disjoint, and the next starts one beyond the preceding endpoint. Every nonnegative integer therefore determines exactly one diagonal $s$, then exactly one $j$, and finally $i=s-j$. If one's convention starts the natural numbers at one, translate both coordinates by one. Thus $\mathbb{N}\times \mathbb{N}$ is a countable set.

For countable sets $X,Y$, choose injections $e_X:X\to {\mathbb{N}}_0$ and $e_Y:Y\to {\mathbb{N}}_0$. The map $(x,y)\mapsto \Pi (e_X(x),e_Y(y))$ is an injection, proving their Cartesian product is countable. Repeating this proves that every finite Cartesian power of a countable set is countable.

For a sequence of countable sets $X_n$, choose an injection $e_n:X_n\to {\mathbb{N}}_0$ for each $n$. For $x\in {\bigcup }_n{X}_n$, let $n(x)$ be the least index containing $x$. The mapis an injection: its value recovers $n(x)$ and then $x$. This proves the countable union of countable sets theorem. Selecting all $e_n$ uses the usual axiom of countable choice; if enumerations are already supplied, the construction itself needs no additional choices.

For a countable set $A$, the polynomials of polynomial degree at most $d$ with coefficients in $A$ are described by coefficient tuples in $A^{d+1}$. The finite Cartesian power of a countable set result makes this a countable set. Taking the union over $d\ge 0$ shows there are only countably many such polynomials altogether; restricting to the nonzero polynomials preserves countability.

A nonzero polynomial of polynomial degree $d$ has at most $d$ distinct roots of a polynomial. To see the bound, a root $r$ gives the factorization $P(x)=(x-r)Q(x)$ by the factor theorem, and each other root is a root of $Q$, whose degree is $d-1$; induction starts with a nonzero constant, which has no roots. Thus $\varphi (A)$ is a countable union of countable sets, each of them finite, and is a countable set.

Starting with the given countable set $A_0$, mathematical induction now shows that every $A_n=\varphi (A_{n-1})$ is countable. A final application of the countable union of countable sets theorem givesThis countability argument does not require that the sequence of sets be increasing.

To obtain a countable closure under real polynomial roots, start with $B_0=\{1,\pi \}$ and explicitly retain previous elements at each stage:Part (b) shows that $\varphi$ takes countable sets to countable sets; consequently all $B_n$ and then $X$ are countable by the countable union of countable sets theorem. Also $1,\pi \in X$.

For a nonzero polynomial $P(t)=c_0+\cdots +c_d{t}^d$ with all $c_j\in X$, choose stages $n_j$ containing the finitely many coefficients and put $N={\max }_j{n}_j$. The inclusions $B_n\subseteq B_{n+1}$ ensure that every coefficient belongs to $B_N$. Every real root of a polynomial $P$ therefore belongs to $\varphi (B_N)\subseteq B_{N+1}\subseteq X$. This countable set $X$ has all the required properties. Retaining $B_n$ explicitly avoids assuming the generally false inclusion $A\subseteq \varphi (A)$: for example, $\varphi (\{1\})$ does not contain $1$, since a nonzero polynomial all of whose coefficients are one is positive at $1$.

Let $d=\gcd (a,m)$. If the linear congruence $ar\equiv b(\mathrm{mod}m)$ holds, then $b=ar-ms$ for some integer $s$, so the greatest common divisor $d$ divides $b$. Conversely, Bézout's identity gives integers $u,v$ with $au+mv=d$. If $b=dj$, multiply this identity by $j$ to obtain $a(uj)\equiv b(\mathrm{mod}m)$. HenceFor the number of solutions, write $a=d{a}^{\prime }$, $m=d{m}^{\prime }$ and $b=d{b}^{\prime }$. The linear congruence becomes $a^{\prime }r\equiv b^{\prime }(\mathrm{mod}{m}^{\prime })$, where $a^{\prime },m^{\prime }$ are coprime integers. Multiplication by $a^{\prime }$ is invertible modulo $m^{\prime }$ by Bézout's identity, so the solutions form one residue class $r\equiv r_0(\mathrm{mod}{m}^{\prime })$. Modulo $m=d{m}^{\prime }$, these are exactlyThey are distinct: if two have the same residue class modulo $m$, then $d{m}^{\prime }$ divides $(j-\ell )m^{\prime }$, forcing $d\mid j-\ell$; with $0\le j,\ell <d$, this forces $j=\ell$. Every other solution differs from $r_0$ by a multiple of $m^{\prime }$, so these exhaust the $d$ solutions.

Finally,Combining this with the existence criterion gives the requested equivalent modular congruence.

Take a generator $u$ of the multiplicative group of a finite field ${\mathbb{F}}_p^{\times }$, which has order $p-1$. Write $x=u^a$. Since any possible nonzero base is $y=u^r$, the condition of being a $k$th power isBy part (a), this linear congruence is soluble exactly when $d=\gcd (k,p-1)$ divides $a$. MeanwhileThus the required test isThe exponent residue classes divisible by $d$ are $0,d,\dots ,p-1-d$, so there are exactly $(p-1)/d$ distinct nonzero $k$th powers. Equivalently, part (a) shows each value has exactly $d$ preimages under the power map.

The greatest common divisor issince $19$ and $44$ are coprime integers. Part (b) therefore gives $\boxed{1012/23=44}$ distinct $437$th powers in the nonzero multiplicative group of a finite field ${\mathbb{F}}_{1013}^{\times }$. If “powers mod $1013$” includes all residue classes, the additional value $0=0^{437}$ gives $\boxed{45}$ values including zero. The distinction is relevant because part (b) explicitly works in the nonzero group.

Suppose $x^2+y^2=0$ in the field $F$. If $y\ne 0$, division by $y^2$ gives $(x/y{)}^2=-1$, contrary to the hypothesis. Hence $y=0$ and then $x^2=0$; the absence of nonzero zero divisors in a field gives $x=0$. ThereforeFor the stated operations on $F^2$, addition is an abelian group operation: associativity and commutativity hold componentwise, its identity is $(0,0)$, and the negative of $(x,y)$ is $(-x,-y)$.

To check multiplication without omitting associativity, associate to each pair the matrixThis is an injection into the two-by-two matrices over $F$, and direct matrix multiplication givesIt also preserves addition. The associativity and distributivity of matrix multiplication therefore imply the same laws for the pair multiplication. Its formula is symmetric in the pairs, so it is commutative. Its identity is $(1,0)$, which is different from $(0,0)$.

For a nonzero pair, the first result shows that $x^2+y^2\ne 0$. Its multiplicative inverse issince multiplying $(x,y)$ by $(x,-y)$ gives $(x^2+y^2,0)$. This verifies every field axiom, so the given operations make $F^2$ a field. The embedded copy of $F$ is $\{(x,0):x\in F\}$; the element $(0,1)$ has square $(-1,0)$, describing a quadratic extension of $F$.

Suppose $x^2\equiv -1(\mathrm{mod}p)$. Then $x\ne 0$ modulo the prime number $p$, so Fermat's little theorem gives $x^{p-1}\equiv 1(\mathrm{mod}p)$. But $p=4m+3$ makes $(p-1)/2=2m+1$ odd, and thereforeThis contradicts $1\not\equiv -1(\mathrm{mod}p)$, since $p$ is odd. Thus $-1$ is not a quadratic residue modulo $p$. Apply part (a) to the finite field $F={\mathbb{F}}_p$: the pairs $F^2$ with the given operations form a field, and there are $p$ choices for each coordinate, so its cardinality is $\boxed{p^2}$.

The key telescoping series identity isFor the requested mathematical induction, when $n=1$ the proposed sum is $q/(q+1)=1-q!/(q+1)!$. If the identity holds for $n$, adding $c_{n+1}=q!/(q+n)!-q!/(q+n+1)!$ cancels its last term and yields $1-q!/(q+n+1)!$. Thus it holds for every $n\ge 1$. Since $q!/(q+n)!\to 0$ for fixed positive integer $q$, the infinite series has sum $\boxed{1}$.

For the second series, the integral digit condition is $0\le a_n\le n-1$, and in particular $a_1=0$. Its partial sums are increasing and satisfyThus the bounded monotone sequence theorem proves convergence to a real number $S\in [0,1]$. The same telescoping calculation gives, for every $N\ge 1$,If positive digits occur infinitely often, then every tail contains a positive term, so $R_N>0$. If $a_n\le n-2$ occurs infinitely often, then every tail contains a digit smaller than its maximum. Indeed,Consequently the two conditions together give $0<R_N<1$ for every $N$. Were $S=A/B$ a rational number, with positive integer $B$, choose $N\ge B$. Because $B\mid N!$, the number $N!S$ is an integer, as is ${\sum }_{n=1}^N{a}_{n}N!/n!$. Their difference $R_N$ would be an integer strictly between zero and one, a contradiction.

Conversely, if positive digits occur only finitely often, then $S$ is a finite sum of rational numbers. If digits below their maximum occur only finitely often, then $a_n=n-1$ for every $n>N$ for some $N$, givingThese are exactly the two ways the conjunction of infinitude conditions can fail. Hence the irrationality criterion for factorial series is proved in both directions: $S$ is irrational exactly when both kinds of digit occur infinitely often.

During ejection, the remaining mass is $m(t)=m_o+m_w-Qt$, and the water is exhausted at $t_c=m_w/Q$. Consider the momentum of the octopus and the small portion of water expelled during $dt$. Initially it is $mu$. At the end of this interval, the remaining body has mass $m-Qdt$ and velocity $u+du$, while the expelled mass $Qdt$ has laboratory velocity $u-V$, to first order. Hence the total final momentum isThe external impulse from quadratic drag is $-\alpha u^{2}dt$. Equating this to the change in total momentum, and dividing by $dt$, proves the equation of motionThe outgoing water's momentum flux is essential: applying $d(mu)/dt$ to the remaining body alone would omit it.

For dimensional analysis, the independent physical inputs are $m_o,m_w,Q,V,\alpha$, with dimensionsThe scales $m_o$, $m_o/Q$ and $V{m}_o/Q$ fix units of mass, time and length. In these units, the only remaining independent dimensionless variables areFor example, with $s=Qt/m_o$ and $w=u/V$, the equation of motion becomes $(1+\lambda -s)dw/ds=1-\mu w^2$, with $w(0)=0$ and ejection ending at $s=\lambda$. Thus the dimensionless terminal value depends only on $\lambda ,\mu$, proving $u_c=Vf(\lambda ,\mu )$.

For its explicit value, put $m_0=m_o+m_w$ and $U=\sqrt{QV/\alpha }$. The initially stationary solution stays below $U$, since the acceleration vanishes at $U$ and is positive below it. Separation of variables givesThe two integrals yieldThis is constant mass-loss propulsion with quadratic drag. At $t_c$, the remaining mass is $m_o$, givingThus $f(\lambda ,\mu )={\mu }^{-1/2}\tanh (\sqrt{\mu }\log (1+\lambda ))$, verifying the required dimensional form. The limit as drag tends to zero is $V\log (1+\lambda )$, the ordinary rocket equation, while the positive-drag answer is below the terminal velocity $U$.

Multiplying the tangential equation of motion by $r$ givesTherefore $h=r^2\dot{\theta }$ is constant. It is the signed specific angular momentum; reverse the angular orientation if necessary to take $h>0$ for a nonradial orbit. Set $u=1/r$ and denote differentiation with respect to $\theta$ by a prime. ThenSubstitution into the radial equation of motion and division by $-h^2{u}^2$ give the Binet equationIts general solution is $u=GM/h^2+A\cos \theta +B\sin \theta$. Write $A=(GM/h^2)e\cos {\theta }_0$ and $B=(GM/h^2)e\sin {\theta }_0$, where $e\ge 0$. This produces the Kepler orbitHere $e$ is the orbital eccentricity, and ${\theta }_0$ points toward periapsis when $e>0$. Only portions with $u>0$ describe positive radial distances. The expression assumes $h\ne 0$; a zero-angular momentum trajectory is radial and must be treated separately.

Choose the gravitational potential energy to vanish at infinity. The total mechanical energy isPut $\gamma =GM/h^2$ and $\phi =\theta -{\theta }_0$. From part (i), $u=\gamma (1+e\cos \phi )$ and $u^{\prime }=-\gamma e\sin \phi$. Consequentlyand the angular terms cancel against the gravitational potential energy:For a nonradial Kepler orbit, negative, zero and positive mechanical energy correspond respectively to $e<1$, $e=1$ and $e>1$.

At infinity, the meteorite's incoming asymptote has speed $V$ and perpendicular distance $b$ from the Earth’s centre. The magnitude of its specific angular momentum is the magnitude of $\mathbf{r}\times \mathbf{v}$. On the asymptote, this is $bV$, so conservation of angular momentum gives $\boxed{h=bV}$. Its mechanical energy at infinity is $E=m{V}^2/2$. Comparing with part (ii) givesFor $b>0$ this Kepler orbit is a hyperbola. The smallest $r=1/u$ occurs at periapsis, where $\cos (\theta -{\theta }_0)=1$. ThusThe middle equality follows by substituting $e^2-1=b^2{V}^4/(G^2{M}^2)$. A trajectory entering the Earth satisfies $r_{\min }<R$, equivalentlyTherefore the sufficient collision condition isThis is gravitational focusing: Newtonian gravity increases the collision radius measured at infinity. Equality is the ideal grazing trajectory, which touches the surface; a strict inequality penetrates it. For $b=0$ the incoming motion is radial and collides, with $r_{\min }=0$ as the limiting value of the above expression.

Let ${\mathbf{e}}_1^{\prime }(t),{\mathbf{e}}_2^{\prime }(t),{\mathbf{e}}_3^{\prime }(t)$ be an orthonormal basis fixed in the rotating reference frame $S^{\prime }$. A small rotation through $\mathbf{\omega }dt$ changes each basis vector by $\mathbf{\omega }\times {\mathbf{e}}_j^{\prime }dt$, so its derivative in the inertial frame isWrite the arbitrary vector as $\mathbf{a}={\sum }_j{a}_j(t){\mathbf{e}}_j^{\prime }(t)$. Differentiating the components and the moving basis separately givesThis proves the rotating-frame derivative formula, including when the angular velocity varies with time.

Use $D=(d/dt{)}_S$, $D^{\prime }=(d/dt{)}_{S^{\prime }}$, and ${\mathbf{v}}^{\prime }=D^{\prime }\mathbf{r}$. By the rotating-frame derivative formula, $D\mathbf{r}={\mathbf{v}}^{\prime }+\mathbf{\omega }\times \mathbf{r}$. Apply the product rule for the cross product and the same rotating-frame derivative formula again:We have $D{\mathbf{v}}^{\prime }=D^{\prime }{\mathbf{v}}^{\prime }+\mathbf{\omega }\times {\mathbf{v}}^{\prime }$ and $D\mathbf{\omega }=D^{\prime }\mathbf{\omega }$, since $\mathbf{\omega }\times \mathbf{\omega }=0$. ThereforeRearranging this identity into an equation of motion in a rotating frame produces the apparent Coriolis acceleration, Euler acceleration and centrifugal acceleration, with signs opposite to their corresponding terms on the right of this inertial acceleration identity. No translational term is needed because the two origins coincide.

Let $\Omega$ be the Earth's angular velocity magnitude. Use the local east, north and upward unit vectors ${\mathbf{e}}_E,{\mathbf{e}}_N,{\mathbf{e}}_U$, with ${\mathbf{e}}_E\times {\mathbf{e}}_N={\mathbf{e}}_U$. At latitude $\lambda$, the Earth's angular velocity and the train's ground-relative velocity areThus the east component of the Coriolis force isFor a north–south track, the train has no eastward acceleration relative to Earth. Its path curvature lies in the local north–vertical plane. The centrifugal acceleration and Newtonian gravity also lie in that plane, and the Earth's constant angular velocity gives no Euler acceleration. Hence the sideways force from the track must cancel the eastward Coriolis force:Its magnitude is $2m\Omega V\sin \lambda$, and its direction is west in the Northern hemisphere. The eastward tendency is the apparent Coriolis force; the requested track force has the opposite direction.

Let $\rho =3m/(4\pi R_0^3)$ be the uniform mass density. In spherical coordinates $(r,\vartheta ,\varphi )$ with the chosen diameter as polar axis, the squared perpendicular distance to that axis is $r^2{\sin }^2\vartheta$. The moment of inertia is thereforeThis derives the moment of inertia of a uniform solid sphere about any central axis by spherical symmetry.

Put $a=R_1-R_0$. The center of mass follows the circle of radius $a$, with position ${\mathbf{r}}_C=a(\sin \theta ,-\cos \theta )$. Let ${\mathbf{e}}_r=(\sin \theta ,-\cos \theta )$ and ${\mathbf{e}}_{\theta }=(\cos \theta ,\sin \theta )$. Its velocity is $a\dot{\theta }{\mathbf{e}}_{\theta }$, and the contact point is displaced from the center of mass by $R_0{\mathbf{e}}_r$. With positive spin angular velocity ${\Omega }_s$ counterclockwise, its contact-point velocity isThe cylinder is fixed, so rolling without slipping requires this velocity to vanish. Consequently ${\Omega }_s=-a\dot{\theta }/R_0$. If instead the spin angle $\psi$ is positive clockwise, opposite to increasing $\theta$, then the printed positive-coefficient convention isThe spin and orbital rotation have opposite directions when both are measured about the same oriented axis; the angular speed is $a|\dot{\theta }|/R_0$. This specifies the sign convention in the printed expression.

The instantaneous contact point is at rest, so the normal reaction and static friction do no work. Conservation of energy equates the loss of gravitational potential energy from release to the total kinetic energy:On the descent from $0<\alpha <\pi /2$, $\theta$ decreases, soIntegrating $dt=-d\theta /|\dot{\theta }|$ from release to the bottom givesThe integral is finite: at the release point its denominator is asymptotic to $\sqrt{\sin \alpha (\alpha -\theta )}$. Contact is maintained, since the inward radial equation of motion gives the positive normal reaction $N=m(g\cos \theta +a{\dot{\theta }}^2)$ throughout this range.

For frictionless sliding, the normal reaction passes through the sphere's centre and produces no torque; Newtonian gravity also exerts no central torque. With initial zero spin, the sphere remains nonrotating. All the lost gravitational potential energy becomes translational kinetic energy, soA hollow spherical shell of the same mass and radius places its material farther from the centre, giving a larger moment of inertia. Under rolling without slipping, a given centre speed therefore requires more rotational kinetic energy; the same gravitational drop yields a smaller speed. Replacing the solid sphere by a hollow shell increases $T_R$ and leaves $T_S$ unchanged. The sliding case remains nonrotating and has the same center of mass path and gravitational drop. This is the general comparison for rolling inside a fixed circular cylinder.