STEP 2 1995

I have $n$ fence posts placed in a line and, as part of my spouse's birthday celebrations, I wish to paint them using three different colours red, white and blue in such a way that no adjacent fence posts have the same colours. (This allows the possibility of using fewer than three colours as well as exactly three.) Let $r_n$ be the number of ways (possibly zero) that I can paint them if I paint the first and the last post red and let $s_n$ be the number of ways that I can paint them if I paint the first post red but the last post either of the other two colours. Explain why $r_{n+1}=s_n$ and find $r_n+s_n.$ Hence find the value of $r_{n+1}+r_n$ for all $n⩾1.$

Prove, by induction, that $$r_n=\frac{2^{n-1}+2(-1{)}^{n-1}}{3}.$$ Find the number of ways of painting $n$ fence posts (where $n⩾3$) placed in a circle using three different colours in such a way that no adjacent fence posts have the same colours.

The Tour de Clochemerle is not yet as big as the rival Tour de France. This year there were five riders, Arouet, Barthes, Camus, Diderot and Eluard, who took part in five stages. The winner of each stage got 5 points, the runner up 4 points and so on down to the last rider who got 1 point. The total number of points acquired over the five states was the rider's score. Each rider obtained a different score overall and the riders finished the whole tour in alphabetical order with Arouet gaining a magnificent 24 points. Camus showed consistency by gaining the same position in four of the five stages and Eluard's rather dismal performance was relieved by a third place in the fourth stage and first place in the final stage. Explain why Eluard must have received 11 points in all and find the scores obtained by Barthes, Camus and Diderot.

Where did Barthes come in the final stage?

Let $$u_n={\int }_0^{\frac{1}{2}\pi }{\sin }^{n}t\mathrm{d}t$$ for each integer $n⩾0$. By integrating $${\int }_0^{\frac{1}{2}\pi }\sin t{\sin }^{n-1}t\mathrm{d}t$$ by parts, or otherwise, obtain a formula connecting $u_n$ and $u_{n-2}$ when $n⩾2$ and deduce that $$n{u}_n{u}_{n-1}=\left(n-1\right)u_{n-1}{u}_{n-2}$$ for all $n⩾2$. Deduce that $$n{u}_n{u}_{n-1}=\frac{1}{2}\pi .$$ Sketch graphs of ${\sin }^{n}t$ and ${\sin }^{n-1}t$, for $0⩽t⩽\frac{1}{2}\pi ,$ on the same diagram and explain why $0<u_n<u_{n-1}.$ By using the result of the previous paragraph show that $$n{u}_n^2<\frac{1}{2}\pi <n{u}_{n-1}^2$$ for all $n⩾1$. Hence show that $$\left(\frac{n}{n+1}\right)\frac{1}{2}\pi <n{u}_n^2<\frac{1}{2}\pi$$ and deduce that $n{u}_n^2\to \frac{1}{2}\pi$ as $n\to \infty$.

The famous film star Birkhoff Maclane is sunning herself by the side of her enormous circular swimming pool (with centre $O$) at a point $A$ on its circumference. She wants a drink from a small jug of iced tea placed at the diametrically opposite point $B$. She has three choices:

1. to swim directly to $B$.
2. to choose $\theta$ with $0<\theta <\pi ,$ to run round the pool to a point $X$ with $\angle AOX=\theta$ and then to swim directly from $X$ to $B$.
3. to run round the pool from $A$ to $B$.

She can run $k$ times as fast as she can swim and she wishes to reach her tea as fast as possible. Explain, with reasons, which of (i), (ii) and (iii) she should choose for each value of $k$. Is there one choice from (i), (ii) and (iii) she will never take whatever the value of $k$?

If $u$ and $v$ are the two roots of $z^2+az+b=0,$ show that $a=-u-v$ and $b=uv.$

Let $\alpha =\cos (2\pi /7)+\mathrm{i}\sin (2\pi /7).$ Show that $\alpha$ is a root of $z^6-1=0$ and express the roots in terms of $\alpha .$ The number $\alpha +{\alpha }^2+{\alpha }^4$ is a root of a quadratic equation $$z^2+Az+B=0$$ where $A$ and $B$ are real. By guessing the other root, or otherwise, find the numerical values of $A$ and $B$.

Show that $$\cos \frac{2\pi }{7}+\cos \frac{4\pi }{7}+\cos \frac{8\pi }{7}=-\frac{1}{2},$$ and evaluate $$\sin \frac{2\pi }{7}+\sin \frac{4\pi }{7}+\sin \frac{8\pi }{7},$$ making it clear how you determine the sign of your answer.

The diagram shows a circle, of radius $r$ and centre $I$, touching the three sides of a triangle $ABC$. We write $a$ for the length of $BC$ and $\alpha$ for the angle $\angle BAC$ and so on.

Let $s=\frac{1}{2}\left(a+b+c\right)$ and let $△$ be the area of the triangle.

1. By considering the area of the triangles $AIB,$ $BIC$ and $CIA$, or otherwise, show that $\Delta =rs$.
2. By using the formula $\Delta =\frac{1}{2}bc\sin \alpha$, show that $${\Delta }^2=\frac{1}{16}[4b^2{c}^2-{\left(2bc\cos \alpha \right)}^2].$$ Now use the formula $a^2=b^2+c^2-2bc\cos \alpha$ to show that $${\Delta }^2=\frac{1}{16}[(a^2-{\left(b-c\right)}^2)({\left(b+c\right)}^2-a^2)]$$ and deduce that $$\Delta =\sqrt{s\left(s-a\right)\left(s-b\right)\left(s-c\right)}.$$
3. A hole in the shape of the triangle $ABC$ is cut in the top of a level table. A sphere of radius $R$ rests in the hole. Find the height of the centre of the sphere above the level of the table top, expressing your answer in terms of $a,b,c,s$ and $R$.

If there are $x$ micrograms of bacteria in a nutrient medium, the population of bacteria will grow at the rate $(2K-x)x$ micrograms per hour. Show that, if $x=K$ when $t=0$, the population at time $t$ is given by $$x(t)=K+K\frac{1-{\mathrm{e}}^{-2Kt}}{1+{\mathrm{e}}^{-2Kt}}.$$ Sketch, for $t⩾0$, the graph of $x$ against $t$. What happens to $x(t)$ as $t\to \infty$?

Now suppose that the situation is as described in the first paragraph, except that we remove the bacteria from the nutrient medium at a rate $L$ micrograms per hour where $K^2>L$. We set $\alpha =\sqrt{K^2-L}.$ Write down the new differential equation for $x$. By considering a new variable $y=x-K+\alpha ,$ or otherwise, show that, if $x(0)=K$ then $x(t)\to K+\alpha$ as $t\to \infty$.

Two thin horizontal bars are parallel and fixed at a distance $d$ apart, and the plane containing them is at an angle $\alpha$ to the horizontal. A thin uniform rod rests in equilibrium in contact with the bars under one and above the other and perpendicular to both. The diagram shows the bards (in cross section and exaggerated in size) with the rod over one bar at $Y$ and under the other at $Z$. (Thus $YZ$ has length $d$.) The centre of the rod is at $X$ and $XZ$ has length $l.$ The coefficient of friction between the rod and each bar is $\mu .$ Explain why we must have $l⩽d.$

Find, in terms of $d,l$ and $\alpha ,$ the least possible value of $\mu .$ Verify that, when $l=2d,$ your result shows that $$\mu ⩾\frac{1}{3}\tan \alpha .$$

Three small spheres of masses $m_1,m_2$ and $m_3,$ move in a straight line on a smooth horizontal table. (Their order on the straight line is the order given.) The coefficient of restitution between any two spheres is $e$. The first moves with velocity $u$ towards the second whilst the second and third are at rest. After the first collision the second sphere hits the third after which the velocity of the second sphere is $u.$ Find $m_1$ in terms of $m_2,m_3$ and $e$. deduce that $$m_{2}e>m_3(1+e+e^2).$$ Suppose that the relation between $m_1,m_2$ and $m_3$ is that in the formula you found above, but that now the first sphere initially moves with velocity $u$ and the other two spheres with velocity $v$, all in the same direction along the line. If $u>v>0$ use the first part to find the velocity of the second sphere after two collisions have taken place. (You should not need to make any substantial computations but you should state your argument clearly.)

Two identical particles of unit mass move under gravity in a medium for which the magnitude of the retarding force on a particle is $k$ times its speed. The first particle is allowed to fall from rest at a point $A$ whilst, at the same time, the second is projected upwards with speed $u$ from a point $B$ a positive distance $d$ vertically above $A$. Find their distance apart after a time $t$ and show that this distance tends to the value $$d+\frac{u}{k}$$ as $t\to \infty .$

Bread roll throwing duels at the Drones' Club are governed by a strict etiquette. The two duellists throw alternatively until one is hit, when the other is declared the winner. If Percy has probability $p>0$ of hitting his target and Rodney has probability $r>0$ of hitting his, show that, if Percy throws first, the probability that he beats Rodney is $$\frac{p}{p+r-pr}.$$ Algernon, Bertie and Cuthbert decide to have a three sided duel in which they throw in order $\mathrm{A},\mathrm{B},\mathrm{C},\mathrm{A},\mathrm{B},\mathrm{C},\dots$ except that anyone who is hit must leave the game. Cuthbert always his target, Bertie hits his target with probability $3/5$ and Algernon hits his target with probability $2/5.$ Bertie and Cuthbert will always aim at each other if they are both still in the duel. Otherwise they aim at Algernon. With his first shot Algernon may aim at either Bertie or Cuthbert or deliberately miss both. Faced with only one opponent Algernon will aim at him. What are Algernon's changes of winning if he:

• (i) hits Cuthbert with his first shot?
• (ii) hits Bertie with his first shot?
• (iii) misses with his first shot?

Advise Algernon as to his best plan and show that, if he uses this plan, his probability of winning is $226/475.$

Fly By Night Airlines run jumbo jets which seat $N$ passengers. From long experience they know that a very small proportion $ϵ$ of their passengers fail to turn up. They decide to sell $N+k$ tickets for each flight. If $k$ is very small compared with $N$ explain why they might expect $$\mathrm{P}(r\text{ passengers fail to turn up})=\frac{{\lambda }^r}{r!}{\mathrm{e}}^{-\lambda }$$ approximately, with $\lambda =Nϵ.$ For the rest of the question you may assume that the formula holds exactly.

Each ticket sold represents $\pounds A$ profit, but the airline must pay each passenger that it cannot fly $\pounds B$ where $B>A>0.$ Explain why, if $r$ passengers fail to turn up, its profit, in pounds, is $$A(N+k)-B\max (0,k-r),$$ where $\max (0,k-r)$ is the larger of $0$ and $k-r.$ Write down the expected profit $u_k$ when $k=0,1,2$ and $3.$ Find $v_k=u_{k+1}-u_k$ for general $k$ and show that $v_k>v_{k+1}.$ Show also that $$v_k\to A-B$$ as $k\to \infty .$

Advise Fly By Night on how to choose $k$ to maximise its expected profit $u_k.$

Suppose $X$ is a random variable with probability density $$\mathrm{f}(x)=A{x}^2\exp (-x^2/2)$$ for $-\infty <x<\infty .$ Find $A$.

You belong to a group of scientists who believe that the outcome of a certain experiment is a random variable with the probability density just given, while other scientists believe that the probability density is the same except with different mean (i.e. the probability density is $\mathrm{f}(x-\mu )$ with $\mu \ne 0$). In each of the following two cases decide whether the result given would shake your faith in your hypothesis, and justify your answer.

• (i) A single trial produces the result 87.3.
• (ii) 1000 independent trials produce results having a mean value $\mathrm{0.23.}$

{[}Great weight will be placed on clear statements of your reasons and none on the mere repetition of standard tests, however sophisticated, if unsupported by argument. There are several possible approaches to this question. For some of them it is useful to know that if $Z$ is normal with mean 0 and variance 1 then $\mathrm{E}(Z^4)=3.${]}