Past exam of the mathematics course of the University of Cambridge / 2025 / ia / Paper 2

The critical-point equations are $2xy=0$ and $x^2+y^2=1$, so the points are $(\pm 1,0)$ and $(0,\pm 1)$. The Hessian isThus $(0,1)$ is a strict minimum, $(0,-1)$ a strict maximum, and $(\pm 1,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$. HencePutting $u=y^2$ gives $x{u}^{\prime }-u=x^2-1$. Multiplication by the integrating factor $1/x$ yieldsand therefore the general trajectory is

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^{\prime }<0$. Since $f^{\prime }(0)=a$ and $f^{\prime }(r)=2r(1-r)$ at either nonzero root, excluding the bifurcation values as requested,and

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

Since $Y={\int }_0^{\infty }{1}_{\{Y\ge y\}}dy$, Tonelli's theorem givesFor the integer-valued minimum,Markov's inequality now gives

The number of stops is $X\sim \mathrm{Bin}(n,1/n)$. For each fixed $k\ge 0$,the mass function of a Poisson random variable of mean one.

At station $j$, the probability of stopping isbecause the lower rate applies exactly when no earlier stop occurred. By linearity of expectation,

The Wronskian is $W=y_1{y}_2^{\prime }-y_2{y}_1^{\prime }$. Abel's identity givesIf $W\ne 0$, 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 givesSubstitution in the differential equation givesSolving this two-by-two system yields

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 choicesThe normalized forcing is $f=x^{3/2}$, soTaking convenient antiderivatives and simplifying gives the particular solution $-x^{3/2}-2x^{-1/2}$. Hence

For $k\ne m$, the required Euler-equation solution isFor $k=m>0$, the limiting resonant form isBoth extend continuously to zero and satisfy the two boundary conditions. If $k=m=0$, integration giveswhich cannot have a finite zero limit at $t=0$, so no such solution exists.

Set $y=tz$ and $u=(x,z{)}^T$. The system becomesThe matrix has eigenpairs $1,(2,1{)}^T$ and $-2,(1,1{)}^T$. A particular solution is $(-t/3-2,-1{)}^T$. Therefore

ChooseUsing $\delta (t-n{t}^{\ast })=\omega \delta (\tau -nT)$ and $y=m\omega x/P$ then gives exactly the displayed dimensionless equation.

Iteration giveswhere the inverse exists by the hypothesis.

Continuity of $y$ and integration across the impulse show that $y^{\prime }$ jumps by one. Since $f^{\prime }=-g-\kappa f$ and $g^{\prime }=f-\kappa g$, evaluation just before and after $(n+1)T$ gives

The eigenvalues of the recurrence matrix have modulus $e^{-\kappa T}<1$, so transients decay and the coefficients approach the fixed pointThusFor $T=k\pi$ and $\kappa k\ll 1$, this isEven multiples deliver impulses in phase and produce resonance; odd multiples alternate the phase and largely cancel.

The chain rule givesChooseThe PDE then reduces to the stated ODE. One integration, using symmetry at zero, gives $Y^m{Y}^{\prime }=-\eta Y$. Hencewhich has the required endpoint values.

For $m=1$, $Y=(1-{\eta }^2)/2$. Expanding both sides of the perturbation equation givesFor $y={\sum }_{r\ge 0}{a}_r{\eta }^r$, coefficient comparison givesThe 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.

If $T$ is the number of triads, thenMarkov's inequality therefore gives

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{E}S=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$.

With $p=(1+\epsilon )\log n/(n-1)$, the union bound gives

Every reachable sequence is a restricted-growth sequence in $A_n$. Given one, the transition masses sum toand every allowed transition remains in $A_{n+1}$. Induction from $X_1=1$ therefore proves that $(X_1,\dots ,X_n)\in A_n$ almost surely.

Conditional on label $1$ still having frequency one, it is avoided at step $i+1$ with probability $(i+1/2)/(i+1)$. ConsequentlyThe 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

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 productIt is therefore unchanged when the final label frequencies are permuted. This proves the claimed equality.

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

For a nonnegative random variable $Z$ and $a>0$, the pointwise inequality $Z\ge a{1}_{\{Z\ge a\}}$ gives

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{E}L=\ell$.

Similarly,Thus $\mathrm{Var}(L)\le \ell 2^b/n$. Chebyshev's inequality gives

Let ${\sigma }^2=\mathrm{Var}(2^{X_1})\le \ell 2^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

Direct integration of the gamma density gives, for $t<1$,

For $0<x,y<1$, set $a=x^{-1/n}-1$ and $b=y^{-1/n}-1$. Conditional on $S$,Using part (a),Differentiation givesPutting $y=1$ yields $F_{X_1}(x)=x$, so $X_1$ is uniform on $(0,1)$.

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 givesSince $\mathbb{E}[S^i]=(n+i-1)!/(n-1)!$, the $i$th term is $\left(\genfrac{}{}{0ex}{}{n+i-1}{i}\right)$, proving the formula.