Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 1

For an odd composite $N$ and a unit $b$ modulo $N$, $N$ is a Fermat pseudoprime to base $b$ whenIt is an Euler pseudoprime to base $b$ whenwhere the right side is the Jacobi symbol.

By the Chinese remainder theorem,and $\phi (105)=2\cdot 4\cdot 6=48$. The condition $b^{104}=1$ is automatic modulo $3$ and $5$. Modulo $7$ it hassolutions. Thus there are $2\cdot 4\cdot 2=16$ Fermat bases, giving proportion

For the Euler condition, $b^{52}=1$ modulo $3$, so the Jacobi symbol must be $+1$. The power condition is automatic modulo $5$, while modulo $7$ it again restricts $b$ to the two solutions of $b^2=1$. For each of those two residues, exactly half of the $2\cdot 4$ choices modulo $3$ and $5$ have Jacobi symbol $+1$. Hence there are $2\cdot 4=8$ Euler bases and proportion

Solved by gpt-5.6-sol high.

The $n$th Chebyshev polynomial is defined on $[-1,1]$ byThe cosine addition formula givesInduction therefore shows that every $T_n$ is a polynomial. Its defining cosine formula also gives

Solved by gpt-5.6-sol high.

The assertion is clear for $T_1=x$. If $T_n$ has degree $n$ and leading coefficient $2^{n-1}$, the recurrence shows that the leading term of $T_{n+1}$ isthe lower-degree polynomial $T_{n-1}$ cannot cancel it. Hence

Solved by gpt-5.6-sol high.

For $x=\cos \theta \in [-1,1]$,Both sides are polynomials in $x$. Since they agree on an interval, the polynomial identity theorem extends the equality to every real $x$. Thus $T_n$ is even for even $n$ and odd for odd $n$.

Solved by gpt-5.6-sol high.

The $n$ roots of $T_n$ are distinct and lie in $(-1,1)$. Repeated use of Rolle's theorem shows that every root of $T_n^{(k)}$, for $0\le k<n$, also lies in $(-1,1)$. Its leading coefficient is positive, soTaking $k=r+1$ shows thatfor $0\le r\le n-1$; when $r=n-1$, the derivative is the positive constant $T_n^{(n)}$. This is the positivity of Chebyshev derivatives beyond the unit interval.

Solved by gpt-5.6-sol high.

Writing $x=\cos \theta$ and taking the limit as $\theta \to 0$ givesPart (d), with $r=1$, shows that $T_n^{\prime }$ is increasing on $[1,\infty )$, soSince $T_n(1)=1$ and $n^2\ge n$,

Solved by gpt-5.6-sol high.

Binary Huffman coding repeatedly merges the two least probable current symbols, assigns opposite bits to the two children of every merge, and reads each original symbol's codeword from the root. The resulting prefix code minimizes expected word length.

The merge weights here may be chosen asOne corresponding code isIts expected word length is

Solved by gpt-5.6-sol high.

Take the productionsand the word $w=aa$. There is only one parse tree: its root uses $S\to AA$ and each child uses $A\to a$. There are nevertheless exactly two derivations,andaccording as the left or right occurrence of $A$ is replaced first. This illustrates that derivations record replacement order while a context-free grammar parse tree does not.

Solved by gpt-5.6-sol high.

The first displayed tree supplies the productions $S\Rightarrow AS$ and $S\Rightarrow AA$, as well as an $A$-parse tree producing $ab$. By assumption there is also an $A$-parse tree producing $baba$. Substitute these trees as follows:The resulting yield is

Solved by gpt-5.6-sol high.

The displayed trees provide $A$-parse trees producing $ab$, $bb$, and $aa$, together with the same root productions as above. Thereforewhose yield is

Solved by gpt-5.6-sol high.

Assume that $L$ is context-free and let $p$ be its pumping length. Apply the pumping lemma for context-free languages toWrite $w=uvxyz$, with $|vxy|\le p$ and $|vy|>0$. The substring $vxy$ meets at most two of the three constant-letter blocks.

If $v$ and $y$ affect only the first block, only the middle block, or only the last block, pumping down immediately makes the final block length differ from the minimum of the first two lengths. If they meet the first and second blocks, pumping down decreases at least one of those block lengths while leaving the final length $p$, again violating the defining minimum.

It remains that they meet the second and third blocks. Let pumping change their lengths by $s$ and $t$, respectively. Pumping down fails unless $s=t$. If $s=t>0$, pumping up gives lengthswhose last entry is not $\min (p,p+s)=p$. Thus some pumping exponent always leaves $L$, contradicting the lemma. Hence

Solved by gpt-5.6-sol high.

A generalized linear model has three components:

Solved by gpt-5.6-sol high.

Write the exponential-dispersion density asWith the canonical link, ${\theta }_i={\eta }_i=x_i^T\beta$. ThereforeKnown prior weights replace $\varphi$ by $\varphi /w_i$.

Solved by gpt-5.6-sol high.

In the Poisson GLM the responses are independent andThe Poisson canonical link is logarithmic, so

Solved by gpt-5.6-sol high.

For $F(n)=\alpha n-\beta n^3$, the nonnegative equilibria areSincethe zero equilibrium is unstable and $K$ is asymptotically stable.

Solved by gpt-5.6-sol high.

For $0<n<K$, $F(n)>0$, so solutions increase monotonically toward $K$. For $n>K$, $F(n)<0$, so they decrease monotonically toward $K$. The solution $n=0$ remains at zero. Thus a phase-line sketch has arrows away from $0$ and toward $K$; a time-series sketch has all positive curves tending to the same horizontal asymptote $K$. This is the cubic saturation population model.

Solved by gpt-5.6-sol high.

With the same low-density rate and carrying capacity, the two per-capita growth rates arefor the cubic model andfor logistic growth. The logistic correction is linear in a small population, whereas the cubic correction is quadratic. Consequently the cubic trajectory initially follows pure exponential growth more closely and lies above the logistic trajectory before both approach $K$. Plotting measured per-capita growth against $n$ distinguishes a linear decline from a curve with zero slope at the origin.

Solved by gpt-5.6-sol high.

For singularities $a<c_1<\cdots <c_N<b$, the Cauchy principal value iswhere the assumed tail integrals make the two unbounded pieces meaningful. Equivalently, remove a symmetric interval of radius $\epsilon$ about each $c_j$ and take the limit of the remaining integral.

Solved by gpt-5.6-sol high.

Using the convention adopted here, the Hilbert transform isThe convention with denominator $x-y$ differs by a minus sign.

Solved by gpt-5.6-sol high.

For $f(x)=1/(x^2+1)$, contour integration or partial fractions givesunder the convention in part (b). Therefore

Solved by gpt-5.6-sol high.

Let $\theta$ be the angle from the downward vertical to the hoop's centre, measured at the suspension point, and let $\varphi$ be the absolute angle from the downward vertical to the bead's radius from the hoop centre. The bead position is the sum of two vectors of length $a$. Including the hoop's moment of inertia about the pivot giveswhileThus one suitable Lagrangian is

Solved by gpt-5.6-sol high.

To quadratic order about $\theta =\varphi =0$,andFor a normal mode, put $c={\omega }^{2}a/g$. The characteristic equation isso $c=1/2$ or $2$. The small oscillations of a hoop with a sliding bead therefore have

Solved by gpt-5.6-sol high.

The slow-roll equations implyFor $V=\lambda {\varphi }^n/n$, $V/V^{\prime }=\varphi /n$. Integrating from ${\varphi }_i$ and using $a({\varphi }_i)=1$ gives

Solved by gpt-5.6-sol high.

From $3H\dot{\varphi }=-c^2{V}^{\prime }$ and $H^2=8\pi GV/(3c^2)$,The slow-roll approximation fails when this kinetic contribution is comparable with $V$, giving

The number of e-folds isUsing the estimate above,For $n=6$ and the roughly $60$ e-folds needed for the flatness problem,This is the monomial slow-roll e-fold count.

Solved by gpt-5.6-sol high.

Let $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$. After the Hadamards and the oracle, Bernstein-Vazirani phase kickback gives

Solved by gpt-5.6-sol high.

The Walsh-Hadamard identityand $H|-⟩=|1⟩$ give

Solved by gpt-5.6-sol high.

A final oracle call evaluates $f$ on the definite input $a$:Since $a\cdot a$ modulo two is the parity of the Hamming weight of $a$, this form also determines the last-qubit measurement.

Solved by gpt-5.6-sol high.

The first register of $|{\Phi }_3⟩$ is exactly $|a⟩$, so the probability of observing the string $a$ is

Solved by gpt-5.6-sol high.

Measuring the first register does not disturb the product-state last register. Its state is

Solved by gpt-5.6-sol high.

If $a$ has odd Hamming weight, then $a\cdot a=1$ and the final bit is $b$, so the probability is $1$. If $a$ has even Hamming weight, then $a\cdot a=0$ and the final bit is $1\oplus b$, so the probability is $0$. Thus

Solved by gpt-5.6-sol high.

For a received word $y$, the ideal-observer rule chooses a message $i$ maximizing the posterior probabilityMaximum-likelihood decoding chooses $i$ maximizingand minimum-distance decoding chooses a codeword minimizing its Hamming distance from $y$.

Bayes' formula givesEqual message priors therefore make ideal-observer and maximum-likelihood decoding identical. On a binary symmetric channel, if $d=d_H(y,c_i)$, thenFor $p<1/2$, this strictly decreases with $d$, so maximum likelihood and minimum distance agree.

Solved by gpt-5.6-sol high.

Choose $\delta$ withA greedy packing construction gives binary length-$n$ codes of minimum distance greater than $2\delta n$ and size at leastTheir asymptotic rate is at leastwhere $h_2$ is binary Binary entropy. Minimum-distance decoding corrects every error pattern of weight at most $\delta n$. Since a channel error count is $\mathrm{Bin}(n,p)$, the law of large numbers givesThus a fixed positive rate is achievable with error tending to zero, proving that the operational capacity is nonzero. This is the positive-rate coding bound below one-quarter crossover.

Solved by gpt-5.6-sol high.

Shannon second coding theorem states that the operational capacity of a discrete memoryless channel equalsevery rate below $C$ is achievable with error probability tending to zero, while rates above $C$ are not.

Put $d=b-a$. If $d=0$, then $Y=X+a$, so $X$ is recovered exactly and $C=1$ bit. If $|d|\ge 2$, the two output supportsare disjoint, so again $Y$ determines $X$ and $C=1$.

If $|d|=1$, one output value is common to both inputs and occurs with probability $1/2$ independently of the input, while either of the other two values reveals the input. The channel is therefore a binary erasure channel with erasure probability $1/2$, whose capacity is $1/2$ bit. Hence

Solved by gpt-5.6-sol high.

The upper register index is the largest register number occurring in an instruction of $P$, with value zero if only register $0$ is used. A configuration records the current state and the contents of every register up to that index.

For input $\vec{w}$, let $C(0,M,\vec{w})$ be the initial configuration: the designated initial state, the words of $\vec{w}$ in the input registers, and the empty word in every remaining register. Recursively, if $C(t,M,\vec{w})$ is halting, keep it fixed; otherwise let $C(t+1,M,\vec{w})$ be the unique configuration into which $M$ transforms it. The resulting sequenceis the computation sequence.

Solved by gpt-5.6-sol high.

Choose an input word $w$ of length at least $n+1$. The final value $f_{M,1}(w)={\chi }_L(w)$ has length at most one. Every symbol initially in register $0$ must either be deleted or transferred elsewhere, and either action begins with a remove instructionNo other instruction can lower the length of register $0$. Consequently at leastsuch remove instructions occur in this computation. Since words of arbitrary length exist, the assertion follows.