Past exam of the mathematics course of the University of Cambridge / 2001 / ia / Paper 4

Suppose $F:X\to \mathcal{P}(X)$ were a surjection onto the power set of the set $X$. Form the subsetSurjectivity would give $a\in X$ with $F(a)=D$. But then $a\in D$ holds exactly when $a\notin F(a)=D$, a contradiction. Hence no such surjection exists, and in particular there is no bijection between a set and its power set. This is the diagonal construction in Cantor's theorem; it also covers the empty set, whose power set has one element.

No such set exists. If $R$ had precisely the sets $x$ satisfying $x\notin x$ as its elements, applying that membership criterion to $R$ itself would givea contradiction. This is Russell's paradox. It rules out this unrestricted universal collection; a set whose elements happen not to contain themselves is perfectly possible, for example the empty set.

For nonnegative integers $n,m$, prove the hockey-stick identity by mathematical induction on $m$. The induction base case $m=0$ is $\left(\genfrac{}{}{0ex}{}{n}{0}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{0}\right)=1$. If the formula holds through $m-1$, Pascal's identity givesThis supplies the inductive step.

A binary string containing exactly $n$ zeroes and $j$ ones has length $n+j$. Choosing its $j$ one-positions gives $\left(\genfrac{}{}{0ex}{}{n+j}{j}\right)$ possibilities. Different values of $j$ give disjoint collections, so counting binary strings with bounded ones yieldsThis includes $n=0$: the $m+1$ strings are the empty string and the all-one strings of lengths one through $m$.

For an attractive central force, the transverse acceleration vanishes. In polar coordinates,Thus the specific angular momentum $h=r^2\dot{\theta }$ is constant. Assume $h\ne 0$, so angle can parameterize the orbit, and put $u=1/r$. Primes denote angle derivatives. The chain rule givesThe outward radial component of the attractive force is $-f(u)$. Its Newton's second law equation is therefore $m(\ddot{r}-r{\dot{\theta }}^2)=-f(u)$, giving the Binet equationThe sign reflects $f$ being the positive inward force magnitude. Zero angular momentum produces radial motion and is outside this angular parametrization.

Put $M=m_1+m_2$, define the center of mass $\mathbf{R}=(m_1{\mathbf{x}}_1+m_2{\mathbf{x}}_2)/M$, and let $\mathbf{r}={\mathbf{x}}_1-{\mathbf{x}}_2$ be relative position. Adding the two Newton's second law equations givesThe center of mass has constant velocity, by conservation of total momentum.

Subtracting the particle accelerations instead givesThus relative motion is a one-particle problem with the reduced mass $\mu$, while center-of-mass motion is uniform. The same reduced mass appears in the kinetic energy decomposition $T=\frac{1}{2}M|\dot{\mathbf{R}}{|}^2+\frac{1}{2}\mu |\dot{\mathbf{r}}{|}^2$.

For a prime number $p$, the nonzero residue classes form the multiplicative group of the finite field ${\mathbb{F}}_p$. Every class has a unique multiplicative inverse. A class equals its own inverse precisely when $x^2=1$, so $(x-1)(x+1)=0$ in the field and $x=1$ or $x=-1$.

For an odd prime, pair each remaining class with its distinct inverse. Each pair contributes one to the product, leavingFor $p=2$, the same congruence is $1\equiv -1(\mathrm{mod}2)$. This proves Wilson's theorem.

Write $r=(p-1)/2$, $O=1\cdot 3\cdots (p-2)$ and $E=2\cdot 4\cdots (p-1)$. The residues $p-2,p-4,\dots ,p-2r$ are exactly the odd factors of $O$, in reverse order. Henceby Wilson's theorem. It follows that the odd-residue squared product modulo a prime isThus it is $-1$ for $p\equiv 1(\mathrm{mod}4)$ and $1$ for $p\equiv 3(\mathrm{mod}4)$.

For finite sets $A_1,\dots ,A_s$, the inclusion-exclusion principle statesTo prove it, count the contribution of an element lying in exactly $r\ge 1$ of the sets. Its total coefficient isby the binomial theorem. An element in none contributes zero. Summing these elementwise counts proves the formula. Applying the same argument to indicator functions and taking expectations proves the corresponding probability formula.

Factor $4199=13\cdot 17\cdot 19$. An integer is coprime to this product precisely when none of its three prime factors divides it. Inclusion-exclusion applied to the multiples of those prime numbers among $1,\dots ,4199$ gives Euler's totient functionFor the survey, let $H,D,S$ be the three detestation events and use proportions as probabilities. The union $H\cup D$ is the reported total union with the only-$S$ group removed, so $\mathbb{P}(H\cup D)=0.90-0.27=0.63$. The two-set inclusion-exclusion principle gives $\mathbb{P}(H\cap D)=0.45+0.28-0.63=0.10$. Removing the all-three group leavesThe required proportion is 4%. The separately reported total $S$ proportion is consistent with, but unnecessary for, this calculation.

If $p$ is a prime number and $p\nmid a$, multiplication by $a$ permutes the nonzero residue classes modulo $p$: $ai\equiv aj$ implies $i\equiv j$ because $a$ has a multiplicative inverse. Multiplying all the permuted classes givesThe factorial is a nonzero element of the finite field ${\mathbb{F}}_p$, so cancellation is valid. Thereforewhich is Fermat's little theorem.

Let $d$ be the multiplicative order of $a$ modulo $p$. Use Euclidean division to write $x=qd+r$, $0\le r<d$. Since $a^d\equiv 1$,If $a^x\equiv 1$, minimality of $d$ forces $r=0$, so $d$ divides $x$. Conversely, $d\mid x$ immediately gives $a^x\equiv 1$. For negative integers $x$, powers are interpreted using the multiplicative inverse and the same argument applies.

Apply the result to $x=p-1$, using Fermat's little theorem. Then $d\mid p-1$, equivalently

If $x^2\equiv -1(\mathrm{mod}p)$ with $p$ an odd prime, then $x^4\equiv 1$ but $x^2\not\equiv 1$. The multiplicative order consequently divides four and is neither one nor two, so it is four. The preceding divisibility result makes $4\mid p-1$ necessary.

For sufficiency, suppose $p\equiv 1(\mathrm{mod}4)$ and put $r=(p-1)/2$, an even integer. Pair opposite factors in the factorial:Wilson's theorem gives $(r!{)}^2\equiv -1(\mathrm{mod}p)$, explicitly producing a square root of minus one modulo a prime. Thus

Mathematical induction consists of an induction base case $P(1)$ and an inductive step $P(n)\Rightarrow P(n+1)$ for every positive integer $n$. To derive it from the well-ordering principle, suppose the set of counterexamples were nonempty and take its least element $n$. The base case excludes $n=1$. If $n>1$, minimality gives $P(n-1)$, and the step then gives $P(n)$, a contradiction. Hence there are no counterexamples.

For the stated integer congruence, the base case is $9\equiv 2(\mathrm{mod}7)$. If $9^n\equiv 2^n(\mathrm{mod}7)$, multiplication and $9\equiv 2(\mathrm{mod}7)$ givecompleting the induction.

The purported shifted-sum proof has a correct conditional successor calculation, but the base case is missing and false: at $n=1$ it would assert $1=1+126$. An inductive step without a true induction base case cannot establish any instance.

The equation of motion in a rotating frame with constant angular velocity $\mathbf{\omega }$ isWith $\mathbf{F}=-4m{\omega }^2\mathbf{x}$ and $\mathbf{\omega }=(0,0,\omega )$, this becomesThe given initial data make $z=0$. For the complex coordinate $\zeta =x+iy$, the planar equations combine intoIts characteristic roots are $i\omega$ and $-3i\omega$. Applying $\zeta (0)=1$, $\dot{\zeta }(0)=0$ gives $\zeta =\frac{3}{4}{e}^{i\omega t}+\frac{1}{4}{e}^{-3i\omega t}$. The triple-angle identities reduce this astroid motion of a harmonic oscillator in a rotating frame toIt traces an astroid. Differentiating gives the relative speedFor $\omega >0$, its maxima occur at $t=(2n+1)\pi /(4\omega )$, withThis is speed measured in the specified rotating frame. The same physical motion has inertial complex coordinate $e^{i\omega t}\zeta =\cos (2\omega t)+(i/2)\sin (2\omega t)$, an ellipse; its initial velocity is the frame-rotation contribution even though the initial relative velocity is zero.

Let $m=4\pi \rho a^3/3$ be the drop's mass, with constant mass density $\rho$. Its volume-growth rule gives $4\pi a^2\dot{a}=c\pi a^{2}v$, hence $\dot{a}=cv/4$ and $\dot{m}=\rho c\pi a^{2}v$. The incoming mist is stationary, so the variable-mass system momentum balance isExpanding the derivative and substituting the accretion rate gives the accreting raindrop with quadratic drag equationsThe extra $c$ contribution is the momentum needed to accelerate collected matter from rest; omitting it would treat the growing drop as a constant-mass particle.

Set $q=v^2/a$ and $B=7c/8+3k/4$. The chain rule givesTo justify the limiting value as well as its stability sign, use $c>0$, as appropriate to volume growth. Divide by $\dot{a}=cv/4$ and integrate the resulting first-order equation:Thus $q$ remains between two positive constants, its initial value and $g/B$. Since $d\sqrt{a}/dt=c\sqrt{q}/8$, the radius is defined for all increasing time and tends to infinity. The correction vanishes, proving the speed-radius attractor of an accreting raindrop:The strict inequality uses $k>0$. The growing radius prevents a finite terminal velocity; instead the acceleration approaches this positive constant.

Write $h=r^2\dot{\theta }$ for the conserved specific angular momentum. Zero specific orbital energy in the inverse-square Newtonian gravitational field givesDefine $r_0=h^2/(2GM)$, the periapsis radius for a nonradial parabolic trajectory. ThenOn the outgoing branch, integrate from the periapsis time $t_0$ and put $s=\sqrt{r-r_0}$:The incoming branch has the opposite sign. Squaring gives the radius-time relation for a parabolic Kepler orbit, a version of the Barker equation:Here $r_0$ and $t_0$ are fixed by angular momentum and the time origin at periapsis. The relation applies on both branches, with $r\ge r_0$; it is not necessary to solve for the polar angle.

A coaxial shell of radius $r$ and thickness $dr$ has mass $dm=2\pi \rho lrdr$. Integrating squared radius against mass, the moment of inertia of a uniform solid cylinder about its axis isOn the smooth incline, no tangential contact force produces spin, so the initially stationary cylinder simply slides with acceleration $g\sin \theta$. Therefore $t_{\mathrm{slide}}=\sqrt{2L/(g\sin \theta )}$.

For rolling without slipping, let $F$ be uphill static friction and $A$ the downward translational acceleration. Newton's second law, the rotational torque equation, and the contact constraint giveWith $I=M{a}^2/2$, these give $F=MA/2$ and $A=2g\sin \theta /3$. The rolling-time factor on a straight incline is consequentlyThe required friction is $Mg\sin \theta /3$; the stated no-slip motion presupposes sufficient static friction. At an instantaneously stationary contact point it does no work. Gravitational potential energy is shared between translational and rotational kinetic energy, explaining why rolling accelerates more slowly than the smooth slide.