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

The Euclidean algorithm givesBack substitution produces the Bézout's identityHence a positive integer solution is $\boxed{m=19,n=15}$. More generally, subtracting this identity from any other solution shows $79(m-19)=100(n-15)$. Since $79$ and $100$ are coprime, the integer solutions are $m=19+100k$, $n=15+79k$; both are positive precisely when $k\ge 0$.

Divide the linear congruence by the common factor $3$, also dividing its modulus:The Bézout's identity from part (a) makes $19$ the inverse of $79$ modulo $100$. Multiplication by $19$ therefore gives $x\equiv 133\equiv 33(\mathrm{mod}100)$. Thus all integer solutions are $\boxed{x=33+100k,k\in \mathbb{Z}}$. Equivalently, the three solution classes modulo $300$ are $33,133,233$; using modulus $300$ must not discard two of these classes.

Write $x=11+100t$. Reduction of the other integer congruence modulo $79$ gives $21t\equiv -3(\mathrm{mod}79)$. The Bézout's identity $19\cdot 79-15\cdot 100=1$ gives $-15\cdot 21\equiv 1(\mathrm{mod}79)$, so $t\equiv 45(\mathrm{mod}79)$. Consequently,Indeed, $4511=8+79\cdot 57=11+100\cdot 45$. The Chinese remainder theorem guarantees one class modulo $79\cdot 100$, since the two moduli are coprime.

For the odd-square sum, the initial case $n=1$ gives $1=(4-1)/3$. Assume the formula at $n$. Adding the next square givesThe initial case and this induction step prove $\boxed{\sum _{j=1}^n(2j-1{)}^2=(4n^3-n)/3}$ for every positive integer $n$.

For the divisibility assertion, $1^3+5\cdot 1=6$. The change when $n$ is replaced by $n+1$ isOne of the consecutive integers $n,n+1$ is even, so the displayed change is divisible by $6$. If $n^3+5n$ is divisible by $6$, its successor is too. Thus induction proves $\boxed{6\mid n^3+5n}$ for every $n\ge 1$.

Choose the positive direction along the incoming car's velocity. Treat each car as a translating body, take $m_1,m_2>0$, and neglect external impulse, rotation and energy losses during the short elastic collision. If $v_1,v_2$ are the final signed velocities, conservation of momentum and conservation of energy giveFactoring the second relation and using the first gives $U_1+v_1=v_2$ on the collision branch. The other algebraic branch, $v_1=U_1,v_2=0$, describes no impulse and cannot describe separating bodies after contact. Solving the collision branch yieldsFor $0<R<1$ the first car rebounds and the second moves forwards. At $R=1$ the first stops and the second takes its original velocity. For $R>1$ both move forwards, with $v_2-v_1=U_1>0$, so they separate. In the limits $R\to 0$ and $R\to \infty$, the first car's velocity approaches $-U_1$ and $U_1$, respectively.

For the deformable car, take $y=0$ at first contact. The resisting force does negative work. The work-energy theorem therefore givesAt the first stop $v=0$, whence $\sqrt{L-y}=\sqrt{L}-M{V}^2/4$. The speed bound ensures that this right-hand side is positive, so squaring introduces no extraneous solution. The stopping compression isFor $0<V<2L^{1/4}/M^{1/2}$ this lies strictly between $0$ and $L$, as required before complete crushing. The coefficient in the stipulated force law is taken in its stated normalization.

Let $z$ measure height above the release point, and use $\mathcal{V}=4\pi a^3/3$ for the bubble volume to avoid confusing it with a speed. For constant radius, Newton's second law, the specified buoyancy and the given Stokes law giveWith positive $\alpha ,\rho ,\mu ,a$, defineThe differential equation becomes $\dot{u}+(u/\tau )=U/\tau$. Its solution with $u(0)=0$ is $u(t)=U(1-e^{-t/\tau })$. Integration using $z(0)=0$ yieldsAn arbitrary initial height is added to this expression. The effective inertia changes the relaxation time $\tau$, but not the terminal velocity obtained by balancing buoyancy and drag.

For the dissolving bubble assume $\beta >0$ and use the specified instantaneous terminal velocity, rather than the constant-radius transient formula. The bubble disappears at $t_{\ast }=a_0^2/\beta$, andIts total rise is therefore $\boxed{z(t_{\ast })=\rho g{a}_0^4/(9\mu \beta )}$. This second model neglects the initial acceleration and uses exactly the terminal-speed approximation stipulated for the shrinking bubble.

Number the natural numbers from one. If the power set could be enumerated as $A_1,A_2,\dots$, form $D=\{j:j\notin A_j\}$. For each $j$, membership of $j$ in $D$ is opposite to its membership in $A_j$, so $D\ne A_j$. This contradicts completeness of the enumeration. Thus the Cantor diagonal argument proves that the power set is an uncountable set.

For a finite subset $A$, define $b(A)={\sum }_{j\in A}{2}^{j-1}$. This is a nonnegative integer and the map is injective: if two finite subsets differ, let $k$ be their largest differing element. Its contribution $2^{k-1}$ exceeds the sum $1+2+\cdots +2^{k-2}$ of all smaller possible contributions, so their codes differ. There are infinitely many singleton subsets. Hence the countability of finite subsets of a countable set here is countable infinitude.

To treat all bijections, associate to every subset $A\subseteq \mathbb{N}$ the permutation that swaps $2j-1$ and $2j$ when $j\in A$, and fixes both when $j\notin A$. These disjoint pair swaps define a bijection of $\mathbb{N}$. Different subsets give different permutations, so the map from the power set into $X$ is injective. Therefore $X$ is an uncountable set.

Every finitely supported permutation fixes all elements above some $k$. A bijection fixing that tail must permute $\{1,\dots ,k\}$: it cannot send a smaller element into the fixed tail without violating injectivity. There are exactly $k!$ such permutations. Thusis a countable union of finite sets. Enumerate first by $k$, then by one of the finitely many permutations at that $k$; duplicates can be omitted. Infinitely many distinct pair swaps belong to $Y$, so $Y$ is countably infinite. The full family is uncountable, while the finitely supported family is countably infinite.

For a prime number $p$ and an integer $x$ coprime to $p$, multiplication by $x$ permutes the nonzero residue classes modulo $p$. Indeed, $ax\equiv bx(\mathrm{mod}p)$ implies $a\equiv b(\mathrm{mod}p)$, and none of the products is zero. Taking the product over the $p-1$ classes givesThe factorial is coprime to $p$ and can be cancelled, proving Fermat little theorem: $\boxed{x^{p-1}\equiv 1(\mathrm{mod}p)}$.

Now $n=mp$ and $x$ is coprime to $n$, so it is coprime to $p$. Since $(n-1)-(m-1)=m(p-1)$, the proved theorem givesThus the two specified integer congruences modulo $p$ are equivalent. In this particular step the additional hypothesis $(m,p)=1$ is not needed; it will hold for the squarefree factorization used next.

If $n$ is a squarefree integer, its distinct prime factors are pairwise coprime. Consequently $n$ divides $x^{n-1}-1$ exactly when every prime factor does. Applying the preceding equivalence with $m=n/p$ provesFinally retain this squarefree hypothesis. If $p-1$ divides $n-1$, write $n-1=k_p(p-1)$. Fermat little theorem gives $x^{n-1}=(x^{p-1}{)}^{k_p}\equiv 1(\mathrm{mod}p)$ for every prime factor. Their pairwise coprimality then gives $\boxed{x^{n-1}\equiv 1(\mathrm{mod}n)}$. For composite $n$ this is the sufficient direction of the Korselt criterion for a Carmichael number; primality is not excluded by the requested implication.

The binomial polynomial $P_r$ equals $1$ when $r=0$. For $n\ge 0$, it has value $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ if $r\le n$ and value zero otherwise. These are integers. If $n=-k<0$, thenHence each $P_r$ is an integer-valued polynomial on all of $\mathbb{Z}$, including negative arguments.

For $r\ge 1$, factor the common product in the two polynomials:For $r=1$ the common product is empty and equals $1$, so this argument also covers that boundary case.

The polynomial $P_r$ has polynomial degree $r$ and leading coefficient $1/r!$. For a polynomial $F$ of polynomial degree $d$ with leading coefficient $a_d\in \mathbb{Q}$, subtract $d!a_d{P}_d$; the remainder has smaller polynomial degree. Repeating gives the required expansion with rational numbers $c_r$. For uniqueness, suppose two expansions differ and let $s$ be the largest index with different coefficients. Their difference then has a nonzero term of polynomial degree $s$, with leading coefficient equal to that coefficient difference divided by $s!$. It cannot be the zero polynomial. Thus the expansion is unique.

Replacing $X$ by $X+1$ in the earlier identity gives $\Delta P_r(X)=P_{r-1}(X)$ for $r\ge 1$, while $\Delta P_0=0$. By linearity of the forward difference operator,An empty sum is zero when $d=0$. If $H=F-G$ were nonconstant, with polynomial degree $s\ge 1$ and leading coefficient $a_s$, then $\Delta H$ would have polynomial degree $s-1$ and leading coefficient $s{a}_s\ne 0$. Therefore $\Delta F=\Delta G$ forces $H$ to be constant.

There is a direct way to recover every coefficient. Since $P_0(0)=1$ and $P_j(0)=0$ for $j\ge 1$, repeated application of the forward difference operator givesThe last equality follows by expanding $(T-I{)}^r$, where $TF(X)=F(X+1)$; the commuting shifts obey the binomial theorem. If $F$ is an integer-valued polynomial, every summand on the right is an integer, proving that all $c_r(F)$ are integers. Together with the first paragraph this gives both directions of the Newton series for an integer-valued polynomial sequence description.

For each $x\in X$, the product ${\prod }_{i=1}^m(1-g_i(x))$ is $1$ precisely outside every $X_i$, and is $0$ otherwise. It is therefore the indicator function of $Y$. Expanding the finite product givesMultiply by $f(x)$ and sum over the finite set $X$. The product of indicator functions is the indicator function of the corresponding intersection, soHere the empty intersection is $X$, and the empty product is $1$. Grouping the subsets $S$ by their cardinality gives the requested weighted inclusion-exclusion principle, with no contribution for $r>m$.

Let $\mathcal{P}$ be the finite set of distinct prime factors of $n$, and work in $\{0,\dots ,n-1\}$. For $S\subseteq \mathcal{P}$ put $d_S={\prod }_{p\in S}p$, including $d_{\varnothing }=1$. Then $d_S\mid n$, and an integer belongs to every $X_p$ for $p\in S$ exactly when it is a multiple of $d_S$. Thus the intersection has size $n/d_S$. The complement consists precisely of the residues coprime to $n$. Using weight $1$ givesThis proves the product formula for the Euler totient function without requiring $n$ to be squarefree.

For the weight $f(x)=x$, the sum over the multiples of any divisor $d$ in this interval isThe weighted inclusion-exclusion principle therefore givesSince $n>1$, $\mathcal{P}$ is nonempty and the last sum is $(1-1{)}^{|\mathcal{P}|}=0$. The first factors as before, givingThis sum of reduced residues also follows by pairing the bijection $x\mapsto n-x$; at $n=2$ its sole fixed residue causes no problem because the sum of both copies still equals $n\phi (n)$.

Use a translating accelerated reference frame; its axes do not rotate. If $\mathbf{R}=(\xi ,\eta ,\zeta )$ is the block's position relative to the table, then its inertial position is $\mathbf{r}=\mathbf{R}+\mathbf{A}\sin \omega t$. Its relative velocity is $\dot{\mathbf{R}}$ and its inertial acceleration is $\ddot{\mathbf{R}}-{\omega }^2\mathbf{A}\sin \omega t$. Let $N$ be the upward normal force. During contact $\zeta =\dot{\zeta }=\ddot{\zeta }=0$, and the linear tangential resistance givesThese are Newton's second law transformed to the table's reference frame; the extra terms arise from the table's acceleration. The last equation gives $N=m(g-A_z{\omega }^2\sin \omega t)$ while contact persists. If contact is lost, both the contact resistance and $N$ vanish, and free flight must be described by the corresponding gravity-only equations.

For $A_z=0$, assume $\lambda >0$ and put $\gamma =\lambda /m$. Seek a periodic particular solution ${\xi }_p=b\sin \omega t+c\cos \omega t$. Substitution into the first differential equation givesSolving yieldsThe homogeneous solutions are a constant and a multiple of $e^{-\gamma t}$. Choose the phase $0<\theta <\pi /2$ with $\tan \theta =\omega /\gamma =m\omega /\lambda$. Then $b=-A_x{\sin }^2\theta$ and $c=-A_x\sin \theta \cos \theta$, soAlso $\eta (t)={\eta }_{\infty }+C_{\eta }{e}^{-\lambda t/m}$. The decaying transients leave the stated steady orbit. Positive damping is essential to this late-time assertion; for $\lambda =0$ an additional constant drift may persist.

No attractive contact force is available, so $N$ cannot be negative. Over a whole oscillation its minimum is $m(g-{\omega }^2|A_z|)$. Thus strictly positive contact loading throughout requires $\boxed{{\omega }^2|A_z|<g}$, or the printed form with $A_z$ taken as a nonnegative vertical amplitude. If ${\omega }^2|A_z|>g$, contact cannot persist: it would require $N<0$ during part of the cycle. At equality, $N$ vanishes only at isolated instants and the ideal constrained motion can still remain in contact. Hence the strict inequality characterizes positive loading; mere nonnegative contact permits the marginal equality case.

Write $k=GM$ and $r=|\mathbf{r}|$. The gravitational central force has zero torque, so the specific angular momentumis constant. For a nonradial orbit $h=|\mathbf{h}|>0$, motion lies in the plane normal to $\mathbf{h}$, and plane polar coordinates give $r^2\dot{\theta }=h$. With $u=1/r$ and primes denoting $\theta$ derivatives,The radial equation $\ddot{r}-r{\dot{\theta }}^2=-k/r^2$ is therefore the Binet equationIts general solution, after choosing the polar origin of angle, isThe origin is a focus of this conic section. To identify which conic section occurs, use the conserved specific energyA bound, nonradial orbit has $\epsilon <0$, hence $0\le e<1$ and is an ellipse. For example, putting $x=r\cos \theta$, $y=r\sin \theta$ in $r+ex=p$ givesan explicit ellipse equation. This is the intended low, bound Kepler orbit. The inverse-square equation alone does not imply an ellipse: an initially tangential speed larger than $\sqrt{2GM/r}$ gives $\epsilon >0$, $e>1$ and a hyperbolic Kepler orbit. Zero angular momentum instead gives radial motion. Those qualifications are necessary for the elliptic conclusion.

In a circular orbit, centripetal acceleration balances the gravitational acceleration:Here $\Omega$ is the positive angular speed; either sense of circulation has this period.

With the stated drag force, use the full angular momentum $\mathbf{L}=m\mathbf{r}\times \dot{\mathbf{r}}$. Gravitational torque is still zero, while the drag torque isTherefore $\boxed{\mathbf{L}(t)=\mathbf{L}(0)e^{-At/m}}$ for constant $A>0$. Its direction remains fixed, and its magnitude has exponential decay with time constant $m/A$; the orbit remains planar although its shape is no longer a fixed ellipse.

Taking the scalar product of the Lorentz force equation with the velocity givesThe triple product vanishes because the cross product is perpendicular to its first factor. Thus the kinetic energy is constant, even if the magnetic field varies with position: magnetic forces do no work.

In cylindrical coordinates, the radial, angular and vertical equations areFor a nonstationary circular orbit with constant $r$ and $z$, the first equation gives $-m{\dot{\theta }}^2=qB(r)\dot{\theta }$. Hence its signed angular velocity is $\boxed{\dot{\theta }=-qB(r)/m}$. The sign gives the sense of circulation. The zero root describes a stationary transverse position, not a moving circular orbit. A constant vertical velocity can be superposed to produce a helix.

Define the mechanical angular momentum about the axis by $L=m{r}^2\dot{\theta }$. Multiplying the angular equation by $r$ givesFor the inverse-radius magnetic field this becomes $\dot{L}=-q{B}_0\dot{r}$. Integrating from an initial radius $r_0$ provesLet $c=q{B}_0/m$ and $\ell =(L_0+q{B}_0{r}_0)/m$, so that $L/m=\ell -cr$. Since $\dot{z}$ is constant and the total kinetic energy is constant, the transverse speed squaredis also constant. Substituting the angular momentum relation gives the required radial curve:Only the region $W(r)\ge 0$ is accessible. For $\ell \ne 0$, $W(r)\to -\infty$ as $r\to 0$, and its horizontal asymptote is $v_{\perp }^2-c^2$. Its derivative is $W^{\prime }(r)=2\ell (\ell -cr)/r^3$. Thus, when $\ell c>0$, it has a single maximum $W=v_{\perp }^2$ at $r=\ell /c$. The positive roots of $W$ are the turning points obtained from $r=\ell /(c\pm v_{\perp })$.

For nonzero $c$ and $\ell c>0$, write $r_c=|\ell /c|$. When $0<v_{\perp }<|c|$, two turning points occur atand the radius is confined between them. At $v_{\perp }=|c|$, there is only the finite lower turning point $r_c/2$; $W$ tends to zero from above and an outgoing particle reaches arbitrarily large radius. For $v_{\perp }>|c|$, only the lower turning point remains and the outgoing radial velocity approaches $\sqrt{v_{\perp }^2-c^2}$. The sketch shows these three cases and omits inaccessible negative values of ${\dot{r}}^2$ from the physical interpretation.

For completeness, if $\ell c<0$, $W$ rises monotonically from $-\infty$ to its asymptote; admissible motion then requires $v_{\perp }>|c|$ and is radially unbound after any inward branch turns. If $\ell =0$, $W=v_{\perp }^2-c^2$ is constant; equality gives a circular orbit rather than escape. Above threshold the outgoing branch escapes, whereas an incoming branch reaches the singular axis in finite time and cannot be continued through it without specifying a nonsingular core field. These cases explain why a borderline escape assertion needs an initial-direction qualification.

The transverse escape velocity threshold for radial escape in an inverse-radius axial magnetic field isFor a radial launch at $r_0$, $\ell =c{r}_0$, and equality permits marginal escape; for $\ell \ne 0$, larger transverse speed guarantees radial escape in forward time after any initial inward leg turns. The singular incoming $\ell =0$ branch is the exception described above. More general launches at equality can instead give the circular exception $\ell =0$. A vertical velocity adds to the total speed but cannot pay the transverse escape-energy requirement; if escape merely means unbounded $z$, any nonzero $\dot{z}$ already achieves that. If $q{B}_0=0$, transverse motion is force-free and there is no positive escape-speed threshold.

The moment of inertia of a uniform solid cylinder is taken about its symmetry axis. Write its mass density as ${\rho }_c=m/(\pi a^{2}L)$. A coaxial shell of radius $r$ and thickness $dr$ has mass $dm=2\pi {\rho }_{c}Lrdr$. ThusA hollow cylinder would have a different moment of inertia; uniform solid density is the intended assumption.

Let $s$ measure the centre's displacement uphill from its initial position, and choose signed angular velocity $\omega$ so that uphill rolling without slipping has $\dot{s}=a\omega$. Let $F$ be the signed contact force uphill. The translation and rotation equations areThe minus sign in the torque equation follows from the chosen rolling sense: uphill contact force opposes the positive spin. Under rolling without slipping, $\ddot{s}=a\dot{\omega }$. Eliminating $F$ givesUsing $s(0)=0$ and $\dot{s}(0)=V$, the no-slip motion and maximum vertical rise areIndeed the centre turns at $t=3V/(2g\sin \alpha )$, reaching $s_{\max }=3V^2/(4g\sin \alpha )$, whose vertical component is the boxed height. Conservation of energy independently gives the same answer from initial kinetic energy $m{V}^2/2+I(V/a{)}^2/2=3m{V}^2/4$.

The available static friction is at most $\mu mg\cos \alpha$. It can supply the required uphill force exactly when $mg\sin \alpha /3\le \mu mg\cos \alpha$. ThereforeInterpret the stated friction magnitude as limiting static friction and as kinetic friction during slip, with the same coefficient. Take $0<\alpha <\pi /2$, $\mu \ge 0$. In the slipping regime the contact point moves downhill relative to the slope, so kinetic friction acts uphill. To verify this direction rather than assume it unchecked, solve with $F=\mu mg\cos \alpha$. Define $b=g(\sin \alpha -\mu \cos \alpha )>0$. The result isThe centre's speed is $|V-bt|$, with the sign of $v$ specifying ascent or descent. The contact point's relative velocity isThus the assumed uphill kinetic friction is consistent throughout both ascent and descent, including when the centre's velocity changes sign. There is no later return to rolling without slipping before reaching the bottom. This is the characteristic slipping solid cylinder on an incline regime.

The centre turns at $t_{\ast }=V/b$, givingThe formulas apply up to the positive return time $t_b=2V/b$. Substitution into the signed velocity and angular velocity givesThe return spin can have either sign and vanishes at $\tan \alpha =5\mu$. It reverses when $3\mu <\tan \alpha <5\mu$, although the contact point still slips downhill. The unchanged centre speed does not mean that no energy was dissipated: the rotational kinetic energy has decreased. Indeed integrating the frictional power $Fw<0$ giveswhich agrees with the difference of the initial and final rotational kinetic energies.