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

An injective function satisfies $f(a)=f(a^{\prime })\Rightarrow a=a^{\prime }$ for all $a,a^{\prime }\in A$. A surjective function $g:A\to B$ satisfies: for every $b\in B$, some $a\in A$ has $g(a)=b$. The following arguments apply to function composition with the stated domains and codomains.

Let $c\in C$. Since $g$ is surjective, choose $b\in B$ with $g(b)=c$. Since $f$ is surjective, choose $a\in A$ with $f(a)=b$. Then $(g\circ f)(a)=g(b)=c$. Thus every element of $C$ has a preimage, proving that $g\circ f$ is surjective.

Suppose $(g\circ f)(a)=(g\circ f)(a^{\prime })$. The injectivity of $g$ implies $f(a)=f(a^{\prime })$, and the injectivity of $f$ then implies $a=a^{\prime }$. Hence $g\circ f$ is injective.

If $f(a)=f(a^{\prime })$, applying $g$ gives $(g\circ f)(a)=(g\circ f)(a^{\prime })$. The injectivity of $g\circ f$ implies $a=a^{\prime }$, so $f$ is injective.

For any $c\in C$, the surjectivity of $g\circ f$ supplies $a\in A$ with $g(f(a))=c$. Therefore $f(a)\in B$ is a preimage of $c$ under $g$, proving surjectivity of $g$.

For the requested counterexample, take $A=C=\{0\}$, $B=\{0,1\}$, $f(0)=0$, and $g(0)=g(1)=0$. The function composition is the identity bijection of the singleton, but $f$ is not surjective and $g$ is not injective.

The base case $n=1$ is the product rule. Suppose the Leibniz rule holds at order $n$. Taking one more derivative of each term and collecting the coefficient of $f^{(n+1-r)}{g}^{(r)}$ givesHere binomial coefficients outside $0\le r\le n$ are zero. For $1\le r\le n$, the factorial definition proves Pascal's identity directly:At $r=0,n+1$, the identity is $1+0=1$. Substitution gives the required order-$n+1$ formula, completing the induction.

Put $A=g\sin \alpha >0$ and $v=\dot{x}$. Multiplying the equation by $xv$ givesso its first integral isThese level curves give the positive phase plane for the avalanche front with linear mass entrainment. For $c<0$, the curve starts at $v=0$, $x=(-3c/(2A){)}^{1/3}$ and rises. For $c>0$, it diverges as $x\downarrow 0$, has a minimum at $x=(3c/A{)}^{1/3}$, and then rises. The $c=0$ curve is $v=\sqrt{2Ax/3}$. Forward-time arrows have increasing $x$; at a zero-velocity endpoint the equation gives $\ddot{x}=A>0$.

Every forward-moving trajectory has $x\to \infty$: after it has entered $v>0$, a bounded limiting $x$ would force a zero of the displayed positive-branch speed ahead of it, but its only possible zero is the lower endpoint. For large $x$,Expanding the equation as $x\ddot{x}+v^2=Ax$ and substituting the first integral givesThus both the asymptotic phase plane trajectory and the limiting acceleration are independent of the initial data.

Apply the rotating-vector derivative rule first to the position vector and then to its velocity. Since $\mathbf{\omega }$ is constant,For example, the derivative of ${\mathbf{v}}^{\prime }$ contributes ${\mathbf{a}}^{\prime }+\mathbf{\omega }\times {\mathbf{v}}^{\prime }$, while that of $\mathbf{\omega }\times \mathbf{x}$ contributes the other two terms. This is the equation of motion in a rotating frame. The mutual central forces are unchanged in form because rotations preserve lengths and differences of position vectors. Newton's second law for particle $i$ becomesSet $\mathbf{\omega }=-e\mathbf{B}/(2m)$. The velocity-dependent Lorentz force is $e{\mathbf{v}}_i^{\prime }\times \mathbf{B}=-e\mathbf{B}\times {\mathbf{v}}_i^{\prime }$, and it cancels the Coriolis force $-2m\mathbf{\omega }\times {\mathbf{v}}_i^{\prime }=e\mathbf{B}\times {\mathbf{v}}_i^{\prime }$. The remaining terms combine to $m\mathbf{\omega }\times (\mathbf{\omega }\times {\mathbf{x}}_i)$ and are quadratic in the magnetic field. Neglecting them givesidentical to the zero-field equations to first order. The Larmor theorem requires the common charge-to-mass ratio; a mixture with different ratios cannot use one rotating frame to cancel every magnetic term.

A set is countable if it is finite or admits an injection into the natural numbers; an infinite countable set can equivalently be listed as a sequence. Let $A={\bigcup }_{i\ge 1}{A}_i$ with each $A_i$ countable. Choose an enumeration of each nonempty $A_i$, allowing repetition if it is finite. List the pairs $(i,j)\in {\mathbb{N}}^2$ in successive finite diagonals of constant $i+j$ and output the $j$th member of $A_i$. This lists every member of $A$, so $A$ is countable; empty sets contribute nothing, and repetitions can be removed by retaining first occurrences. This is the countable union of countable sets theorem, in the usual setting with axiom of countable choice for selecting the enumerations.

Each positive-length interval $J_i$ has a nonempty interior containing a rational number by the density of the rational numbers. Fix one enumeration of the rational numbers and let $q_i$ be its first member in the interior of $J_i$. Disjointness gives $i\ne j\Rightarrow q_i\ne q_j$, so $i\mapsto q_i$ is an injection of $I$ into a countable set. Hence $I$ is countable. This proof of the countability of disjoint positive-length intervals uses a fixed enumeration and needs no arbitrary simultaneous choice of rationals.

First, finite additivity of a set function gives $f(\varnothing )=0$, since $f(\varnothing )=2f(\varnothing )$. Put $w_s=f(\{s\})$. Decomposing any subset into its singleton elements and using induction gives $f(A)={\sum }_{s\in A}{w}_s$. Fix $s\in S$ and let $r$ be the number of sets $A_i$ containing it. Its total coefficient in the alternating intersection sum is zero if $r=0$, and otherwise isby the binomial theorem. These are exactly the coefficients in $f({\bigcup }_i{A}_i)$. Summing against $w_s$ proves the required inclusion-exclusion principle for the additive set function, including signed weights.

Take the finite ambient set $S={\bigcup }_i{A}_i$ and the additive set function $f(A)=|A|$. Disjoint subsets have additive cardinality, so (a) applies and givesThis is the finite inclusion-exclusion principle.

In the set of all $n!$ permutations, let $A_i$ consist of those fixing $i$. For a prescribed collection of $k$ fixed points, its intersection has $(n-k)!$ members. Applying the inclusion-exclusion principle to the complement of ${\bigcup }_i{A}_i$ gives the number of derangements:The convergent power series for the exponential function at $-1$ therefore gives $\boxed{d_n/n!⟶e^{-1}}$.

For each $1\le j\le p-1$, Fermat's little theorem gives $j^p\equiv j(\mathrm{mod}p)$. Since $p$ is odd,

Put $m=(p-1)/2$, so the requested modulus is $pm$. The factorial $(p-1)!$ is divisible by $m$, and so is $p-1=2m$. Also, Wilson's theorem gives $(p-1)!\equiv -1\equiv p-1(\mathrm{mod}p)$. Because $m$ and $p$ are coprime integers, their product divides the difference. Thus the Wilson factorial congruence modulo a triangular number isThe displayed residue lies in the standard range even at $p=3$.

For $b>1$, Euler's theorem allows $d=\phi (b)>0$, since $a,b$ are coprime integers. At $b=1$ every congruence holds and one may take $d=1$. Let $y$ be the multiplicative order of $a$ modulo $b$. Write a nonnegative exponent $x=qy+r$ with $0\le r<y$ using the Euclidean division. Then $a^x\equiv a^r(\mathrm{mod}b)$, so $a^x\equiv 1$ implies $r=0$ by minimality of $y$. Thus $y\mid x$. Negative exponents, if included, give the same conclusion using the inverse residue of $a$.

A prime divisor of a Fermat number $F_n=2^{2^n}+1$ is odd, and satisfies $2^{2^n}\equiv -1(\mathrm{mod}p)$. Therefore $2^{2^{n+1}}\equiv 1(\mathrm{mod}p)$, so its multiplicative order divides $2^{n+1}$. It does not divide $2^n$, since $-1\ne 1$ modulo the odd prime. Every divisor of $2^{n+1}$ is a power of two, henceBy Fermat's little theorem and the divisibility just proved, $2^{n+1}\mid p-1$, giving $\boxed{p\equiv 1(\mathrm{mod}{2}^{n+1})}$.

For distinct positions and positive masses, Newton's law of universal gravitation givesThe proposed homothetic gravitational motion has ${\ddot{\mathbf{x}}}_i=-(2/9)t^{-4/3}{\mathbf{a}}_i$ and pair distances $t^{2/3}|{\mathbf{a}}_i-{\mathbf{a}}_j|$, so cancellation of $t^{-4/3}$ gives the time-independent equationsThese define a Newtonian central configuration with this choice of scale. Fordifferentiation in ${\mathbf{a}}_i$ gives ${\nabla }_{{\mathbf{a}}_i}\Phi =(2/9)m_i{\mathbf{a}}_i-G{\sum }_{j\ne i}{m}_i{m}_j({\mathbf{a}}_i-{\mathbf{a}}_j)/|{\mathbf{a}}_i-{\mathbf{a}}_j{|}^3=0$, exactly the displayed equations. The double sum in the paper counts each pair twice, so it agrees with this expression.

Multiply the configuration equations by $m_i$ and sum. Pair contributions cancel, giving ${\sum }_i{m}_i{\mathbf{a}}_i=0$. Thus the total linear momentum is $\mathbf{P}=(2/3)t^{-1/3}{\sum }_i{m}_i{\mathbf{a}}_i=0$. Each position is parallel to its velocity, so every $m_i{\mathbf{x}}_i\times {\dot{\mathbf{x}}}_i=0$ and the total angular momentum is zero. About any other fixed point $\mathbf{b}$, it is ${\mathbf{L}}_{\mathbf{b}}={\mathbf{L}}_O-\mathbf{b}\times \mathbf{P}=\boxed{0}$.

A central force has zero torque, so $h=r^2\dot{\theta }$ is constant and the angular momentum is $mh$. The areal velocity is $h/2$. Put $u=1/r$ and let primes denote angular derivatives. Then $\dot{r}=-h{u}^{\prime }$, $\ddot{r}=-h^2{u}^2{u}^{\prime \prime }$, and $r{\dot{\theta }}^2=h^2{u}^3$. The radial equation with inward force magnitude $f(u)$ is $m(\ddot{r}-r{\dot{\theta }}^2)=-f(u)$, giving the Binet equationChoose the angular origin along a diameter of a radius-$R$ circle through $O$. Its polar equation is $r=2R\cos \theta$, so $u=(2R{)}^{-1}\sec \theta$ on $-\pi /2<\theta <\pi /2$. Since $(\sec \theta {)}^{\prime \prime }+\sec \theta =2{\sec }^3\theta$, substitution gives $u^{\prime \prime }+u=8R^2{u}^3$ and henceThe force is attractive. For fixed force coefficient $c$ and mass, $R|mh|=\sqrt{mc/8}$, so $R$ is inversely proportional to the magnitude of the angular momentum. The time along the circle isThis circular orbit through an inverse-fifth-power singularity reaches the force center at the two endpoints of this angular interval. The integral is finite; continuation through the singular collision is not specified by the force law alone.

Neglecting gravity, the equation of motion is $m\ddot{\mathbf{x}}=a\dot{\mathbf{x}}\times \mathbf{x}/r^3$, where $r=|\mathbf{x}|>0$. Dotting with the velocity gives $d(m|\dot{\mathbf{x}}{|}^2/2)/dt=0$, because a cross product is perpendicular to its factors. Thus the speed is constant. The vector triple product givesHence the generalized angular momentum in a radial monopole field isDotting with $\mathbf{x}$ gives $\mathbf{L}\cdot \mathbf{x}=-ar$, or $\hat{\mathbf{L}}\cdot \hat{\mathbf{x}}=-a/|\mathbf{L}|$. For $\mathbf{L}\ne 0$, the direction of $\mathbf{x}$ therefore makes the fixed angle $\boxed{\cos \beta =-a/|\mathbf{L}|}$ with the axis $\mathbf{L}$, describing a right circular conical surface with vertex at the North Pole. Orthogonality gives $|\mathbf{L}{|}^2=m^2|\mathbf{x}\times \dot{\mathbf{x}}{|}^2+a^2$, so this cosine is in $[-1,1]$. Radial motion gives a degenerate cone; when $a=0$ and the ordinary angular momentum is nonzero the cone is the usual orbital plane. If $\mathbf{L}=0$, the norm identity forces $a=0$ and $\mathbf{x}\times \dot{\mathbf{x}}=0$, giving a radial straight line.

The moment of inertia of a uniform length-$2l$ rod about its transverse central axis isThe kinetic energy decomposition about the center of mass gives $\boxed{T=M{V}^2/2+M{l}^2{\dot{\theta }}^2/6}$ for center speed $V$ and rod angle $\theta$.

For a falling arch with $0<\alpha <\pi /2$, the symmetric two hinged rods with both ends sliding on a floor have the following motion. The hinge remains vertically over the arch center. Their centers are ${\mathbf{R}}_{\pm }=(\pm l\cos \theta ,l\sin \theta )$, so each has squared speed $l^2{\dot{\theta }}^2$. Total kinetic energy is $T=4M{l}^2{\dot{\theta }}^2/3$, and total gravitational potential energy is $U=2Mgl\sin \theta$. Conservation of energy from rest at angle $\alpha$ gives ${\dot{\theta }}^2=3g(\sin \alpha -\sin \theta )/(2l)$. At the hinge impact $\theta =0$, its height derivative is $2l\cos \theta \dot{\theta }$, givingThe floor-contact assumption is consistent: differentiating the energy relation gives $\ddot{\theta }=-3g\cos \theta /(4l)$, and the normal reaction on each outer endpoint is $N=Mg[1+9{\sin }^2\theta -6\sin \alpha \sin \theta ]/4$. Completing the square shows $N\ge Mg{\cos }^2\alpha /4\ge 0$ throughout the fall.