= Paper 2
{scope}

https://www.maths.cam.ac.uk/undergrad/pastpapers/files/2025/paperia_2_2025.pdf

= 1C
{parent=Paper 2}
{scope}
{title2=Differential Equations}

= Solution
{parent=1c}

The critical-point equations are $2xy=0$ and $x^2+y^2=1$, so the points are $(\pm1,0)$ and $(0,\pm1)$. The Hessian is
$$\begin{pmatrix}2y&2x\\2x&2y\end{pmatrix}.$$
Thus $(0,1)$ is a strict minimum, $(0,-1)$ a strict maximum, and $(\pm1,0)$ are saddles. The local contour patterns are respectively ellipses, inverted ellipses, and crossing hyperbolas.

The <gradient flow> has $\dot x=-2xy$ and $\dot y=1-x^2-y^2$. Hence
$$2xy\frac{dy}{dx}-y^2=x^2-1.$$
Putting $u=y^2$ gives $xu'-u=x^2-1$. Multiplication by the <integrating factor> $1/x$ yields
$$\left(\frac ux\right)'=1-\frac1{x^2},$$
and therefore the general trajectory is
$$y^2=x^2+1+cx.$$

Solved by gpt-5.6-sol high.

= 2C
{parent=Paper 2}
{scope}
{title2=Differential Equations}

= a
{parent=2c}
{scope}

= Solution
{parent=a}

The fixed points are $0$ and, when $a\ge-1$, $1\pm\sqrt{1+a}$. For a <scalar> autonomous equation, a simple fixed point is stable when $f'<0$. Since $f'(0)=a$ and $f'(r)=2r(1-r)$ at either nonzero root, excluding the bifurcation values as requested,
$$0\text{ is stable for }a<0,$$
$$1+\sqrt{1+a}\text{ is stable for }a>-1,$$
and
$$1-\sqrt{1+a}\text{ is stable for }a>0.$$

Solved by gpt-5.6-sol high.

= b
{parent=2c}
{scope}

= Solution
{parent=b}

The fixed points are $x=-2\pm2\sqrt{1+b}$, so they exist for $b\ge-1$. A fixed point of an iteration is stable when $|g'(x)|<1$; here this is $|x|<2$. Only the plus root can satisfy it, and it does precisely for
$$-1<b<3.$$

Solved by gpt-5.6-sol high.

= 3F
{parent=Paper 2}
{scope}
{title2=Probability}

= Solution
{parent=3f}

Since $Y=\int_0^\infty\mathbf1_{\{Y\ge y\}}\,dy$, Tonelli's theorem gives
$$\mathbb E Y=\int_0^\infty\mathbb P(Y\ge y)\,dy.$$
For the integer-valued minimum,
$$\mathbb E M=\sum_{k=1}^n\mathbb P(M\ge k)
=\sum_{j=0}^{n-1}\left(1-\frac jn\right)^n
\le\sum_{j=0}^\infty e^{-j}=\frac e{e-1}<e.$$
Markov's inequality now gives
$$\mathbb P(M\ge6)\le\frac{\mathbb E M}{6}<\frac e6<\frac12.$$

Solved by gpt-5.6-sol high.

= 4F
{parent=Paper 2}
{scope}
{title2=Probability}

= a
{parent=4f}
{scope}

= Solution
{parent=a}

The number of stops is $X\sim\operatorname{Bin}(n,1/n)$. For each fixed $k\ge0$,
$$\mathbb P(X=k)=\binom nk n^{-k}(1-n^{-1})^{n-k}\longrightarrow\frac{e^{-1}}{k!},$$
the mass <function> of a Poisson <random variable> of mean one.

Solved by gpt-5.6-sol high.

= b
{parent=4f}
{scope}

= Solution
{parent=b}

At station $j$, the probability of stopping is
$$\frac2n-\frac1n\left(1-\frac1n\right)^{j-1},$$
because the lower rate applies exactly when no earlier stop occurred. By <linearity of expectation>,
$$\mathbb E X=2-\frac1n\sum_{j=1}^n\left(1-\frac1n\right)^{j-1}
=1+\left(1-\frac1n\right)^n\longrightarrow1+e^{-1}.$$

Solved by gpt-5.6-sol high.

= 5C
{parent=Paper 2}
{scope}
{title2=Differential Equations}

= a
{parent=5c}
{scope}

= Solution
{parent=a}

The <Wronskian> is $W=y_1y_2'-y_2y_1'$. Abel's identity gives
$$W'=-pW.$$
If $W\ne0$, the two column <vectors> in the displayed representation form a <basis> of $\mathbb R^2$ at each $x$. Differentiating the first component and comparing it with the second gives
$$u'y_1+v'y_2=0.$$
Substitution in the differential equation gives
$$u'y_1'+v'y_2'=f.$$
Solving this two-by-two system yields
$$u'=-\frac{y_2f}{W},\qquad v'=\frac{y_1f}{W}.$$

Solved by gpt-5.6-sol high.

= b
{parent=5c}
{scope}

= Solution
{parent=b}

After division by $x^2$, Abel's identity gives $W=C/x$. <Reduction of order> from $y_1=x^{-1/2}e^{-x}$ allows the convenient choices
$$y_2=x^{-1/2}e^x,\qquad W=\frac2x.$$
The normalized forcing is $f=x^{3/2}$, so
$$u'=-\frac12x^2e^x,\qquad v'=\frac12x^2e^{-x}.$$
Taking convenient antiderivatives and simplifying gives the particular solution $-x^{3/2}-2x^{-1/2}$. Hence
$$y=C_1x^{-1/2}e^{-x}+C_2x^{-1/2}e^x-x^{3/2}-2x^{-1/2}.$$

Solved by gpt-5.6-sol high.

= 6C
{parent=Paper 2}
{scope}
{title2=Differential Equations}

= a
{parent=6c}
{scope}

= Solution
{parent=a}

For $k\ne m$, the required Euler-equation solution is
$$x(t)=\frac{t^k-t^m}{k^2-m^2}.$$
For $k=m>0$, the limiting resonant form is
$$x(t)=\frac{t^m\log t}{2m}.$$
Both extend continuously to zero and satisfy the two <boundary conditions>. If $k=m=0$, integration gives
$$x=\frac12(\log t)^2+C\log t+D,$$
which cannot have a finite zero <limit> at $t=0$, so no such solution exists.

Solved by gpt-5.6-sol high.

= b
{parent=6c}
{scope}

= Solution
{parent=b}

Set $y=tz$ and $u=(x,z)^T$. The system becomes
$$tu'=\begin{pmatrix}4&-6\\3&-5\end{pmatrix}u+t\binom11+\binom21.$$
The <matrix> has eigenpairs $1,(2,1)^T$ and $-2,(1,1)^T$. A particular solution is $(-t/3-2,-1)^T$. Therefore
$$x=2C_1t+C_2t^{-2}-\frac t3-2,$$
$$y=C_1t^2+C_2t^{-1}-t.$$

Solved by gpt-5.6-sol high.

= 7C
{parent=Paper 2}
{scope}
{title2=Differential Equations}

= a
{parent=7c}
{scope}

= Solution
{parent=a}

Choose
$$\omega=\sqrt{\frac km-\frac{b^2}{4m^2}},\qquad
\kappa=\frac{b}{2m\omega},\qquad T=\omega t^*.$$
Using $\delta(t-nt^*)=\omega\delta(\tau-nT)$ and $y=m\omega x/P$ then gives exactly the displayed dimensionless equation.

Solved by gpt-5.6-sol high.

= b
{parent=7c}
{scope}

= Solution
{parent=b}

Iteration gives
$$x_n=A^na+\sum_{j=0}^{n-1}A^jb
=A^na+(I-A^n)(I-A)^{-1}b,$$
where the inverse exists by the hypothesis.

Solved by gpt-5.6-sol high.

= c
{parent=7c}
{scope}

= Solution
{parent=c}

Continuity of $y$ and integration across the impulse show that $y'$ jumps by one. Since $f'=-g-\kappa f$ and $g'=f-\kappa g$, evaluation just before and after $(n+1)T$ gives
$$\binom{C_{n+1}}{D_{n+1}}=
\begin{pmatrix}f(T)&g(T)\\-g(T)&f(T)\end{pmatrix}
\binom{C_n}{D_n}+\binom01.$$

Solved by gpt-5.6-sol high.

= d
{parent=7c}
{scope}

= Solution
{parent=d}

The <eigenvalues> of the recurrence <matrix> have <modulus> $e^{-\kappa T}<1$, so transients decay and the coefficients approach the fixed point
$$x_\infty=(I-A)^{-1}b
=\frac{(g(T),1-f(T))^T}{[1-f(T)]^2+g(T)^2}.$$
Thus
$$|x_\infty|=\{[1-f(T)]^2+g(T)^2\}^{-1/2}.$$
For $T=k\pi$ and $\kappa k\ll1$, this is
$$|x_\infty|\sim\begin{cases}(\kappa k\pi)^{-1},&k\text{ even},\\[2mm]1/2,&k\text{ odd}.
\end{cases}$$
Even multiples deliver impulses in phase and produce <resonance>; odd multiples alternate the phase and largely cancel.

Solved by gpt-5.6-sol high.

= 8C
{parent=Paper 2}
{scope}
{title2=Differential Equations}

= a
{parent=8c}
{scope}

= Solution
{parent=a}

The chain rule gives
$$\partial_x=\tau^{-p}\partial_\eta,\qquad
\partial_t=\partial_\tau-\frac{p\eta}{\tau}\partial_\eta.$$
Choose
$$p=\frac1{m+2},\qquad H(\tau)=\tau^{-1/(m+2)}.$$
The PDE then reduces to the stated ODE. One integration, using symmetry at zero, gives $Y^mY'=-\eta Y$. Hence
$$Y(\eta)=\left[\frac m2(1-\eta^2)\right]^{1/m},\qquad |\eta|\le1,$$
which has the required endpoint values.

Solved by gpt-5.6-sol high.

= b
{parent=8c}
{scope}

= Solution
{parent=b}

For $m=1$, $Y=(1-\eta^2)/2$. Expanding both sides of the perturbation equation gives
$$(1-\eta^2)y''-2\eta y'+6\lambda y=0.$$
For $y=\sum_{r\ge0}a_r\eta^r$, coefficient comparison gives
$$a_{r+2}=\frac{r(r+1)-6\lambda}{(r+2)(r+1)}a_r.$$
The even and odd <series> terminate exactly when $6\lambda=k(k+1)$ with the corresponding parity. Thus every positive integer $k$ gives the regular <polynomial> solution, a Legendre <polynomial> up to scale.

Solved by gpt-5.6-sol high.

= 9F
{parent=Paper 2}
{scope}
{title2=Probability}

= a
{parent=9f}
{scope}

= Solution
{parent=a}

If $T$ is the number of triads, then
$$\mathbb ET=\binom n3\frac18<\frac{n^3}{48}.$$
Markov's inequality therefore gives
$$\mathbb P(T\ge n^3/24)\le\frac12.$$

Solved by gpt-5.6-sol high.

= b
{parent=9f}
{scope}

= Solution
{parent=b}

Complementing every friendship sends every degree $d$ to $n-1-d$, and hence sends $S=M+L$ to $2(n-1)-S$. Since the random graph and its complement have the same law, the distribution of $S$ is symmetric about $n-1$, giving $\mathbb ES=n-1$.

The same symmetry gives equal probabilities strictly below and above $n-1$. There is positive probability at $n-1$: for odd $n$ use a regular graph of degree $(n-1)/2$; for even $n=2m$, use $K_{m,m}$ with a perfect matching removed and then restore one matching edge. Thus the lower <median> as defined is also $n-1$.

Solved by gpt-5.6-sol high.

= c
{parent=9f}
{scope}

= Solution
{parent=c}

With $p=(1+\varepsilon)\log n/(n-1)$, the <union bound> gives
$$\mathbb P(L=0)\le n(1-p)^{n-1}
\le ne^{-p(n-1)}=n^{-\varepsilon}.$$

Solved by gpt-5.6-sol high.

= 10F
{parent=Paper 2}
{scope}
{title2=Probability}

= a
{parent=10f}
{scope}

= Solution
{parent=a}

Every reachable <sequence> is a restricted-growth <sequence> in $A_n$. Given one, the transition masses sum to
$$\frac{\sum_{i=1}^{M}(N_i-1/2)+1+M/2}{n+1}=1,$$
and every allowed transition remains in $A_{n+1}$. Induction from $X_1=1$ therefore proves that $(X_1,\ldots,X_n)\in A_n$ almost surely.

Solved by gpt-5.6-sol high.

= b
{parent=10f}
{scope}

= Solution
{parent=b}

Conditional on label $1$ still having frequency one, it is avoided at step $i+1$ with probability $(i+1/2)/(i+1)$. Consequently
$$\mathbb P(N_1(X)=1)=\frac{\prod_{i=1}^{n-1}(i+1/2)}{n!}.$$
The last observation is a singleton exactly when it introduces a new label, whose <conditional probability> is $(1+M_{n-1}/2)/n$. Taking expectations gives
$$\mathbb P(N_{X_n}(X)=1)=\frac{1+\tfrac12\mathbb E M_{n-1}}n.$$

Solved by gpt-5.6-sol high.

= c
{parent=10f}
{scope}

= Solution
{parent=c}

Multiplying transition probabilities along a path gives a denominator $n!$. The numerator factors into one product depending only on the final number of labels and, for each label, a product
$$\prod_{j=1}^{N_i-1}(j-1/2).$$
It is therefore unchanged when the final label frequencies are permuted. This proves the claimed equality.

Solved by gpt-5.6-sol high.

= d
{parent=10f}
{scope}

= Solution
{parent=d}

View a restricted-growth string as a set partition. Reverse the underlying order and relabel blocks by first appearance. This is a bijection of $A_n$ which sends the size of the block containing the first position to the size of the block containing the last position. Part (c) shows that it preserves probability, so the two probabilities in part (b) are equal. Replacing $n$ there by $n+1$ gives
$$\mathbb E M_n=2\left(\frac{\prod_{i=1}^{n}(i+1/2)}{n!}-1\right).$$

Solved by gpt-5.6-sol high.

= 11F
{parent=Paper 2}
{scope}
{title2=Probability}

= a
{parent=11f}
{scope}

= Solution
{parent=a}

For a nonnegative <random variable> $Z$ and $a>0$, the pointwise inequality $Z\ge a\mathbf1_{\{Z\ge a\}}$ gives
$$\mathbb P(Z\ge a)\le\frac{\mathbb EZ}{a}.$$

Solved by gpt-5.6-sol high.

= b
{parent=11f}
{scope}

= Solution
{parent=b}

A leaf at depth $d$ is reached with probability $2^{-d}$ and contributes $2^d$. Summing over leaves gives $\mathbb E[2^{X_1}]=\ell$. Since $L$ is the sample mean of the $2^{X_i}$, $\mathbb EL=\ell$.

Solved by gpt-5.6-sol high.

= c
{parent=11f}
{scope}

= Solution
{parent=c}

Similarly,
$$\mathbb E[2^{2X_1}]=\sum_{\text{leaves }v}2^{d(v)}\le\ell2^b.$$
Thus $\operatorname{Var}(L)\le\ell2^b/n$. Chebyshev's inequality gives
$$\mathbb P\left(\frac{|L-\ell|}{\ell}\ge\alpha\sqrt{\frac{2^b}{n\ell}}\right)\le\frac1{\alpha^2}.$$

Solved by gpt-5.6-sol high.

= d
{parent=11f}
{scope}

= Solution
{parent=d}

Let $\sigma^2=\operatorname{Var}(2^{X_1})\le\ell2^b$. If $\sigma=0$ the result is immediate. Otherwise the <central limit theorem> applies to $L$, while the displayed threshold is at least $\alpha\sigma/\sqrt n$. Hence
$$\lim_{n\to\infty}\mathbb P\left(\frac{|L-\ell|}{\ell}\ge\alpha\sqrt{\frac{2^b}{n\ell}}\right)
\le2-2\Phi(\alpha).$$

Solved by gpt-5.6-sol high.

= 12F
{parent=Paper 2}
{scope}
{title2=Probability}

= a
{parent=12f}
{scope}

= Solution
{parent=a}

Direct integration of the gamma density gives, for $t<1$,
$$M_S(t)=\frac1{(n-1)!}\int_0^\infty s^{n-1}e^{-(1-t)s}\,ds=(1-t)^{-n}.$$

Solved by gpt-5.6-sol high.

= b
{parent=12f}
{scope}

= Solution
{parent=b}

For $0<x,y<1$, set $a=x^{-1/n}-1$ and $b=y^{-1/n}-1$. Conditional on $S$,
$$\mathbb P(X_1\le x,X_2\le y\mid S)=e^{-(a+b)S}.$$
Using part (a),
$$F_{X_1,X_2}(x,y)=(x^{-1/n}+y^{-1/n}-1)^{-n}.$$
<Differentiation> gives
$$f_{X_1,X_2}(x,y)=\frac{n+1}{n}\frac{x^{-1-1/n}y^{-1-1/n}}{(x^{-1/n}+y^{-1/n}-1)^{n+2}}.$$
Putting $y=1$ yields $F_{X_1}(x)=x$, so $X_1$ is uniform on $(0,1)$.

Solved by gpt-5.6-sol high.

= c
{parent=12f}
{scope}

= Solution
{parent=c}

Because $u\mapsto(1+u/S)^{-n}$ decreases, $X_i<X_{i+1}$ exactly when $E_i>E_{i+1}$. Therefore $K\ge i$ exactly when $E_1\le\cdots\le E_i$, an event of probability $1/i!$ independent of $S$. The tail-sum rearrangement gives
$$\mathbb E\sum_{i=1}^KS^i=\sum_{i=1}^n\mathbb E[S^i]\mathbb P(K\ge i).$$
Since $\mathbb E[S^i]=(n+i-1)!/(n-1)!$, the $i$th term is $\binom{n+i-1}{i}$, proving the formula.

Solved by gpt-5.6-sol high.