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

Starting at $r=\lceil \sqrt{14351}\rceil =120$, one immediately findsTherefore

Solved by gpt-5.6-sol high.

Since $N=3p$, its nontrivial difference-of-squares representation isAs $p$ is prime, every earlier square difference would give another nontrivial factorization, which is impossible. Thus the first successful value is $r=(p+3)/2$, and

Solved by gpt-5.6-sol high.

Liouville approximation theorem states that if an irrational algebraic number $\alpha$ has degree $d\ge 2$, then some $C(\alpha )>0$ satisfiesfor every rational $p/q$ with $q>0$.

The omitted $n=0$ term is rational and does not affect transcendence. LetThe decimal expansion has ones at the increasingly separated positions $n^n$ and zeros elsewhere, so it is not eventually periodic and $\xi$ is irrational. Moreover,For every fixed $d$, the exponent $(N+1{)}^{N+1}$ eventually exceeds $d{N}^N$ by an arbitrarily large amount, so this upper bound is smaller than $C{q}_N^{-d}$. Liouville's theorem therefore rules out every finite algebraic degree, proving that $\xi$ is transcendental.

There are only countably many integer polynomials and each has finitely many roots, so the algebraic numbers are countable. Since $\mathbb{R}$ is uncountable, its complement, the set of transcendental numbers, is uncountable.

Solved by gpt-5.6-sol high.

For a binary prefix code with word lengths $l_1,\dots ,l_m$, choose $L\ge \max l_i$. Each codeword is the prefix of exactly $2^{L-l_i}$ words of length $L$, and these descendant sets are disjoint. HenceThis is Kraft inequality. Conversely, if integer lengths satisfy this inequality, place words greedily as leaves of the binary tree; the unused capacity ensures that the requested leaves can all be chosen, giving a prefix code.

For Shannon--Fano coding, order symbols by probability and assignKraft's inequality applies because $2^{-l_i}\le p_i$ and therefore ${\sum }_i{2}^{-l_i}\le 1$. Thus codewords of those lengths exist. Sincethe expected length obeys

Solved by gpt-5.6-sol high.

The closure table is

For the context-free intersection failure, takeBoth are context-free, but $L_1\cap L_2=\{a^n{b}^n{c}^n:n\ge 0\}$ is not. If context-free languages were also closed under complement, their closure under union and De Morgan's law would imply closure under intersection, so complement closure also fails. Finally, the halting set is computably enumerable but its complement is not, disproving complement closure for computably enumerable languages.

Solved by gpt-5.6-sol high.

The change of variable $x=(y/\lambda {)}^k$ has derivative $kx/y$, soFor fixed $k$ this isThus the sample's sufficient statistic is $T={\sum }_i{Y}_i^k$.

Since $(Y/\lambda {)}^k\sim \mathrm{Exp}(1)$,The log likelihood, up to constants, is $-kn\log \lambda -T/{\lambda }^k$. Differentiating gives the unique maximum

Solved by gpt-5.6-sol high.

The $\beta YN$ interaction converts supporters into opponents. The $\alpha YN$ interaction converts opponents into undecided people, while $\zeta U$ converts undecided people into opponents. Summing the three equations gives $(Y+N+U{)}^{\prime }=0$, as required for a fixed population.

Solved by gpt-5.6-sol high.

Let the conserved population be $S>0$. At equilibrium $Y^{\prime }=-\beta YN=0$, so $Y$ and $N$ cannot both be positive. The other equations then force $U=0$. The only equilibria are

Near $E_Y$, using $(N,U)$ as coordinates gives the linearizationIts determinant is $-\beta S\zeta <0$, so $E_Y$ is a saddle and is unstable. Near $E_N$, coordinates $(Y,U)$ give the triangular linearization with eigenvalues $-\beta S$ and $-\zeta$. Hence $E_N$ is asymptotically stable.

Solved by gpt-5.6-sol high.

No positive parameter choices can make everyone eventually favour the proposition for every initial condition. The all-opposed state $E_N$ is itself an equilibrium, and part (b) shows that an entire neighborhood is attracted to it. Thus initial conditions in that neighborhood cannot converge to $E_Y$.

Solved by gpt-5.6-sol high.

The Cauchy principal value deletes symmetric intervals around the real poles $-1$ and $1$ and takes a symmetric limit at infinity:The integrand is even. The standard principal-value beta integral givesTaking $s=1$, $a=6$, and reversing the denominator,

Solved by gpt-5.6-sol high.

The Lagrangian isWriting $T=2m+M$, the center of mass isAll internal forces cancel, so $\ddot{Y}=-g$ andIf the molecule is released from rest, the middle term vanishes.

Solved by gpt-5.6-sol high.

Since $y_1=(Q_s+Q_a)/2$, $y_3=(Q_s-Q_a)/2$, elimination of the middle coordinate by the center of mass givesAfter substitution,The antisymmetric coordinate is decoupled. Its Euler--Lagrange equation is

Solved by gpt-5.6-sol high.

Successive radial wave crests travel the same fixed comoving distance, soTo first order, $\delta t_0/a(t_0)=\delta t_e/a(t_e)$. Since wavelength is proportional to the period,

Solved by gpt-5.6-sol high.

Each photon loses a factor $(1+z{)}^{-1}$ in energy, and cosmological time dilation reduces the photon arrival rate by another factor $(1+z{)}^{-1}$. Henceso $n=2$. The physical area of the sphere today is $4\pi a(t_0{)}^2{x}^2$, giving flux

Solved by gpt-5.6-sol high.

Immediately before the final Hadamard, the state isThe outcome-one component after that Hadamard is $(|\psi ⟩+iU|\psi ⟩)/2$. Thus, with $z=⟨\psi |U|\psi ⟩$,

Solved by gpt-5.6-sol high.

For every product vector,Product vectors span the two-register state space, so the single $A\otimes B$ gate equals parallel application of $A$ to the first register and $B$ to the second. Unitarity guarantees that both descriptions are valid quantum circuits.

Solved by gpt-5.6-sol high.

Both $Z\otimes Z$ and $X\otimes I$ are unitary and Hermitian, so their expectations are real. Run the real-part Hadamard test twice, once with controlled $Z\otimes Z$ and once with controlled $X\otimes I$. If the respective ancilla outcome-one probabilities are $p_{ZZ}$ and $p_{XI}$, thenThe identity in part (b) implements each controlled tensor product by gates on its two target wires with the common control. By linearity,

Solved by gpt-5.6-sol high.

Huffman's algorithm repeatedly merges the two least probable current symbols, labels the two new edges $0,1$, and replaces the pair by a compound symbol whose probability is their sum. Reading paths from the final root gives a prefix code.

For optimality, first observe that in some optimal full binary tree the two least probable symbols are sibling leaves at maximum depth: exchange them with any deepest sibling pair, putting the smaller probabilities at no smaller depths, without increasing expected length. Contract that sibling pair to one symbol of combined probability. The original expected length equals the contracted tree's expected length plus the pair's combined probability. Induction on the alphabet size now proves that choosing the two least probabilities and recursing is optimal, which is precisely Huffman's algorithm.

If a symbol has length one, it must be $a_1$. At the three-weight stage, the other two weights $x,y$ must be merged while $p_1$ survives, so $x,y\le p_1$. Thus $1-p_1=x+y\le 2p_1$, proving $p_1\ge 1/3$. Therefore $p_1<1/3$ forces every length to be at least two.

For the other bound, suppose $p_1$ is first merged at the three-weight stage, with weights $p_1,q,r$, where $q\le p_1\le r$. The preceding merge created $r=x+y$ from two weights no larger than the surviving $q$, so $r\le 2q$. Since also $r\ge p_1$, we have $q\ge p_1/2$, and henceThus this can happen only when $p_1\le 2/5$. If $p_1>2/5$, it survives until the final merge and receives a length-one word. At equality, ties can support either tree shape.

For code (a), takeHuffman merging produces lengths $(1,2,3,3)$ and expected length $2$.

Solved by gpt-5.6-sol high.

For the same distribution $(2/5,1/5,1/5,1/5)$, the balanced code has every length equal to two and hence expected length $2$. Part (a) exhibited a Huffman code with that same expected length, so the balanced code is also optimal. Thus both listed codes are optimal for this distribution, after assigning their words in nondecreasing length order to nonincreasing probabilities.

Solved by gpt-5.6-sol high.

For $C,D\subseteq \mathbb{B}$, one writes $C{\le }_{m}D$ if there is a total computable function $f:\mathbb{B}\to \mathbb{B}$ such thatfor every $x$. This is a computable many-one reduction.

Solved by gpt-5.6-sol high.

One writes $C{\equiv }_{m}D$ when both $C{\le }_{m}D$ and $D{\le }_{m}C$.

Solved by gpt-5.6-sol high.

Fix an effective coding of machines and write $W_w$ for the computably enumerable language recognized by code $w$. A set $I$ of codes is an index set when membership depends only on the recognized language:It is nontrivial when it is neither empty nor all of $\mathbb{B}$.

Solved by gpt-5.6-sol high.

Let $K=\{w:w\in W_w\}$ and let $e_{\varnothing }$ be any index for the empty language. The proof of Rice theorem givesIn either case choose a language on the opposite side of the nontrivial property and switch from the empty enumerator to its enumerator if the simulated diagonal computation halts.

Solved by gpt-5.6-sol high.

The empty language belongs to $\mathbf{Emp}$, so the second case applies:It does not belong to $\mathbf{Inf}$, so the first case applies:

Solved by gpt-5.6-sol high.

The set of codes of even length is not an index set because code length is syntactic rather than a property of $W_w$. By the padding lemma, every computably enumerable language has equivalent machine descriptions of arbitrarily many lengths, in particular descriptions of both parities. Hence equal recognized languages need not give equal membership.

Solved by gpt-5.6-sol high.

Since the empty language does not lie inRice's construction gives $K{\le }_m\mathbf{Two}$. Conversely, $\mathbf{Two}$ is computably enumerable: dovetail the enumerator for $W_w$ until two distinct words appear, then accept. The diagonal halting set $K$ is many-one complete for computably enumerable sets, so $\mathbf{Two}{\le }_{m}K$. Therefore

Solved by gpt-5.6-sol high.

For $K{\le }_m\mathbf{Cof}$, map $x$ to a machine that initially enumerates nothing and, if the simulation establishing $x\in K$ halts, enumerates every word. Its language is cofinite exactly when $x\in K$.

For $\mathbb{B}\setminus K{\le }_m\mathbf{Cof}$, map $x$ to a machine that enumerates successively longer finite initial segments of $\mathbb{B}$ while simulating $x$. If the simulation never halts, every word is eventually enumerated; if it halts, enumeration stops with a finite language and therefore an infinite complement. Thus the constructed language is cofinite exactly when $x\notin K$.

The parameter theorem makes both code transformations total and computable.

Solved by gpt-5.6-sol high.

Conditionally on $X$, the log likelihood differs fromonly by terms independent of $\beta$. Differentiation gives the weighted normal equationsand therefore

Solved by gpt-5.6-sol high.

Dividing row $i$ of both $Y$ and $X$ by $\sqrt{v(X_i)}$ transforms the model to one with covariance ${\sigma }^{2}I$. Ordinary least squares without an intercept on these transformed data is exactly the estimator in part (a). In R, the unweighted estimator is returned by

R
fit2 <- lm(Y ~ X - 1)
fit2$coefficients

Solved by gpt-5.6-sol high.

Write $Y_i=X_i^T\beta +{\epsilon }_i$, where conditionally $\mathbb{E}({\epsilon }_i|X_i)=0$ and $\mathrm{Var}({\epsilon }_i|X_i)={\sigma }^{2}v(X_i)$. ThenThe law of large numbers sends the matrix towhile the vector tends to zero, proving consistency. The central limit theorem and Slutsky's theorem give

Similarly, with $B=\mathbb{E}(X{X}^T)$ and $C=\mathbb{E}(v(X)X{X}^T)$,These conclusions require the displayed matrices to be finite and nonsingular.

Solved by gpt-5.6-sol high.

For $p=1$, part (c) givesConsequently

Solved by gpt-5.6-sol high.

Weighted least squares uses the known conditional variances and should be at least as efficient, so $\rho \le 1$. Indeed, apply Cauchy--Schwarz toIt giveswhich is exactly $\rho \le 1$. Equality holds precisely when $v(X_1)$ is constant on the part of the support where $X_1\ne 0$, up to null sets.