From the people behind the Alan Turing Cryptography Competition.
You are reading the website of the 2019 edition of the MathsBombe Competition, which ended on Sunday 28th April at 11:59 pm

# Solutions

## Puzzle 1

Each banana is formed of two circular arcs. The outer arc is tighter than the inner arc, so the circle which the outer arc comes from must be smaller than the circle which the inner arc comes from. Thus Bob's circle must use the outer arcs and Alice's circle must use the inner arcs.

By drawing lines at right angles to the two arcs at each end of the banana we can find the centres of the two circles: These lines will also have an angle of $$\pi/9$$ between them. Let $$\alpha$$ be the angle formed by a single banana at the centre of Bob's circle. Let $$\beta$$ be the angle formed by a single banana at the centre of Alice's circle. By considering the angles in the blue polygon in the following diagram, we get $$\beta+2\pi/9+(2\pi-\alpha)=2\pi$$ , so $$\alpha=\beta+2\pi/9$$ .

Let n be the number of bananas Alice has. Alice's circle is formed of n bananas, so $$\beta=2\pi/n$$ . Bob's circle is formed of n-12 bananas, so $$\alpha=2\pi/(n-12)$$. Combining these with the above equation gives $$2\pi/(n-12)=2\pi/n+2\pi/9. Solving this gives n=18 or n=-6, and clearly the positive answer must be the correct one. ## Puzzle 2 It's clear that once we have enough apples in our possession, and at least two pounds, it's much better to visit Hazel's shop. So our strategy should be first to visit Sam's shop once and spend \(k$$ pounds to buy $$6k$$ apples, and then visit Hazel's shop many times.

We now think about the best way to spend $$n$$ pounds in Hazel's shop. It's often a good idea to start with trial and error, so we think about the best way to spend $$12$$ pounds in Hazel's shop, $$12$$ is a good number to play with since it is quite small but divisible by 2, 3, and 4.

If we enter with $$a$$ apples we could spend twelve pounds in one go to leave with $$12a$$ apples. Alternatively we could go in twice, spending six pounds each time, to leave with $$6 \times 6a=36a$$ apples, which is clearly better. We could go in six times to get $$2^6 a = 64a$$ apples, or four times to get $$3^4a=81a$$ apples. Playing around a bit with the different examples suggests that spending three pounds each time might be the best strategy.

There's a mathematical justification for this. If we spend $$m$$ pounds in Hazel's shop we multiply the number of apples we have by $$m$$. So we could think that each pound we spent multiplied the number of apples that we have by $$m^{\frac{1}{m}}$$, this represents our value for money. So we're looking for the whole number $$m$$ which maximises $$m^{\frac{1}{m}}$$. Plotting the function $$f(m)=m^{\frac{1}{m}}$$ we see that it reaches its maximum at $$m=e\approx 2.718$$, something you can check for yourself by some tricky differentiation, and that the maximum value of $$f(m)$$ when $$m$$ is a whole number is given by $$m=3$$.

All of this tells us that once we have enough apples and $$3n$$ pounds remaining, our best strategy is to visit Hazel's shop $$n$$ times spending $$3$$ pounds each visit.

So one sensible option would be to visit Sam's shop, spend two pounds to buy $$12$$ apples, and then visit Hazel's shop $$16$$ times, multiplying the number of apples we have by $$3$$ each time, to end up with $$12\times 3^{16}$$ apples.

However we need to check that there isn't a more intelligent way of spending our first few pounds, before we spend our last $$3n$$ pounds with Hazel. $$50 = 2+(3\times 16)$$ so we check for the best ways to spend 2, 5 or 8 pounds. In each case we see that an optimal solution is to spend 2 pounds in Sam's shop, and then visit Hazel's shop some number of times spending three pounds each visit. An equally good solution is to spend 3 pounds in Sam's shop, then spend two pounds in Hazel's shop, then to visit Hazel's shop many times spending three pounds on each visit.

Hence the maximal number of apples that we can get is $(6+6)\times 3^{16}=(6+6+6)\times 2 \times 3^{15}=516560652.$

N.B. If you don't think the final paragraph involving the first few pounds was rigorous enough, you could think about $f(m)$ and conclude that the best final move is always to either spend 2 pounds at Hazel's shop, or spend 3 pounds at Hazel's shop (there's no point spending 4 or 5 or 6 pounds in Hazel's shop since it's always at least as good to break this up into multiple visits spending 2 or 3 pounds). Then you could prove by induction that if $$p(n)$$ represents the maximum number of apples you can obtain with $$n$$ pounds, then for $$n\geq 1$$ we have $$p(3n)=2\times 3^{n+1}\\ p(3n+1)=8\times 3^n\\ p(3n+2)= 4\times 3^{n+1}.$$

## Puzzle 3

The answer is: 49.

There are 4950 dominoes in total. One could write down a chain of 4901 dominoes (more realistically: write down an algorithm that would generate this chain). Indeed, trying to write down systematically the longest chain you can will give you some ideas as to one way to approach this. However, just because a systematic approach gives you a chain of 4901 dominoes, that doesn't mean that there isn't a less systematic approach that gives a longer chain.

We'll prove that a systematic approach is, in fact, optimal. To do this, it's easier to work with a more general problem: Suppose you have a set of dominoes with numbers 1 to $$n$$; again there are no blanks, no doubles, and just one of each type of domino. What's the largest chain of dominoes that can be constructed? For convenience, we'll assume $$n$$ is even (the case when $$n$$ is odd is slightly different). We'll show that the longest chain is $$\frac{n^2-2n+2}{2}.$$

First we'll show that the longest chain cannot be longer than this value. First note that each number $$k$$ appears on exactly $$n-1$$ dominoes.

Take a chain of dominoes and write down all the numbers that appear in sequence. Suppose the numbers that start and end the sequence are different (we can assume, by relabelling if necessary, that the numbers at the end are 1 and 2). Any other number in the sequence must appear an even number of times. Thus (as $$n-1$$, the number of dominos that each number appears on is odd) each number other than 1,2 appear on at most $$n-2$$ dominoes. The numbers $$1,2$$ appear on at most $$n-1$$ dominoes. Hence in the sequence of numbers, 1 and 2 appear at most $$n-1$$ times and $$3, \ldots, 100$$ appear at most $$n-2$$ times. Thus the number of dominoes is at most $\frac{1}{2}\left( (n-1)+(n-1)+(n-2)(n-2) \right) = \frac{n^2-2n+2}{2}.$

(If the sequence starts and ends with the same number, then the same argument gives an upper bound of $$(n^2-2n+1)/2$$, which is less than our upper bound..

Now we construct a chain of dominoes of length given by our formula. We'll do this by induction (you can read about induction on Wikipedia here).

When $$n=2$$ there is just one chain: 1-2. Note that $$(n^2-2n+2)/2 =1$$ when $$n=2.$$

Suppose we've constructed a chain $$C_n$$ of dominoes with numbers $$1,2,\ldots, n$$ of length $$(n^2-2n+2)/2$$. Suppose $$C_n$$ starts with a 1 and ends with a 2. We'll show how to construct from this a chain $$C_{n+2}$$ of dominoes with numbers $$1,2, \ldots, n, n+1, n+2$$ of length $$((n+2)^2-2(n+2)+2)/2$$ (i.e.\ the same formula, but with $$n$$ replaced by $$n+2$$), again starting with a $$1$$ and ending in a $$2$$. By induction, this will prove what we want.

The extra dominoes we've added are $$i-j$$ where $$i=1,2,\ldots, n+2$$ and $$j= n+1, n+2$$ (ignoring $$(n+2)-(n+2)$$). To the chain $$C_n$$ append the following dominoes to form $$C_{n+2}$$: $$2-(n+1),\\ (n+1)-3,\\ 3-(n+2),\\ (n+2)-4,\\ 4-(n+1),\\ (n+1)-5,\\ 5-(n+2),\\ (n+2)-6,\\ \ldots \\ 2j-(n+1),\\ (n+1)-(2j+1),\\ (2j+1)-(n+2),\\ (n+2)-(2j+2)\\ \ldots\\ (n-4)- (n+1) ,\\ (n+1)-(n-3),\\ (n-3)-(n+2) ,\\ (n+2)-(n-2),\\ \ldots\\ (n-2, n+1),\\ (n+1)-1,\\ 1-(n+2),\\ (n+2)-2.\\$$

There are $$2n$$ dominoes added to $$C_n$$. This gives a chain of length $\frac{n^2-2n+2}{2} + 2n = \frac{(n+2)^2-2(n+2)+2}{2},$ which is what we wanted.

## Puzzle 4

The set-up of the problem can be thought of as follows: there's a circle (the coastline) divided up into 12 equal segments (like a clockface). Put the celebrity at 12 o'clock and the zombie at 6 o'clock. Each minute, the zombie moves clockwise with probability 2/3 and anticlockwise with probability 1/3. Each move the zombie makes is independent of the previous move. The celeb cannot move. Once the zombie reaches the celebrity, there's a 3 minute commercial break. Thus we need to calculate the expected time (in minutes) for the zombie to reach the celebrity and then add 3.

We'll work out the answer in a more general setting. Suppose that the island has circumference $$C$$ ($$C=12$$ in the above), the zombie starts at position $$n$$ ($$n=6$$ in the above). With probability $$p$$ the zombie moves clockwise (so increases it's position) and with probability $$q = 1-p$$ the zombie moves anticlockwise (so decreases it's position). Let $$S$$ be the number of minutes before the zombie meets the celebrity. We'll also write $$P_j$$ for the position of the zombie after $$j$$ minutes. We're interested in the expected value of $$S$$, given that the zombie started in position $$n$$; denote this by $$E(S \mid P_0 = n)$$; call this $$E_n$$ for short. Clearly $$E_0=0$$ and $$E_C=0$$ (if the zombie starts in the same place as the celebrity then the game is over immediately). For $$n=1,2,\ldots, C-1$$, we can find the following relationship for the term $$E_n$$. As the zombie moves independently each minute, we have (for $$n = 1,2,\ldots, n-1$$) \begin{eqnarray*} E_n & = & E(S \mid P_0=n) \\ & = & E(S \mid P_1=n+1)p + E(S \mid P_1=n-1)q \\ & = & ( 1 + E(S \mid P_0=n+1))p + (1+E(S \mid P_0=n-1))q \\ & = & 1 + pE_{n+1} + qE_{n-1}. \end{eqnarray*} One could, at this stage, substitute in our values of $$C,n,p,q$$ and calculate $$E_6$$. Alternatively, we can solve for $$E_n$$ explicitily. Note that the above equation can be written as $$p E_{n+1}-E_n + qE_{n-1} = -1, E_0=E_C=0. (*)$$ This is called a linear recurrence relation and there is a general theory on how to solve them. See Wikipedia \verb!https://en.wikipedia.org/wiki/Recurrence_relation!.

The method is to first solve $$\label{eqn:recrel1} p E_{n+1}-E_n + qE_{n-1} = 0. (**)$$ This has solutions of the form $$\lambda^n$$ where $$\lambda$$ is a solution of $$p\lambda^2-\lambda+q=0$$ (i.e. substitute $$E_n$$ by $$\lambda^n$$). Solving this quadratic gives $$\lambda = (1-p)/p, 1$$. Thus (**) has solutions of the form $$E_n = A ((1-p)/p)^n$$ and $$E_n = B \times 1^n = B$$ where $$A,B$$ are constants (yet to be determined).

We also need to find what is called a particular solution of equation (**). These are given by solutions of the form $$E_n=an+b$$ and we have to find out the values of $$a,b$$. Substituting $$E_n=an+b$$ in the above equation we see that we can take $$b=0$$ and $$a=1/(1-2p)$$. Hence $$E_n = n/(1-2p)$$ is a particular solution of (**).

Hence the general solution to (**) has the form $E_n = \frac{n}{1-2p} + A\left( \frac{1-p}{p} \right)^n + B.$ Substituting in $$E_0=0$$ and $$E_C=0$$ we have the two simultaneous equations $A+B =0, \frac{C}{1-2p} + A\left( \frac{1-p}{p} \right)^C + B =0.$ These can be easily solved to see that $A = -B = \frac{-C}{1-2p} \frac{1}{\left( \frac{1-p}{p} \right)^C-1}.$

The general solution for $$E_n$$ is then $E_n = \frac{n}{1-2p} - \frac{C}{1-2p} \times \left(\frac{ \left( \frac{1-p}{p}\right)^n - 1} { \left( \frac{1-p}{p}\right)^C - 1}\right).$ Substituting in $$C=12, n= 6, p=2/3$$ we have that $$E_6 = 17.45$$ (to 2 decimal places). As the commercial break is 3 minutes, the expected time between commercial breaks is $$20.45$$ minutes.

This is very closely related to a well-known problem in probability theory called the Gambler's Ruin. You can read about this on Wikipedia here.

## Puzzle 5

We work inductively. First observe that, since $$\beta^{3}=\beta^2+1$$, to buy a piece of fruit costing $$\beta^3$$ pounds we need to use two coins, a one pound coin and a $$\beta^2$$ pounds coin. More generally, if $\beta^m=a_1+a_2\beta+a_3\beta^2$ then $\beta^{m+1}=\beta.\beta^m=a_1\beta+a_2\beta^2+a_3\beta^3= a_3+a_1\beta+(a_2+a_3)\beta^2.$ We can represent this multiplication as a $$3\times 3$$ matrix, we want $A\left( \begin{array}{c}a_1\\a_2\\a_3\end{array}\right)=\left( \begin{array}{c}a_3\\a_1\\a_2+a_3\end{array}\right)$ so $A=\left(\begin{array}{ccc}0&0&1\\1&0&0\\0&1&1\end{array}\right).$ Then $$\beta^{20}=\beta^{20}.1$$ can be written as $$b_1+b_2\beta+b_3\beta^2$$ where $A^{20}\left(\begin{array}{c}1\\0\\0\end{array}\right)=\left(\begin{array}{c}b_1\\b_2\\b_3\end{array}\right).$ Putting this into (for example) wolfram alpha gives $A^{20}=\left(\begin{array}{ccc}406&595&872\\277&476&595\\595&872&1278\end{array}\right).$ and so $A^{20}\left(\begin{array}{c}1\\0\\0\end{array}\right)=\left(\begin{array}{c}406\\277\\595\end{array}\right).$ Thus we have to pay $$406$$ pounds plus $$277\beta$$ pounds plus $$595\beta^2$$ pounds, a total of $$1278$$ coins.

By using matrices, the above solution let us see exactly which coins are necessary, it is possible to get the answer by doing a recurrence relation.

## Puzzle 6

After the earthquake, the North Wall and the South Wall are straight lines which are no longer parallel; let $$O$$ be their point of intersection. From the data given in the problem, we determine that the laser beam leaves $$N_0$$ in the direction perpendicular to the North Wall. Denote the distance between $$O$$ and $$N_0$$ by $$d$$: $$d = O N_0.$$

To calculate the distance travelled by the laser beam, it is convenient to reflect the North Wall in the South Wall, and let the beam continue straight through the South Wall until it hits the image of the North Wall (see diagram). If $$\alpha$$ is the angle between the North Wall and the South Wall, i.e., the angle $$N_0OS_1$$, then the reflected North Wall --- the line $$ON_1$$ --- forms angle $$\alpha$$ with the South Wall. That is, the angle $$S_1ON_1$$ is $$\alpha$$, and the angle $$N_0 O N_1$$ is $$2\alpha$$.

Continuing in the same manner, we can construct the path of the laser beam as the straight line $$N_0 N_{50}$$ which meets, at the point $$N_{50}$$, the 50th reflection of the North Wall. Let $$a$$ denote the length of the beam path from $$N_0$$ to $$N_{50}$$. Then, considering the right-angled triangle $$ON_0N_{50}$$ on the diagram, we conclude that $a = N_0N_{50}=d \tan x$ where the angle $$N_0 O N_{50}=x$$ is equal to $$50\times 2\alpha$$. In the same way, if $$b$$ denotes the length of the path between $$N_{50}$$ and $$N_{100}$$, then $a+b= N_0N_{100}=d \tan 2x,$ and finally the (unknown) length $$c$$ of the path between $$N_{100}$$ and $$N_{150}$$ satisfies $a+b+c = N_0N_{150}=d \tan 3x.$ Our goal is to express $$c$$ in terms of $$a$$ and $$b$$. Having worked out things that we need to understand, we could guess that formulae for tan 2x and tan 3x probably exist, a quick google gives: $$\tan 2x = \frac{2\tan x}{1-\tan^2 x}, \qquad \tan 3x = \frac{\tan x + \tan 2x}{1 - \tan x \tan 2x}.$$ From the double angle formula it follows that $1-\tan^2 x = 2 \tan x / \tan 2x = 2a/(a+b),$ hence $\tan^2 x = 1-(2a/(a+b)) = (b-a)/(a+b).$ Substitute this into the triple angle formula: $$d\tan 3x = \frac{d\tan x + d\tan 2x}{1 - (2 \tan^2 x / (1-\tan^2 x))} = \frac{a+(a+b)}{1 - (b-a)/a } = \frac{2a^2+ab}{2a-b}.$$ It follows that \begin{align*} c & = d\tan 3x-(a+b) \\ &= \frac{2a^2+ab-(2a-b)(a+b)}{2a-b} = \frac{2a^2+ab-(2a^2+ab-b^2)}{2a-b} \\ &=\frac{b^2}{2a-b}. \end{align*} It's time to substitute the numerical values given in the problem. We are given that $$a=332.8935$$m and $$b=662.687$$m. Then $$2a-b=665.787-662.687=3.1$$m. We calculate, taking care not to lose any significant figures: $$c = \frac{b^2}{2a-b} = \frac{662687^2}{31}10^{-5} = \frac{439154059969}{31}10^{-5}= 14166259999\times 10^{-5}\text{ m}$$ which is the answer given above.

## Puzzle 7

To make life easier we split this problem into different cases, according to when emails 29 and 30 arrive.

Case 1. Emails 29 and 30 arrive before 4pm. There are $$2^{29}$$ options.

Case 2a. Email 29 arrives before 4, and has not been replied to by 4. Email 30 has not arrived by 4.

We have a set $$U\subset\{1,\cdots,27\}$$ of emails that also haven't been replied to. Let $$U$$ have $$k$$ elements. Email 30 can't be replied to first, else we would be in case 1, so we have $$k+1$$ places where email 30 could arrive. So we have $\sum_{k=0}^{27} \left(\begin{array}{c}27\\k\end{array}\right)(k+1)$ options. The $$k=0$$ case here is the list $$(29,30)$$, which does not appear elsewhere.

Case 2b. Email 29 arrives before 4 and is replied to before 4. Email 30 has not arrived by 4.

We have a {\bf non-empty} set $$U\subset\{1,\cdots,27\}$$ of emails that haven't been replied to by 4. Email 30 isn't replied to first, else we would be in case 1. So we have $\sum_{k=1}^{27} \left(\begin{array}{c}27\\k\end{array}\right)(k).$

Case 3a. Neither emails 29 nor email 30 arrive before 4. Email 29 is replied to before email 30.

There is a non-empty set $$U\subset\{1,\cdots,27\}$$ of emails that haven't been replied to at 4. Let $$k$$ be the number of elements of $$U$$. Then we can't answer $$29$$ first, since that is dealt with by 2a. We can't answer 30 first since then we would start 30,29 and be in case 1. So we have $$k$$ choices of where 29 can go, and $$k+1$$ choices of where 30 can go. But since we want $$29$$ to be replied to before $$30$$, this halves our options. So we get $\sum_{k=1}^{27} \left(\begin{array}{c}27\\k\end{array}\right)(\frac{k(k+1)}{2}).$

Case 3b. Neither emails 29 nor email 30 arrive before 4. Email 29 is replied to after email 30. This can only happen if 29 and 30 are next to each other, and not at the start since that was dealt with in case 2a. Then we get $\sum_{k=1}^{27}\left(\begin{array}{c}27\\k\end{array}\right)k$ options.

{\bf Total}$2^{29}+\underbrace{1}_{k=0\mbox{ case from 2a}}+ \sum_{k=1}^{27}\left(\begin{array}{c}27\\k\end{array}\right)\left(k+k+k+1+\frac{k(k+1)}{2}\right)=19696451584$

## Puzzle 8

This is related to a classical problem in computer science known as the subset sum problem. subset sum problem

The problem is NP-complete meaning essentially that it's easy to check a solution, but hard to find that solution. In this case, checking whether two subsets have the same sum is very easy, but it can be very laborious to find those subsets.

For the particular problem we can relatively quickly establish upper and lower bounds for N. For the upper bound we can use the pigeon-hole principle. For a selection of size N there are $$2^N$$ subsets, including the complete set and the empty set. The total number of possible sums is certainly less than the highest possible sum which is 24 + 23 + 22 + ... + 25 - N. If there are more subsets than possible sums, the it follows that there must be (at least) two subsets with the same sum. Listing the values for different N in a table we obtain $\begin{array}{ccc} N& \# Subsets& \# Sums (upper bound)\\ 2& 4 & 47\\ 3 & 8 & 69\\ 4 & 16 & 90\\ 5 & 32 & 110\\ 6 & 64 & 129\\ 7 & 128 & 147\\ 8 & 256 & 164\\ \end{array}$

Thus, we find that the upper bound for N is 8.

For the lower bound we can think about finding one specific selection that does not have any subsets with the same sum. Every integer has a unique (binary) representation as the sum of powers of two, so if we choose the selection {1,2,4,8,16} then we definitely avoid having two subsets with the same sum. Thus we can establish N=5 as the lower bound.

We have determined that $$5 < N \leq 8$$ and now we must work a little harder to find the exact value of N.

In fact we can generalise our argument to find a selection of size N=6 that does not have any subsets with the same sum. We want to choose the largest number of integers, so we want the differences between the selected integers to be as small as possible and, of course, no subsets can sum to the same value. If we start from 1 and follow this procedure we end up with the selection {1,2,4,8,16}. An important insight is that we don't have to start this process from 1. If we start from the largest possible integer, 24, and then choose smaller and smaller integers so that none of the sums have the same value, we obtain (eventually) {11,17,20,22,23,24}, which is the only subset of size 6 for which none of the subsets have the same sum. This latter fact can be checked by brute force computation or by repeating the process described above with different starting points.

We now know that the required answer is either 7 or 8. The only way that we can get a bigger subset with the desired property is by adding one more integer to the set {11,17,20,22,23,24}. We find that there is no integer smaller than 11 that we can add and still preserve the property that no subsets have the same sum. Thus, the required answer is 7 {11,17,20,22,23,24}

MathsBombe Competition 2019 is organised by the The School of Mathematics at the University of Manchester.