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

This can fail. Let $X=\{1\}$ and $Y=\{a,b\}$, put $f(1)=a$, and let $g(a)=g(b)=1$. Then the function composition $g\circ f$ is the identity function on $X$, hence is a surjective function, although $f$ is not surjective.

Solved by gpt-5.6-sol high.

This is always true. If $f(x_1)=f(x_2)$, thenThe assumed injectivity of $g\circ f$ gives $x_1=x_2$, so $f$ is injective.

Solved by gpt-5.6-sol high.

This can fail in the same example as in part (i): $g\circ f$ is injective on the singleton $X$, but $g(a)=g(b)$.

For the final count, $g\circ f={\mathrm{id}}_X$ forces $f$ to be injective. There aresuch functions $f$. Once $f$ is chosen, $g$ is forced on the $m$ elements of $f(X)$ and has $m$ independent choices at each of the other $n-m$ elements of $Y$. Hence the number of pairs is

Solved by gpt-5.6-sol high.

The Fibonacci recurrence givesThe map $x\mapsto 1+1/x$ is strictly decreasing for $x>0$. Since $a_3=2\ge a_1=1$, applying this decreasing map reverses each inequality and proves by mathematical induction thatTaking even $n$ shows $a_{2n+2}\le a_{2n}$, so $(a_{2n})$ is a decreasing sequence.

Solved by gpt-5.6-sol high.

The stated formula is Cassini's identity. It holds for $n=1$, and the recurrence giveswhich is the negative of the expression at index $n$. This proves the identity by induction.

ConsequentlyThe positive Fibonacci numbers tend to infinity, so this difference tends to zero.

Solved by gpt-5.6-sol high.

Part (i) also shows that the odd subsequence is increasing and the even subsequence is decreasing. Each odd term is below the adjacent even term, so both are bounded monotone sequences and therefore have limits. Part (ii) says their difference tends to zero, so those limits coincide. Interlacing the two subsequences proves that $(a_n)$ has that common limit.

Solved by gpt-5.6-sol high.

Let $M(t)=m_0-\alpha t$ be the trolley's remaining mass. During $dt$, the expelled mass $-dM$ has ground-frame velocity $v+u$. Conservation of momentum gives, to first order,and hence $Mdv=udM$. Integration yields the rocket equationAt the stopping time, $M=m_0{e}^{-v_0/u}$. Therefore the time spent ejecting gas is

Solved by gpt-5.6-sol high.

Writing $x_i=(x_i,y_i,z_i)$, rotation about the $z$-axis gives particle $i$ the speed $\omega \sqrt{x_i^2+y_i^2}$. Its kinetic energy is therefore $m_i{\omega }^2(x_i^2+y_i^2)/2$, soThis is the defining mass sum for the moment of inertia about the $z$-axis.

For the uniform cuboid, the mass density is $\rho =M/(8abc)$ and

Solved by gpt-5.6-sol high.

Define the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ as the number of $r$-element subsets of an $n$-element set, equivalently as $n!/[r!(n-r)!]$. Partitioning the $r$-element subsets of $\{1,\dots ,n+1\}$ according to whether they contain $n+1$ proves Pascal's identityThus the forward difference operator satisfies

Solved by gpt-5.6-sol high.

We use induction on $k$. If $k=0$, then $\delta f=0$, so the integer-valued function $f$ is constant. For $k>0$, the integer-valued function $\delta f$ satisfies ${\delta }^k(\delta f)=0$. By induction it is an integer linear combination ofPart (i) shows that replacing each $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ by $\left(\genfrac{}{}{0ex}{}{n}{r+1}\right)$ gives an integer-valued discrete antiderivative. Subtracting the resulting integer linear combination from $f$ leaves a function with zero forward difference, hence an integer constant. This giveswith every $c_j\in \mathbb{Z}$.

Solved by gpt-5.6-sol high.

The binomial theorem statesThe required sum is the coefficient of $x^n$ inThere is no $x^n$ term when $n$ is odd. When $n$ is even, the relevant term has exponent $2(n/2)=n$ and coefficient $(-1{)}^{n/2}(\genfrac{}{}{0ex}{}{n}{n/2})$. Hence

Solved by gpt-5.6-sol high.

The Euclidean algorithm repeatedly replaces a pair $(a,b)$ by $(b,a-qb)$ without changing its greatest common divisor. Reversing the divisions expresses $\gcd (a,b)$ as an integer linear combination $\alpha a+\beta b$, which is Bézout's identity.

Here $3=3(15)-2(21)$, and thereforeOne solution is $(x,y,z)=(36,-24,-1)$. It is not unique: for every $t\in \mathbb{Z}$, $(x,y,z)=(36+7t,-24-5t,-1)$ is another solution.

Solved by gpt-5.6-sol high.

Because $\gcd (m,n)=1$, choose $u,v\in \mathbb{Z}$ with $um+vn=1$ by Bézout's identity. Thensatisfies $c\equiv a(\mathrm{mod}m)$ and $c\equiv b(\mathrm{mod}n)$. Any two simultaneous solutions differ by a multiple of both coprime integers and hence by a multiple of $mn$. This proves the two-modulus Chinese remainder theorem.

The three congruences reduce toThe first two give $x\equiv 17(\mathrm{mod}35)$; imposing the last gives

Solved by gpt-5.6-sol high.

The inclusion-exclusion principle says that the size of a finite union is the alternating sum of the sizes of all nonempty intersections of its constituent sets.

For each prime number $p\mid n$, let $A_p$ consist of the tuples for which $p$ divides every $x_i$. Exactly $(n/p{)}^r$ tuples lie in $A_p$, and for distinct primes $p_1,\dots ,p_j\mid n$, exactly $(n/(p_1\cdots p_j){)}^r$ lie in their intersection. A tuple has greatest common divisor greater than one with $n$ exactly when it belongs to some $A_p$. Inclusion-exclusion therefore gives the Jordan totient function

Solved by gpt-5.6-sol high.

This is an infinite binary expansion with digits in $\{0,1\}$. If the usual expansion of $\alpha$ has infinitely many $1$ digits, list their positions as $b_1<b_2<\cdots$. If it terminates with a final term $2^{-k}$, replace that term bythis also covers every dyadic rational. For $\alpha =1$, use $b_n=n$. Thus every $\alpha \in (0,1]$ has the required form.

The representation by an infinite strictly increasing sequence is unique. If two sequences first differ at exponent $k$, one sum contains $2^{-k}$ and the other does not. The latter's entire possible tail is at most ${\sum }_{j>k}{2}^{-j}=2^{-k}$, while the former has $2^{-k}$ plus its own nonempty tail, so the sums cannot agree.

Solved by gpt-5.6-sol high.

For $M=\max \{|s|,|t|,1\}$, factorization of a difference of powers givesConsequently the polynomial $f$ obeys the Lipschitz bound

Solved by gpt-5.6-sol high.

Since $p/q$ is not a root, $q^{d}f(p/q)$ is a nonzero integer, and henceMoreover $0<\theta -p/q<1$ implies $|p/q|<|\theta |+1$. Applying part (i) to $s=\theta$, $t=p/q$, and using $f(\theta )=0$ givesRearrangement provesThis is the core estimate behind the Liouville approximation theorem.

Solved by gpt-5.6-sol high.

LetThe tail satisfiesFor every fixed positive integer $d$, this is smaller than $q_N^{-d}$ for all sufficiently large $N$.

The binary expansion has $1$ digits at factorial positions and arbitrarily long blocks of zeros, but it is neither eventually zero nor eventually periodic. Since a rational number has an eventually periodic binary expansion, $\alpha$ is irrational. If it were an algebraic number of degree $d$, part (b), or equivalently the Liouville approximation theorem, would give a fixed positive multiple of $q^{-d}$ as a lower bound for all rational approximations. The fractions $p_N/q_N$ violate that bound. Thus $\alpha$ is a transcendental number.

Solved by gpt-5.6-sol high.

This can be false. For any nonzero transcendental number $\beta$, the number $\gamma =1/\beta$ is also transcendental, since otherwise its reciprocal would be algebraic. Yet $\beta \gamma =1$ is algebraic.

Solved by gpt-5.6-sol high.

This is always true for every positive integer $n$. If ${\beta }^n$ were algebraic, then $\beta$ would be a root of the polynomial $X^n-{\beta }^n$ over the field of algebraic numbers. By transitivity of algebraic extensions, $\beta$ would then be algebraic over $\mathbb{Q}$, contradicting its transcendence.

Solved by gpt-5.6-sol high.

Write the sets as $A_1,A_2,\dots$, and list each nonempty countable set as $A_i=\{a_{i1},a_{i2},\dots \}$. Enumerate the pairs $(i,j)\in {\mathbb{N}}^2$ along successive diagonals, as in the Cantor pairing function, and output $a_{ij}$ when it has not appeared before. Every member of ${\bigcup }_i{A}_i$ eventually appears, proving that a countable union of countable sets is countable.

Solved by gpt-5.6-sol high.

Suppose all functions $\mathbb{N}\to \mathbb{N}$ could be listed as $f_1,f_2,\dots$. DefineThen $g$ differs from $f_n$ at $n$ for every $n$, so it is absent from the list. This Cantor's diagonal argument proves that ${\mathbb{N}}^{\mathbb{N}}$ is an uncountable set.

Solved by gpt-5.6-sol high.

$A$ is uncountable. For each binary sequence $({\epsilon }_j)$, defineThis is a nondecreasing function, and different binary sequences give different functions, so the uncountable set of binary sequences injects into $A$.

$B$ is countable. Every nonincreasing sequence of positive integers can decrease only finitely many times and is therefore eventually constant. Such a sequence is specified by a finite sequence of positive integers, and the set of all finite integer sequences is a countable union of countable sets. Hence $B$ is countable.

Solved by gpt-5.6-sol high.

For each $N$, only finitely many permutations fix every $j>N$: they are precisely the permutations of $\{1,\dots ,N\}$. Thusis a countable union of finite sets and is countable.

Solved by gpt-5.6-sol high.

For every binary sequence $({\epsilon }_n)$, independently fix the pair $(2n-1,2n)$ when ${\epsilon }_n=0$ and swap its two entries when ${\epsilon }_n=1$. The resulting map is a permutation with $|\sigma (j)-j|\le 1$, and different binary sequences produce different permutations. Therefore $D$ is uncountable.

In fact these are all the possibilities: if $\sigma (j)=j+1$, bijectivity and the displacement bound force $\sigma (j+1)=j$, while a point not in such an adjacent transposition is fixed.

Solved by gpt-5.6-sol high.

The work done along the trajectory isBy Newton's second law, $F=m\ddot{x}$, soThis is the work-energy theorem: the work equals the change in kinetic energy.

A force is conservative when its work between two points is independent of the path, equivalently when it is the negative gradient of a potential energy. Here a potential with $V(0)=0$ isConservation of energy for $x>0$ givesThus

If $v_0>v_e$, the particle escapes with asymptotic speed $\sqrt{v_0^2-v_e^2}$; the graph decreases from $v_0$ to this horizontal asymptote. At the escape velocity $v_0=v_e$, it decreases as $v_e{e}^{-x/(2\lambda )}$ and approaches zero only at infinity. If $v_0<v_e$, it reaches the turning pointwhere $v=0$, then returns on the negative branch of the same curve and oscillates symmetrically about the origin.

For oscillation put $w=1-v_0^2/v_e^2$. One quarter of the period iswhere $u=e^{-x/\lambda }$. Therefore

Solved by gpt-5.6-sol high.

The torque about the origin isSince $\dot{L}=\tau$, the angular momentum $L=mr\times \dot{r}$ is conserved. The force is the negative gradient of the inverse-square potentialso the conserved energy isDirectly, $\dot{E}=\dot{r}\cdot (m\ddot{r}+kmr/r^3)=0$.

Solved by gpt-5.6-sol high.

Motion under a central force is planar. In plane polar coordinates, the radial component of the acceleration is $\ddot{r}-r{\dot{\theta }}^2$, soThe conserved specific angular momentum is $h=r^2\dot{\theta }$. Substitution of $\dot{\theta }=h/r^2$ yieldsThe last term is the centrifugal part of the radial effective potential.

Solved by gpt-5.6-sol high.

At the periapsis $r_1$ and apoapsis $r_2$, the given Kepler orbit satisfiesHenceTherefore

Solved by gpt-5.6-sol high.

A circular orbit of radius $r$ has speed $v_c(r)=\sqrt{k/r}$. On the transfer ellipse, the velocity is tangential at both apsides and has magnitude $h/r$. The first prograde burst therefore changes the speed byAt $r_2$ the satellite must again accelerate in the direction of motion to circularize, byThese are the two impulses of a Hohmann transfer.

Solved by gpt-5.6-sol high.

The transfer ellipse has semi-major axis and semi-minor axisConservation of angular momentum gives constant areal velocity $h/2$. The satellite sweeps half the ellipse, whose area is $\pi ab/2$, soUsing part (i),This is half the orbital period from Kepler's third law.

Solved by gpt-5.6-sol high.

Let $e_i^{\prime }(t)$ be a Cartesian basis fixed in the rotating frame. A vector $A=A_i^{\prime }{e}_i^{\prime }$ then satisfiesbecause a derivative of a body-fixed basis vector is ${\dot{e}}_i^{\prime }=\omega \times e_i^{\prime }$. Applying this transport formula twice to $r$ gives, for constant $\omega$,The second and third terms correspond to Coriolis acceleration and centrifugal acceleration in the rotating description.

For the bead, use cylindrical unit vectors $(e_r,e_{\varphi },e_z)$ with $e_z$ upward andProjection of $m\ddot{r}=-mg{e}_z+N$ along the wire tangent $\cos \theta e_r+\sin \theta e_z$ eliminates the smooth-wire normal force $N$ and gives

Solved by gpt-5.6-sol high.

The downward and upward positions $\theta =0,\pi$ are equilibria. Linearization about $\theta =0$ givesso the downward equilibrium is stable for ${\omega }^2<g/R$ and unstable for ${\omega }^2>g/R$; at equality it is marginal at linear order. At $\theta =\pi$, the linear coefficient is ${\omega }^2+g/R>0$, so the upward equilibrium is unstable.

When ${\omega }^2\ge g/R$, there are also the two equilibriaAt either nonvertical equilibrium, differentiation of the right-hand side gives $-{\omega }^2{\sin }^2\theta <0$, so both are stable when distinct. This is a pitchfork bifurcation of a rotating hoop bead at ${\omega }^2=g/R$.

Solved by gpt-5.6-sol high.

The inertial acceleration obtained by differentiating the position used in part (i) isSince $N=m\ddot{r}+mg{e}_z$, substitution of the equation of motion gives the wire's force on the bead asThe first component is normal to the circle within its plane; the second is perpendicular to the rotating plane.

Solved by gpt-5.6-sol high.

With Lorentz factor $\gamma =(1-v^2/c^2{)}^{-1/2}$, the relativistic momentum and four-momentum areThe Newtonian formula $a=F/m$ fails because $p$ is not $mv$: both the magnitude and direction of $v$ affect $dp/dt$. Sincethe relativistic force isTaking the dot product with $v$ gives $F\cdot v=m{\gamma }^{3}v\cdot a$, and substitution yields the inverse relationThis is the requested sum of a vector parallel to $F$ and one parallel to $v$.

In the constant electric field, $dp/dt=qE$ and the particle starts with $p(0)=0$, so $p=qEt$. The relativistic energy-momentum relation impliesThus the speed increases monotonically but remains subluminal, and $v$ tends to $c$ in the direction of $qE$ as $t\to \infty$.

Solved by gpt-5.6-sol high.