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

DefineThis is an involution on permutations. Every inequality is reversed, so it maps up-down permutations bijectively to down-up permutations.

Solved by gpt-5.6-sol high.

By part (a), there are $A_{n+1}$ permutations of each alternating type. In an up-down permutation the maximum $n+1$ can occur only at a peak, while in a down-up permutation it can occur only at the complementary positions. Thus, after combining the two types, each possible number $k$ of entries to the left of the maximum occurs once.

Choose those $k$ labels in $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways. The entries on the two sides must independently alternate, and after order-preserving relabelling can be chosen in $A_k$ and $A_{n-k}$ ways. This alternating-permutation convolution is

Solved by gpt-5.6-sol high.

The Chinese remainder theorem says that for pairwise coprime positive integers $m_i$, the mapis a bijection. For two moduli, choose $u,v$ with $um+vn=1$; thenhas residues $a$ modulo $m$ and $b$ modulo $n$. Uniqueness follows because the difference of two solutions is divisible by both coprime moduli, hence by their product. Induction proves the general case.

The two given congruences are compatible modulo $\gcd (6,8)=2$, and checking modulo $\mathrm{lcm}(6,8)=24$ gives

Write $d=2^r{3}^{s}m$ with $(m,6)=1$. Use the Chinese remainder theorem to chooseThen $4a^2+9b^2\equiv 1$ modulo each of the pairwise coprime factors $2^r$, $3^s$, and $m$, hence modulo $d$.

Solved by gpt-5.6-sol high.

During a short time $dt$, the rocket loses mass $-dm>0$. Conservation of upward momentum, including gravity's impulse and exhaust velocity $v-U$, gives to first orderwhich is the stated rocket equation.

Here $dm/dt=-\alpha$ and $U=U_0{m}_0/m$, soLift-off from rest requires positive initial acceleration,With $v(0)=0$, integration givesThe dimensions are $[m_0]=[m]=M$, $[\alpha ]=M/T$, $[U_0]=[U]=[v]=L/T$, $[g]=L/T^2$, and $[t]=T$. Both displayed terms in $v$ therefore have dimension $L/T$.

Solved by gpt-5.6-sol high.

With $\gamma (v)=(1-v^2/c^2{)}^{-1/2}$,Adding and subtracting $c{t}^{\prime }$ givesThe product of the two multipliers is one, so $x_{+}^{\prime }{x}_{-}^{\prime }=x_{+}{x}_{-}$, which is $x^{\prime 2}-c^2{t}^{\prime 2}=x^2-c^2{t}^2$.

Successive transformations multiply the $x_{+}$ factors. Equatingand solving gives the relativistic velocity-addition law

Solved by gpt-5.6-sol high.

The recurrence and the addition formula give the result by induction. It is true for $n=0,1$, and if true for $n,n-1$, then

Solved by gpt-5.6-sol high.

The recurrence shows that $T_n$ is a polynomial with integer coefficients. Part (a) givesThus $\cos (\pi /n)$ is a root of a nonzero integer polynomial and is algebraic.

Solved by gpt-5.6-sol high.

Put $z=2\cos (\pi /n)$. The recurrencedefines monic integer polynomials and gives $S_k(z)=2\cos (k\pi /n)$. Hence $z$ is an algebraic integer. If $\cos (\pi /n)$ is rational, then the rational algebraic integer $z$ is an integer. Since $-2\le z<2$, this leaves the values corresponding toThis is the rational cosine of an integral submultiple of pi result. For every $n\ge 4$, the value lies strictly between $1/2$ and $1$, so it is irrational.

Solved by gpt-5.6-sol high.

Every term is nonnegative. Since $1-\cos x\le x^2/2$,Comparison with $\sum k^{-2}$ shows that the partial sums are bounded. Being increasing, they converge to the finite limit

Solved by gpt-5.6-sol high.

Taking real parts of the geometric sum givesso $(a_n)$ is bounded when $\cos y\ne 1$. It cannot converge: convergence would imply $\cos (ny)=a_n-a_{n-1}\to 0$, but thenwhereas the same necessary condition applied to the subsequence $2n$ would give a limit of zero.

Solved by gpt-5.6-sol high.

For prime $p$, the nonzero residues pair with their distinct inverses except for $1$ and $-1$, so Wilson theorem givesIf composite $n>4$ has a factorization $n=ab$ with $1<a<b<n$, both factors occur in $(n-1)!$. If $n=m^2$, the distinct factors $m$ and $2m$ occur and their product is divisible by $n$; the excluded case $m=2$ is exactly $n=4$. Thus $(n-1)!\equiv 0(\mathrm{mod}n)$.

The Fermat-Euler theorem states $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$ when $(a,n)=1$. For prime $p$, $\varphi (p)=p-1$, giving Fermat's little theorem for $p\nmid a$; the form $a^p\equiv a(\mathrm{mod}p)$ also covers $p\mid a$.

If $a\equiv b(\mathrm{mod}p)$, induction and the binomial theorem showIndeed, write $a^{p^n}=b^{p^n}+c{p}^{n+1}$ and raise to the $p$th power; every nonleading binomial term gains enough powers of $p$.

Fix $a>1$ and choose any odd prime $p\nmid a^2-1$. PutFermat's theorem gives $N_p\equiv 1(\mathrm{mod}p)$, and $N_p$ is odd, so $2p\mid N_p-1$. Also $a^{2p}\equiv 1(\mathrm{mod}{N}_p)$, hence $a^{N_p-1}\equiv 1(\mathrm{mod}{N}_p)$. For odd $p$,is composite. This generalized repunit pseudoprime construction gives infinitely many distinct base-$a$ pseudoprimes because the values are unbounded.

Solved by gpt-5.6-sol high.

Induction shows that every iterate $f^n$ is injective. Applying $f$ repeatedly givesIf $f^k(X)=f^{k+1}(X)$, applying $f$ inductively gives equality with every later image. Set $A=f^k(X)$. Then $f(A)=A$, so the restriction $f:A\to A$ is surjective, and it remains injective; hence it is bijective.

Solved by gpt-5.6-sol high.

The relation preserves the equality pattern among positions. The identity permutation gives reflexivity, inverses give symmetry, and compositions give transitivity.

For $W_3$, representatives are the restricted-growth wordswhen $n=1$, $n=2$, and $n\ge 3$, respectively. Here digits denote distinct symbols, and each displayed word represents one class.

For $W_4$ with $n=3$, the fourteen classes have representativesThe cyclic subgroup $F$ gives finer classes than all of $P_4$. For example, $x_1{x}_1{x}_2$ and $x_1{x}_1{x}_3$ have the same equality pattern and are equivalent under $P_4$, but no power of the four-cycle fixes $x_1$ while sending $x_2$ to $x_3$. Thus the two equivalence-class decompositions of $W_3$ differ.

Solved by gpt-5.6-sol high.

If $A_n$ are countable, choose enumerations and map each element of ${\bigcup }_n{A}_n$ to the first pair $(n,k)$ at which it occurs. Since ${\mathbb{N}}^2$ is countable, the union is countable.

A periodic function of period $k$ is determined by its $k$ values on a complete residue system. Thus all periodic functions form a countable union over $k$ of the countable sets ${\mathbb{N}}^k$, and are countable.

The set of bijections $\mathbb{N}\to \mathbb{N}$ is uncountable. Indeed, each binary sequence determines a bijection that swaps $2j-1$ and $2j$ exactly when its $j$th bit is one. This is an injection from the uncountable set of binary sequences.

Solved by gpt-5.6-sol high.

The set is uncountable by Cantor's diagonal argument: from any proposed list, form a sequence whose $n$th bit differs from the $n$th bit of the $n$th listed sequence.

Solved by gpt-5.6-sol high.

Sequences with finitely many ones correspond to finite subsets of $\mathbb{N}$, a countable union of the countable sets of $k$-element subsets. Complementation gives the same result for finitely many zeros. Their union is therefore countable.

Solved by gpt-5.6-sol high.

All binary sequences are uncountable, while part (ii) accounts for the sequences which fail to have infinitely many symbols of both kinds and is countable. Removing that countable subset leaves an uncountable set.

Solved by gpt-5.6-sol high.

Using spherical shells and averaging the squared distance from the axis givesSliding without friction has acceleration $g\sin \alpha$, soFor rolling, $M{a}_{\mathrm{cm}}=Mg\sin \alpha -F$ and $I(a_{\mathrm{cm}}/a)=Fa$, whenceThe rolling acceleration with rotational inertia gives $5g\sin \alpha /7$ for the uniform sphere, and thereforeMechanical energy is conserved in both idealizations: there is no friction in sliding, while static friction does no work at the instantaneous contact point in pure rolling.

For $I=\gamma M{a}^2$, the same calculation gives

Solved by gpt-5.6-sol high.

With signature $(+,-,-,-)$, the four-momenta areIn the rest frame of a future timelike $P_1$, one has $P_1=(Mc,0)$ and $P_2^0>0$, so $P_1\cdot P_2=Mc{P}_2^0>0$; Lorentz invariance proves the assertion in every frame.

The impossibility of photon decay into two massive particles follows because a photon has squared four-momentum zero. If it decayed into an electron and positron, conservation would givea contradiction.

Solved by gpt-5.6-sol high.

Momentum conservation makes the sum of the two photon momenta parallel to $u$, so all three vectors are coplanar. Put the photons on opposite sides of the incident direction. Transverse and longitudinal momentum and energy conservation giveEliminating $E_1,E_2$ yieldsUsing the half-angle identities on the left gives exactly

Solved by gpt-5.6-sol high.

Assume Newton's second law, $F_{ij}=-F_{ji}$, and that each internal pair force is central, so $F_{ij}$ is parallel to $r_i-r_j$. Summingcancels internal pairs and gives $dP/dt=F:={\sum }_i{F}_i$. Taking moments about fixed $a$ cancels the internal torques pairwise and gives

The angular momentum about the centre of mass result follows similarly: differentiating ${\sum }_i(r_i-R)\times m_i({\dot{r}}_i-\dot{R})$ introduces no extra term because both total relative position weighted by mass and total relative momentum vanish. Thus its derivative is the external torque about $R$.

Finally, if every mass is $m$ and $F_i=-k{\dot{r}}_i$, then about a fixed pointTherefore

Solved by gpt-5.6-sol high.

The transverse equation of motion is $r^{-1}d(r^2\dot{\theta })/dt=0$, sois constant. With $u=1/r$,Differentiating once more and substituting into the radial equation $\ddot{r}-r{\dot{\theta }}^2=-f(r)$ gives the Binet equation

Solved by gpt-5.6-sol high.

Take $\theta =0$ initially. The velocity components areso $l=2\sqrt{3}$. Since $f(1/u)=3u^2+9u^3$, the orbit equation becomesThusThe data $u(0)=1$ and $\dot{r}=-l{u}^{\prime }$ give $A=0$, $B=2/\sqrt{3}$, henceAt $\theta =2\pi$, $u=1$ again, so the particle returns to its initial position after one revolution; now $u^{\prime }=-1/\sqrt{3}$, so it is moving outward. Subsequently $u$ first reaches zero at $\theta =8\pi /3$, where $r=1/u\to \infty$. It therefore flies off to infinity.

Solved by gpt-5.6-sol high.