= Paper 4
{scope}

https://www.maths.cam.ac.uk/undergrad/pastpapers/files/2023/paperia_4_2023.pdf

= 1F
{parent=Paper 4}
{scope}
{title2=Numbers and Sets}

= a
{parent=1f}
{scope}

= Solution
{parent=a}

Define
$$
\tau(\sigma)(j)=n+1-\sigma(j).
$$
This 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.

= b
{parent=1f}
{scope}

= Solution
{parent=b}

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 $\binom nk$ 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
$$
2A_{n+1}=\sum_{k=0}^n\binom nkA_kA_{n-k}.
$$

Solved by gpt-5.6-sol high.

= 2E
{parent=Paper 4}
{scope}
{title2=Numbers and Sets}

= Solution
{parent=2E}

The <Chinese remainder theorem> says that for pairwise coprime positive integers $m_i$, the map
$$
\mathbb Z/(m_1\cdots m_r)\mathbb Z
\longrightarrow\prod_i\mathbb Z/m_i\mathbb Z
$$
is a bijection. For two <moduli>, choose $u,v$ with $um+vn=1$; then
$$
x=b,um+a,vn
$$
has 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 $\operatorname{lcm}(6,8)=24$ gives
$$
x\equiv10\pmod{24}.
$$

Write $d=2^r3^sm$ with $(m,6)=1$. Use the Chinese remainder theorem to choose
$$
a\equiv0\pmod{2^r},\qquad 2a\equiv1\pmod{3^sm},
$$
$$
3b\equiv1\pmod{2^r},\qquad b\equiv0\pmod{3^sm}.
$$
Then $4a^2+9b^2\equiv1$ modulo each of the pairwise coprime factors $2^r$, $3^s$, and $m$, hence modulo $d$.

Solved by gpt-5.6-sol high.

= 3C
{parent=Paper 4}
{scope}
{title2=Dynamics and Relativity}

= Solution
{parent=3C}

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 order
$$
m\,dv+U\,dm=-mg\,dt,
$$
which is the stated rocket equation.

Here $dm/dt=-\alpha$ and $U=U_0m_0/m$, so
$$
\frac{dv}{dt}=\frac{\alpha U_0m_0}{(m_0-\alpha t)^2}-g.
$$
Lift-off from rest requires positive initial <acceleration>,
$$
\frac{\alpha U_0}{m_0}>g.
$$
With $v(0)=0$, integration gives
$$
v(t)=U_0\left(\frac{m_0}{m_0-\alpha t}-1\right)-gt.
$$
The 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.

= 4C
{parent=Paper 4}
{scope}
{title2=Dynamics and Relativity}

= Solution
{parent=4C}

With $\gamma(v)=(1-v^2/c^2)^{-1/2}$,
$$
x'=\gamma(x-vt),
\qquad
t'=\gamma\left(t-\frac{vx}{c^2}\right).
$$
Adding and subtracting $ct'$ gives
$$
x'_+=\gamma(1-v/c)x_+
=\sqrt{\frac{c-v}{c+v}},x_+,
$$
$$
x'_- =\gamma(1+v/c)x_-
=\sqrt{\frac{c+v}{c-v}},x_-.
$$
The product of the two multipliers is one, so $x'_+x'_-=x_+x_-$, which is $x'^2-c^2t'^2=x^2-c^2t^2$.

Successive transformations multiply the $x_+$ factors. Equating
$$
\lambda(v_3)=\lambda(v_2)\lambda(v_1)
$$
and solving gives the relativistic velocity-addition law
$$
v_3=\frac{v_1+v_2}{1+v_1v_2/c^2}.
$$

Solved by gpt-5.6-sol high.

= 5F
{parent=Paper 4}
{scope}
{title2=Numbers and Sets}

= a
{parent=5f}
{scope}

= Solution
{parent=a}

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
$$
T_{n+1}(\cos y)=2\cos y\cos(ny)-\cos((n-1)y)=\cos((n+1)y).
$$

Solved by gpt-5.6-sol high.

= b
{parent=5f}
{scope}

= Solution
{parent=b}

The recurrence shows that $T_n$ is a <polynomial> with integer coefficients. Part (a) gives
$$
T_n(\cos(\pi/n))+1=\cos\pi+1=0.
$$
Thus $\cos(\pi/n)$ is a root of a nonzero integer <polynomial> and is algebraic.

Solved by gpt-5.6-sol high.

= c
{parent=5f}
{scope}

= Solution
{parent=c}

Put $z=2\cos(\pi/n)$. The recurrence
$$
S_0(z)=2,\quad S_1(z)=z,\quad S_{k+1}(z)=zS_k(z)-S_{k-1}(z)
$$
defines 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\leq z<2$, this leaves the values corresponding to
$$
n=1:\cos\pi=-1,\qquad n=2:\cos(\pi/2)=0,\qquad n=3:\cos(\pi/3)=\frac12.
$$
This is the <rational cosine of an integral submultiple of pi> result. For every $n\geq4$, the value lies strictly between $1/2$ and $1$, so it is irrational.

Solved by gpt-5.6-sol high.

= d
{parent=5f}
{scope}

= i
{parent=d}
{scope}

= Solution
{parent=i}

Every term is nonnegative. Since $1-\cos x\leq x^2/2$,
$$
0\leq1-\cos(\pi/k)\leq\frac{\pi^2}{2k^2}.
$$
Comparison with $\sum k^{-2}$ shows that the partial sums are bounded. Being increasing, they converge to the finite <limit>
$$
\sum_{k=1}^{\infty}(1-\cos(\pi/k)).
$$

Solved by gpt-5.6-sol high.

= ii
{parent=d}
{scope}

= Solution
{parent=ii}

Taking real parts of the geometric sum gives
$$
a_n=\Re\frac{1-e^{i(n+1)y}}{1-e^{iy}},
$$
so $(a_n)$ is bounded when $\cos y\ne1$. It cannot converge: convergence would imply $\cos(ny)=a_n-a_{n-1}\to0$, but then
$$
\cos(2ny)=2\cos^2(ny)-1\to-1,
$$
whereas the same necessary condition applied to the subsequence $2n$ would give a <limit> of zero.

Solved by gpt-5.6-sol high.

= 6E
{parent=Paper 4}
{scope}
{title2=Numbers and Sets}

= Solution
{parent=6E}

For prime $p$, the nonzero residues pair with their distinct inverses except for $1$ and $-1$, so <Wilson theorem> gives
$$
(p-1)!\equiv-1\pmod p.
$$
If 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)!\equiv0\pmod n$.

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

If $a\equiv b\pmod p$, induction and the binomial theorem show
$$
a^{p^n}\equiv b^{p^n}\pmod{p^{n+1}}.
$$
Indeed, write $a^{p^n}=b^{p^n}+cp^{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$. Put
$$
N_p=\frac{a^{2p}-1}{a^2-1}=1+a^2+\cdots+a^{2(p-1)}.
$$
Fermat's theorem gives $N_p\equiv1\pmod p$, and $N_p$ is odd, so $2p\mid N_p-1$. Also $a^{2p}\equiv1\pmod{N_p}$, hence $a^{N_p-1}\equiv1\pmod{N_p}$. For odd $p$,
$$
N_p=\frac{a^p-1}{a-1}\frac{a^p+1}{a+1}
$$
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.

= 7D
{parent=Paper 4}
{scope}
{title2=Numbers & Sets}

= a
{parent=7d}
{scope}

= Solution
{parent=a}

Induction shows that every iterate $f^n$ is injective. Applying $f$ repeatedly gives
$$
X\supseteq f(X)\supseteq f^2(X)\supseteq\cdots.
$$
If $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.

= b
{parent=7d}
{scope}

= Solution
{parent=b}

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 words
$$
111;\qquad 111,112,121,122;\qquad 111,112,121,122,123
$$
when $n=1$, $n=2$, and $n\geq3$, respectively. Here digits denote distinct symbols, and each displayed word represents one class.

For $W_4$ with $n=3$, the fourteen classes have representatives
$$
1111,1112,1121,1122,1123,1211,1212,1213,
1221,1222,1223,1231,1232,1233.
$$
The cyclic <subgroup> $F$ gives finer classes than all of $P_4$. For example, $x_1x_1x_2$ and $x_1x_1x_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.

= 8D
{parent=Paper 4}
{scope}
{title2=Numbers & Sets}

= Solution
{parent=8D}

If $A_n$ are countable, choose enumerations and map each element of $\bigcup_nA_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.

= i
{parent=8d}
{scope}

= Solution
{parent=i}

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.

= ii
{parent=8d}
{scope}

= Solution
{parent=ii}

<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.

= iii
{parent=8d}
{scope}

= Solution
{parent=iii}

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.

= 9C
{parent=Paper 4}
{scope}
{title2=Dynamics and Relativity}

= Solution
{parent=9C}

Using spherical shells and averaging the squared distance from the axis gives
$$
I=\frac25Ma^2.
$$
Sliding without friction has <acceleration> $g\sin\alpha$, so
$$
t_s=\sqrt{\frac{2l}{g\sin\alpha}}.
$$
For rolling, $Ma_{\rm cm}=Mg\sin\alpha-F$ and $I(a_{\rm cm}/a)=Fa$, whence
$$
a_{\rm cm}=\frac{g\sin\alpha}{1+I/(Ma^2)}.
$$
The <rolling acceleration with rotational inertia> gives $5g\sin\alpha/7$ for the uniform sphere, and therefore
$$
\frac{t_s}{t_r}=\sqrt{\frac57}.
$$
Mechanical 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 Ma^2$, the same calculation gives
$$
\frac{t_s}{t_r}=\frac1{\sqrt{1+\gamma}}.
$$

Solved by gpt-5.6-sol high.

= 10C
{parent=Paper 4}
{scope}
{title2=Dynamics and Relativity}

= a
{parent=10c}
{scope}

= Solution
{parent=a}

With signature $(+,-,-,-)$, the four-momenta are
$$
P_{\rm massive}=m\gamma(c,v),
\qquad
P_\gamma=\frac{\hbar\omega}{c}(1,e).
$$
In 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=McP_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 give
$$
0=(P_-+P_+)^2=2m^2c^2+2P_-\cdot P_+>0,
$$
a contradiction.

Solved by gpt-5.6-sol high.

= b
{parent=10c}
{scope}

= Solution
{parent=b}

<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 give
$$
E_1\sin\theta_1=E_2\sin\theta_2,
$$
$$
E_1\cos\theta_1+E_2\cos\theta_2=\gamma muc,
\qquad E_1+E_2=mc^2(\gamma+1).
$$
Eliminating $E_1,E_2$ yields
$$
\frac{\sin(\theta_1+\theta_2)}{\sin\theta_1+\sin\theta_2}
=\frac{\gamma u/c}{\gamma+1}
=\sqrt{\frac{\gamma-1}{\gamma+1}}.
$$
Using the half-angle identities on the left gives exactly
$$
\frac{1+\cos(\theta_1+\theta_2)}{\cos\theta_1+\cos\theta_2}
=\sqrt{\frac{\gamma-1}{\gamma+1}}.
$$

Solved by gpt-5.6-sol high.

= 11C
{parent=Paper 4}
{scope}
{title2=Dynamics and Relativity}

= Solution
{parent=11C}

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$. Summing
$$
m_i\ddot r_i=F_i+\sum_{j\ne i}F_{ij}
$$
cancels internal pairs and gives $dP/dt=F:=\sum_iF_i$. Taking moments about fixed $a$ cancels the internal <torques> pairwise and gives
$$
\frac{dL}{dt}=G:=\sum_i(r_i-a)\times F_i.
$$

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 point
$$
G=-k\sum_i(r_i-a)\times\dot r_i=-\frac{k}{m}L.
$$
Therefore
$$
L(t)=L(0)e^{-kt/m}.
$$

Solved by gpt-5.6-sol high.

= 12C
{parent=Paper 4}
{scope}
{title2=Dynamics and Relativity}

= a
{parent=12c}
{scope}

= Solution
{parent=a}

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

Solved by gpt-5.6-sol high.

= b
{parent=12c}
{scope}

= Solution
{parent=b}

Take $\theta=0$ initially. The <velocity> components are
$$
\dot r(0)=-4\cos(\pi/3)=-2,
\qquad r\dot\theta(0)=4\sin(\pi/3)=2\sqrt3,
$$
so $l=2\sqrt3$. Since $f(1/u)=3u^2+9u^3$, the orbit equation becomes
$$
u''+\frac14u=\frac14.
$$
Thus
$$
u=1+A\cos(\theta/2)+B\sin(\theta/2).
$$
The data $u(0)=1$ and $\dot r=-lu'$ give $A=0$, $B=2/\sqrt3$, hence
$$
\boxed{u(\theta)=1+\frac2{\sqrt3}\sin(\theta/2)}.
$$
At $\theta=2\pi$, $u=1$ again, so the particle returns to its initial position after one revolution; now $u'=-1/\sqrt3$, 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.