Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 2

Write the continued fraction as $\theta =[a_0;a_1,a_2,\dots ]$ and define its convergents byInduction using these recurrences givesIn particular, consecutive convergents have coprime numerator and denominator. The standard best-approximation consequence of the same determinant identity is that, for $0<q\le q_n$ and $p/q\ne p_n/q_n$,Dividing by $q\le q_n$ givesThe contrapositive proves that any strictly better approximation has $q>q_n$.

For $\sqrt{12}$, the continued-fraction algorithm givesand the remainder then repeats. HenceThe convergent $[3;2]=7/2$ supplies a solution of the Pell equation:

The Legendre polynomial $p_n$ is orthogonal on $[-1,1]$ to every polynomial of degree below $n$. Suppose it changes sign at only $r<n$ distinct interior points $x_1,\dots ,x_r$, and putchoosing its overall sign so that $p_{n}q\ge 0$ on $[-1,1]$. This product is positive except at finitely many points, socontradicting orthogonality because $\mathrm{deg}q=r<n$. Thus $p_n$ has at least $n$ sign-changing roots in $(-1,1)$; its degree is $n$, so these are all its roots and they are distinct.

For arbitrary distinct nodes $x_1,\dots ,x_n$, letbe the Lagrange basis polynomials. Every polynomial $P$ of degree below $n$ satisfies $P(t)={\sum }_{i}P(x_i)L_i(t)$, so the required weights exist and areThey are unique because applying any such formula to $P=L_i$ recovers $A_i$.

Now assume exactness for every $P$ of degree below $2n$ and define $Q(t)={\prod }_i(t-x_i)$. For every polynomial $R$ of degree below $n$, the product $QR$ has degree below $2n$ and vanishes at every node. ThereforeThere is a unique monic polynomial of degree $n$ orthogonal to all lower-degree polynomials, so $Q$ is the monic normalization of $p_n$ and the $x_i$ are precisely the roots of $p_n$. Taking $P=1$ givesFinally $L_i^2$ has degree $2n-2$, so exactness givesThese are the positive weights of Gaussian quadrature.

For a discrete memoryless channel with input $X$ and output $Y$, its information capacity iswhere $I(X;Y)$ is the mutual information and the maximum is over all input distributions. Capacity is measured in bits when logarithms have base two.

With rows indexed by outputs $A,B,\star$ and columns by inputs $A,B$, the channel matrix isThis is a binary erasure channel with erasure probability $1/2$. Conditional on no erasure, the input is recovered exactly, whereas an erasure supplies no information. Thuswhich is maximized by the uniform input distribution. Therefore

Let $q=\mathbb{P}(X=B)$. The merged channel is a Binary Z-channel: its second output occurs with probability $q/2$, while the output has one bit of uncertainty only when $X=B$. In terms of the binary entropy function $h_2$,At an interior maximum,so $(2-q)/q=4$ and $q=2/5$. Consequently

A subset $E\subseteq \mathbb{N}$ is recursive when its indicator function is a total computable function. It is recursively enumerable when it is the domain of a partial computable function, equivalently when an algorithm can enumerate its members.

If $E$ is recursive, its indicator decides both $E$ and its complement, so both sets are recursively enumerable. Conversely, suppose programs enumerate $E$ and $\mathbb{N}\setminus E$. On input $n$, run the two enumerations in parallel by dovetailing. Exactly one must eventually print $n$; accept in the first case and reject in the second. This algorithm always halts and decides $E$. Hence

The setis the diagonal halting set. It is recursively enumerable by simulating the coded machine, but it is not recursive by the halting problem diagonal argument.

By contrast, ${\mathbb{K}}_{100}$ is recursive: decode $n$, reject it if it is not a program code, otherwise simulate the program on input $n$ for exactly $100$ steps and accept precisely if it has halted. This bounded computation always terminates. Thus

Let $Y_i$ be the indicator that man $i$ develops heart disease and let ${\pi }_i=\mathbb{P}(Y_i=1)$. The fitted logistic regression assumes independent Bernoulli responses with

Two packs contain $40$ cigarettes. Holding height fixed, increasing average consumption from zero to two packs per day changes the log odds byThe corresponding odds ratio is thereforeThus the model estimates that a two-pack-per-day smoker has about $2.52$ times the odds of heart disease of an otherwise comparable nonsmoker. This is an association in the fitted observational model, rather than by itself a causal conclusion.

Let ${\epsilon }_i$ be independent standard logistic random variables and define the latent variableSet $Y_i=1$ exactly when $Z_i>0$. If $F$ is the logistic cumulative distribution function, its symmetry and the identity $F^{-1}(p)=\mathrm{logit}(p)$ givewhich is precisely the fitted logistic regression.

At a nonzero fixed point, both bracketed per-capita growth rates vanish:Hence the coexistence equilibrium of this Lotka-Volterra predator-prey model is

Since $N_i=N_i^{\ast }{e}^{x_i}$, division of each population equation by $N_i$ givesDefine the Hamiltonian functionand the antisymmetric matrixThen

Along a solution, the chain rule and antisymmetry of $K$ givebecause $v^{T}Kv=0$ for every real vector $v$. ThereforeThe closed level curves around the strict minimum at the coexistence equilibrium are the periodic population cycles of the Lotka-Volterra predator-prey model.

The poles of ${\csc }^{3}z$ inside $|z|=4$ are $z=-\pi ,0,\pi$. Near $z=k\pi$, write $z=k\pi +w$. Its Laurent series beginsso the residue is $(-1{)}^k/2$. The sum of the three residues isThe positively oriented residue theorem now gives

If $\mathbf{r}$ is measured in the rotating frame, its inertial velocity is $\dot{\mathbf{r}}+\mathbf{\omega }\times \mathbf{r}$. The masses producing the gravitational field are stationary in this frame, so their potential energy is a time-independent function $V(\mathbf{r})$. Thus kinetic minus potential energy gives the stated LagrangianPut $\mathbf{v}=\dot{\mathbf{r}}+\mathbf{\omega }\times \mathbf{r}$. ThenSubstitution in the Euler-Lagrange equation yieldsThe extra terms are the Coriolis acceleration, Euler acceleration, and centrifugal acceleration of a rotating reference frame.

The canonical momentum and Hamiltonian areAccordingly, Hamilton's equations are

Under the slow-roll approximation,For $V=m^2{\varphi }^2/2$ and the branch $\varphi >0$, setThen $H\simeq Am\varphi$ andWith $\varphi (0)={\varphi }_0$ and $a(0)=a_0$,and integrating $\dot{a}/a=H$ gives

For $V=\lambda {\varphi }^4/4$ and $\varphi >0$, putThe slow-roll approximation gives $H\simeq B{\varphi }^2$ andTherefore, with $\gamma =c\sqrt{\lambda /(6\pi G)}$,Since $B/\gamma =2\pi G/c^2$, integration of the Hubble parameter gives

The controlled-NOT gate sends $|0x⟩$ to $|0x⟩$ and $|1\bar{x}⟩$ to $|1x⟩$. HenceSince the Hadamard gate satisfies $H^2=I$,

The required identity isthe first exponent in the scanned statement should be $z$. Indeed, $X^x$ changes the parity label from $0$ to $x$, while $Z^z$ multiplies the component whose first qubit is $1$ by $(-1{)}^z$, creating the phase label. Equivalently, the hint permits either one-qubit operator to be transferred to the second half of the Bell state by transposition.

This is superdense coding. To send the two classical bits $(z,x)$, Alice applies $Z^z{X}^x$ to her half of the shared Bell state $|{\beta }_{00}⟩$, producing $|{\beta }_{zx}⟩$, and sends that one qubit to Bob. Bob applies $\mathrm{CX}$ followed by $H$ on the first qubit, as in part (i), and measures both qubits in the computational basis. The outcome is $zx$ with certainty, so one transmitted qubit communicates two classical bits using the previously shared quantum entanglement.

Label the edges so that barycentric coordinates on $T$ satisfySuppose for contradiction that $A\cap B\cap C=\varnothing$. The distance from a point to a closed set gives continuous nonnegative functions $d_A,d_B,d_C$. Their sum never vanishes, while at every point at least one of them vanishes because $A\cup B\cup C=T$. Henceis a continuous map from $T$ to its boundary in barycentric-coordinate space. Moreover, $F(I)\subseteq I$, $F(J)\subseteq J$, and $F(K)\subseteq K$. On each edge, the straight-line homotopy between $F$ and the identity remains in that edge, so $F{|}_{\partial T}$ has winding number one. On the other hand, a map from the whole triangle to its boundary makes its boundary restriction null-homotopic, and hence gives winding number zero. This contradiction proves the three-set covering lemma:

If a retraction $f:D\to \partial D$ fixed every boundary point, choose a homeomorphism from $T$ to $D$ taking its three edges to three consecutive closed arcs of $\partial D$ with empty triple intersection. The inverse images under $f$ of those arcs would be closed, would cover $D$, and would contain the corresponding boundary arcs. Transporting them to $T$ would contradict the result just proved. Therefore

For the final statement, use compactness of the three closed arcs inside the corresponding open sets. A finite open cover of a compact metric space admits a closed shrinking, and the shrinking can be chosen to preserve specified compact subsets already lying in the respective open sets. Thus there are closed setswhich cover $D$ and contain $\alpha ,\beta ,\gamma$, respectively. The disc version of the three-set covering lemma, obtained from the triangle by a homeomorphism taking its edges to the three arcs, gives a point in $A\cap B\cap C$. Since these sets lie in the original open sets,

The columns of the parity-check matrix of the binary Hamming code are precisely the $n=2^d-1$ distinct nonzero vectors of ${\mathbb{F}}_2^d$. If $h_1\ne h_2$, then $h_1+h_2$ is nonzero and differs from both summands, so it occurs as a unique third column $h_3$.

A word supported on three positions is a codeword exactly when the corresponding three columns sum to zero. Every unordered pair of columns determines one such triple, and each triple is counted once by each of its three pairs. Therefore

Sum all nonzero vectors of ${\mathbb{F}}_2^d$. In each coordinate, exactly $2^{d-1}$ vectors have entry one, which is even because $d>1$. The sum is therefore zero, soThus the all-one word belongs to the Hamming code and has Hamming weight $n$.

Adding the all-one codeword is a bijection from $C$ to itself, and it replaces every bit by its complement. It therefore sends weight $j$ to weight $n-j$, provingThe code has one word of weight zero and, since its minimum Hamming distance is three, no words of weight one or two. Combining this with part (i) gives

The string is initially at rest, so $y(x,0)=y_t(x,0)=0$. Taking the Laplace transform in $t$ converts the wave equation intoFor $\mathrm{Re}p>0$, the solution that decays as $x\to \infty$ is $\hat{y}=A(p)e^{-px/c}$. The transformed boundary condition $\hat{y}(0,p)=\hat{f}(p)$ fixes $A=\hat{f}$, and therefore

For $f(t)=\sin \omega t$,The Bromwich inversion formula givesWhen $t>x/c$, close the contour to the left. The residues at $p=\pm i\omega$ sum to $\sin (\omega (t-x/c))$. When $t<x/c$, close it to the right, where there are no poles, and the integral vanishes. HenceEquivalently, $y(x,t)=\Theta (t-x/c)\sin (\omega (t-x/c))$ in terms of the Heaviside step function. The boundary oscillation travels to the right at wave speed $c$ without reflection or dispersion; a point at $x$ begins moving after the propagation delay $x/c$.

In the Euler angles for a symmetric top convention, $\theta$ is the inclination of the body symmetry axis ${\mathbf{e}}_3$ from the fixed vertical, $\varphi$ is the azimuth of the line of nodes in the fixed horizontal plane, and $\psi$ is rotation about ${\mathbf{e}}_3$ measured from that line:

The coordinates $\varphi$ and $\psi$ are cyclic, so their canonical momenta are conserved:Because the Lagrangian has no explicit time dependence, the conserved energy isThese are the three integrals of motion requested.

Solving the two momentum equations givesSubstitution into the conserved energy reduces the heavy symmetric top to one-dimensional effective potential motion:whereThis is the heavy symmetric top reduction.

Put $L_z=L_3(1-{ϵ}^2/2)$ and seek $\theta =O(ϵ)$. Using $\cos \theta =1-{\theta }^2/2+O({\theta }^4)$ and ${\sin }^2\theta ={\theta }^2+O({\theta }^4)$, the $\theta$-dependent part of the effective potential isIt has a local minimum precisely whenwhich is the gyroscopic stabilization of an inverted symmetric top condition. Differentiating the displayed approximation givesand henceTaking $L_3>0$ without loss of orientation, the steady precession rate isso