Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 3

A reduced positive definite binary quadratic form $f=[a,b,c]=a{x}^2+bxy+c{y}^2$ satisfieswith $b\ge 0$ when $|b|=a$ or $a=c$. Its discriminant of a binary quadratic form is $d=b^2-4ac<0$. The first displayed inequality already gives $|b|\le a$, while $c\ge a$ givesTaking the positive square root yieldsMoreover, $d=b^2-4ac\equiv b^2\equiv b(\mathrm{mod}2)$, so $b\equiv d(\mathrm{mod}2)$. For fixed negative $d$, the displayed bounds leave only finitely many possible integers $a$ and $b$, and then $c=(b^2-d)/(4a)$ is uniquely determined. Hence only finitely many reduced forms have discriminant $d$.

For $d=-15$, the bound gives $a\le \sqrt{5}$, so $a\in \{1,2\}$. The modular congruence condition makes $b$ odd. If $a=1$, then $b=\pm 1$ and $c=4$; the boundary convention $|b|=a\Rightarrow b\ge 0$ retains $[1,1,4]$. If $a=2$, then $b=\pm 1$ and $c=2$; the boundary convention $a=c\Rightarrow b\ge 0$ retains $[2,1,2]$. Thus the complete list is

Nash's theorem says that every finite game, including a two-player game with two pure choices each, has at least one Nash equilibrium in mixed strategies.

For player $1$, holding $p_2$ fixed, the expected value of the payoff isIt is an affine function of $p_1$. Therefore player $1$ chooses $p_1=1$ when $1-(U-1)p_2>0$, chooses $p_1=0$ when it is negative, and is indifferent when it vanishes. By symmetry, player $2$ has the analogous best response.

If $U<2$, then $1-(U-1)p>0$ for every $p\in [0,1]$, so becoming a Dark Lord with probability one is a strictly dominant strategy. The unique equilibrium isIf $U>2$, each player is indifferent when the other chooses $p=1/(U-1)$. This gives one interior mixed equilibrium, while the two asymmetric pure equilibria arise because a player facing a certain peasant chooses Lord and a player facing a certain Lord chooses peasant. The three equilibria areConsequently $\boxed{U_0=2}$. At the threshold itself there is a continuum of equilibria with $p_1=1$ or $p_2=1$, consistent with the question's strict inequalities.

A reliable transmission rate $R$ means that length-$n$ codes can carry $M_n$ messages with $n^{-1}{\log }_2{M}_n$ tending to at least $R$ while the probability measure of the decoding-error event tends to zero. By the Shannon second coding theorem, the supremum of reliable rates is the binary symmetric channel capacityFor small positive $p$, the binary entropy function has the asymptotic expansionso $C(p)$ starts at one bit per channel use and decreases rapidly from one as errors are introduced.

At $p=1/2$, the output of the binary symmetric channel is independent of its input. It conveys no mutual information, and therefore

If $p>1/2$, complementing every received bit converts the channel into a binary symmetric channel with crossover probability $1-p<1/2$. This deterministic and invertible output relabelling does not change the channel capacity. Since $h_2(p)=h_2(1-p)$,Thus the capacity rises again from zero as $p$ increases beyond $1/2$, reaching one at $p=1$, where every bit is flipped deterministically and can be recovered by complementation.

A context-free grammar is in Chomsky normal form when every production is of one of the formswhere $A,B,C$ are nonterminal symbols and $a$ is a terminal symbol. Under this strict convention there is no epsilon production, so such a grammar cannot generate the empty word. Conversion of an arbitrary grammar therefore givesIf $ϵ\notin \mathcal{L}(G)$, the two languages are equal. An alternative extended convention permits the exceptional start production $S_0\to ϵ$; under that convention conversion preserves the whole language.

Use the CYK algorithm. For a nonempty input word $v=v_1\cdots v_n$, let $T_{i,j}$ be the set of nonterminals that derive the substring $v_i\cdots v_j$. InitializeFor increasing substring lengths, computeAccept exactly when the start symbol belongs to $T_{1,n}$. The proof is a mathematical induction on substring length: a one-letter derivation uses a terminal production, while every longer parse tree has a root production $A\to BC$ whose two subtrees yield two adjacent nonempty substrings. The recurrence considers every possible split point and therefore finds exactly all possible roots. For a fixed grammar the algorithm uses $O(n^3)$ time. Under the strict form in part (a), it rejects $ϵ$ immediately.

Introduce nonterminals for the terminals and one for the pair $bb$:Because the original start symbol occurs on a right-hand side, take a fresh start symbol $S_0$. After eliminating the unit production $S\to T$, one grammar in Chomsky normal form isThe original grammar generates exactlyThe displayed grammar generates the same set: $AS$ adds an $a$ on the left, $SU$ adds one $bb$ pair on the right, and $CC$ terminates the derivation with $cc$. Since the original grammar does not generate $ϵ$,

Writing the log-likelihood as $\ell (\beta )=\log L(\beta )$, the Fisher information matrix is the expected negative Hessian matrixUnder the usual regularity conditions it is equivalently the expected outer product of the score function.

For independent observations from an exponential dispersion family with common known dispersion parameter ${\sigma }^2$, the generalized linear model log-likelihood iswhere ${\mu }_i=b^{\prime }({\theta }_i)$ and the link function satisfies $g({\mu }_i)={\eta }_i=x_i^T\beta$.

For the canonical link function, ${\theta }_i={\eta }_i=x_i^T\beta$. Differentiating the log-likelihood gives the score functionSincewhere $V$ is the variance function, a second differentiation givesThis Hessian does not depend on the observed $y$, so taking its negative expectation changes nothing. Hence

With the travelling wave coordinate $\xi =x-ct$, the reaction-diffusion system becomesAt the advancing leading edge the healthy-tissue density is small. Put $f(\xi )\sim e^{-\lambda \xi }$ with $\lambda >0$. The linearization at $f=0$ givesso a nonoscillatory decaying front requires real positive roots,The pulled travelling front selects the Fisher-KPP minimum wave speed, and therefore

For the initial wound $0<x<W$, two mirror-image fronts enter from its endpoints. The left front moves right from $x=0$ and the right front moves left from $x=W$, each with speed approximately $c_{\min }$. A sequence of sketches would show the initial rectangular depression becoming two smooth monotone transition layers, the zero-density plateau shrinking, and the two layers meeting near $x=W/2$ before the profile relaxes to $S=1$. Their meeting time isThere is an additional local relaxation time of order $1/r$ if “close to one” is assigned a fixed numerical tolerance, so the displayed estimate is the dominant healing time when $W$ is large compared with the front width $\sqrt{D/r}$.

Differentiating under the contour integration sign givesSince ${\partial }_t{e}^{zt}=z{e}^{zt}$, integration by parts turns this intoThe integral vanishes whenHence, up to an irrelevant multiplicative constant,The remaining endpoint condition isThus each open end of $\gamma$ must lie where $\mathrm{Re}(zt-1/t)\to -\infty$; a closed contour also makes the boundary term vanish when the integrand is single-valued along it.

One possible open contour begins at $t=0$ along a ray with $\mathrm{Re}(1/t)>0$, avoids the essential singularity at the origin, and ends at infinity along a ray with $\mathrm{Re}(zt)<0$. For example, when $z>0$ is real, it may leave the origin along the positive real axis, bend through the upper half-plane, and approach the negative real axis as $|t|\to \infty$. At its initial end, $e^{-1/t}\to 0$; at its final end, $e^{zt}\to 0$. More generally, the terminal ray may be chosen withso that $zt$ is negative real. This contour satisfies the endpoint condition from part (a) and therefore produces a solution of the differential equation.

LetAn orbit of energy $E>0$ is an ellipse in phase space, with intercepts $x=\pm \sqrt{2E/(m{\omega }^2)}$ and $p=\pm \sqrt{2mE}$. Its enclosed area is $2\pi E/\omega$, so the action variable isThe transformationis canonical and gives the action-angle variables. Substitution yields

The adiabatic invariance of the action applies when the frequency changes by only a small fraction during one oscillation and no separatrix is encountered. A convenient condition isThenConsequentlyIf $A$ is the displacement amplitude, $E=\frac{1}{2}k{A}^2$, and henceThus a slowly stiffened spring raises the energy as $k^{1/2}$ while reducing the amplitude as $k^{-1/4}$.

Let $M(r)$ be the enclosed mass. A spherical shell of thickness $dr$ has inward gravitational acceleration $GM(r)/r^2$, so hydrostatic equilibrium requiresWith $\rho =A{r}^{2}P$, these equations reduce toFor a regular central value $P(0)=P_c>0$, the first equation integrates toThe exponential function is strictly positive at every finite $r$, so the pressure and density cannot reach zero at a finite stellar surface. The equations may describe an atmosphere whose density decreases at large radius, but they admit no nontrivial hydrostatic star of finite radius. Therefore

Because $H_n|0^n⟩=|{\psi }_0⟩$,which is the reflection operator in the line spanned by $|{\psi }_0⟩$. Meanwhile $I_G$ changes the sign of every good basis state and fixes every bad basis state; onit is the reflection in the $|{\psi }_B⟩$ axis. Both reflections preserve $\mathcal{P}$, so their product $Q$ does too.

WriteIn Euclidean geometry, the composition of reflections in two lines through the origin has a rotation matrix through twice the oriented angle between the lines. Hence $Q$ rotates the good-bad plane by $2\theta$ from $|{\psi }_B⟩$ toward $|{\psi }_G⟩$. In particular, the Grover rotation angle formula is

When $k=N/4$,One Grover search algorithm iteration therefore givesThe selective sign change $I_G$ is implemented with one application of the Boolean quantum oracle: prepare its answer qubit in $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$ and use quantum phase kickback, obtaining $(-1{)}^{f(x)}$ on each $|x⟩$. The remaining operations $H_n$, $I_0$, and the final computational-basis measurement are independent of $f$. Measurement of $|{\psi }_G⟩$ returns some $x\in G$ with probability one, so exactly one query to $U_f$ suffices.

A primitive root modulo $p$ is an integer $g$ whose residue class generates the multiplicative group of a finite field ${\mathbb{F}}_p^{\times }$. Equivalently, its multiplicative order modulo $p$ is $p-1$, so

For $k=0$, the convention $0^0=1$ gives $S_0=p\equiv 0(\mathrm{mod}p)$. Now suppose $1\le k<p-1$ and choose a primitive root $g$ modulo $p$. The nonzero residues are $g^j$ for $0\le j\le p-2$, while the $x=0$ term vanishes. HenceThis is a finite geometric series. Since $g^k\not\equiv 1(\mathrm{mod}p)$ but $g^{k(p-1)}\equiv 1(\mathrm{mod}p)$ by Fermat's little theorem, multiplication by the nonzero residue $g^k-1$ givesThe factor $g^k-1$ is invertible modulo the prime number $p$, so

By Fermat's little theorem,Thus the sum of $g$ over ${\mathbb{F}}_p^3$ counts, modulo $p$, the triples on which the ternary quadratic form $f$ vanishes.

Expand $f^{p-1}$ with the multinomial theorem. A term indexed by $r+s+t=p-1$ contributes a constant multiple ofAt least one of $r,s,t$ is strictly less than $(p-1)/2$. Its corresponding exponent is therefore in $\{0,1,\dots ,p-2\}$, so part (b), including its $k=0$ case, makes that power sum zero modulo $p$. Every term in the expansion consequently vanishes after summation. The constant term contributes $p^3\equiv 0$, and therefore

The zero triple is one solution of $f=0$. If it were the only solution, the displayed sum would be congruent to $1$ rather than $0$. Hence there is another triple $(x,y,z)$, not all divisible by $p$, satisfying

Fix an acceptable effective enumeration $f_{e,n}$ of the $n$-ary partial computable functions. The S-m-n theorem states that for every $m,n\ge 1$ there is a total computable function $s_n^m$ such thatwhere $\simeq$ means that both sides have the same value when defined and are otherwise both undefined.

The recursion theorem states that every total computable transformation $h$ of program indices has a semantic fixed point: there is an $e$ such that

Rice theorem says that every nontrivial extensional property of programs computing partial functions is undecidable. Equivalently, a nontrivial index set cannot be a computable set.

Let $A$ be such an index set. Replacing $A$ by its complement if necessary, assume that the nowhere-defined function has no index in $A$. Since the property is nontrivial, choose an index $a\in A$. If membership in $A$ were decidable, we could decide the diagonal halting problem as follows. For each $x$, defineBy the S-m-n theorem, a total computable function $q$ produces an index $q(x)$ for ${\psi }_x$. If $f_{x,1}(x)$ diverges, then ${\psi }_x$ is nowhere defined and $q(x)\notin A$. If it halts, then ${\psi }_x\simeq f_{a,1}$ and extensionality gives $q(x)\in A$. A decider for $A$ would therefore decide whether $f_{x,1}(x)$ halts, a contradiction. Hence $A$ is undecidable.

Apply the S-m-n theorem to $g$. It gives a total computable function $h$ such thatThe recursion theorem supplies an index $e$ satisfying $f_{e,1}\simeq f_{h(e),1}$. Consequently

For each $x$, let $h(x)$ be an effectively obtained index of the partial functionThe existence of the total computable index transformation $h$ follows from the S-m-n theorem. By the recursion theorem, some $m$ satisfies $f_{m,1}\simeq f_{h(m),1}$. Therefore its domain isand hence

No. The propertyis an index set: it depends only on the domain $W_n$ of the partial function computed, not on the syntax of its program. It is nontrivial. For example, an index whose domain is a singleton belongs to $\mathcal{S}$, whereas an index whose domain has two elements does not. The Rice theorem therefore shows that $\mathcal{S}$ is not a computable set, so no algorithm can decide the requested property for arbitrary $n$.

Invoking the Church–Turing thesis, this also rules out any effective procedure in the informal sense, because such a procedure would be represented by a computable function.

This is an immigration--death process. New individuals enter independently of the current population at the constant rate $\lambda$, producing transitions $n\to n+1$. Each existing individual dies at rate $\beta$, so the total transition rate $n\to n-1$ is $\beta n$.

Multiply the master equation by $s^n$ and sum over $n\ge 0$. For the immigration terms,For the death terms, shifting the first sum givesTherefore the probability generating function obeys

The normalized ansatz intended in the question isfor which $\varphi (1,t)=1$. Substitution into the equation from part (ii) and cancellation of $(s-1)\varphi$ gives the linear ordinary differential equationThusThis generating function is that of a Poisson distribution with parameter $f(t)$. Equivalently, differentiating at $s=1$ givesConsequently