Welcome guest.   Log in
From the people behind the Alan Turing Cryptography Competition.
You are reading the website of the 2018 edition of the MathsBombe, which ended on Saturday 28th April at 11:59 pm
Home
Register
FAQ
Rules
For
Teachers
News
Leaderboard
Forum
Archive

Solutions.

Puzzle 1

This problem is a little more tricky that it might appear. We can work out a theoretical maximum by simple counting arguments, but it is not obvious that this maximum is attained for any of the possible sets of three integers. We must therefore work out which set has the smallest number of results in common.

First, let's enumerate all the possibilities in general. We can use each integer at most once, but we do not have to use all the integers or an operator. We can therefore have the three integers themselves. Now, let us consider all numbers that can be made from two of the integers, in which case we can only have one operation. Addition and multiplication are commutative, which means that the number of possible outcomes is simply the number of ways that the two integers can be selected and is therefore three for each operation. Subtraction and division are non-commutative which means that each operation has six possible outcomes and therefore the total number of outcomes for combinations of two integers is \(3 + 3 + 6 + 6 = 18\).

If we finally consider the numbers that can be made using all three integers then we use two operations which leads to sixteen possible combinations, assuming that the order of operations matters. However, we must be careful to avoid counting the same combination twice and be aware of when the order of operations affects the outcome. Let us consider the pairs of operations in sequence, using \(a\), \(b\) and \(c\) to represent our integers:

$$a + b + c \quad\mbox{gives only one outcome}$$ $$a + b - c \quad\mbox{has three possible outcomes}$$ $$a - b + c \quad\mbox{has no new outcomes}$$ $$a - b - c \quad\mbox{has three possible outcomes}$$ $$a \times b \times c \quad\mbox{gives only one outcome}$$ $$a \times b / c \quad\mbox{gives three possible outcomes}$$ $$a / (b \times c) \quad\mbox{gives three more possible outcomes}$$ $$ a / b / c \quad\mbox{does not give any more outcomes}$$ $$ a + (b \times c), (a + b) \times c \quad\mbox{gives six possible outcomes}$$ $$ a + (b/c), (a+b)/c \quad\mbox{gives nine possible outcomes}$$ $$ a - (b\times c), (a-b)\times c \quad\mbox{gives nine possible outcomes}$$ $$ a - (b / c), (a-b)/c \quad\mbox{gives twelve possible outcomes}$$ $$ a \times b + c \quad\mbox{gives no new outcomes}$$ $$ (a \times b) - c \quad\mbox{gives three new outcomes}$$ $$ a / (b +c), (a/b)+c \quad\mbox{gives three new outcomes}$$ $$ a / (b - c), (a/b) - c \quad\mbox{gives twelve new outcomes}$$

The total is thus \(1 + 3 + 3 + 1 + 3 + 3 + 6 + 9 + 9 + 12 + 3 + 3 + 12 = 68\).

The grand total is then \(18 + 68 + 3 = 89\).

In fact, this total is never attained, but the set with the fewest overlaps is \(\{6,8,9\}\), for which the number \(6\) can be obtained in three ways and the number \(-6\) can be obtained in two ways. Thus, the total number of different possible numbers in this case is 86. This result can be checked with a simple computer program.

Puzzle 2

Refer to each Goblin or Nilbog by the first letter of its name. If a monster is a Goblin then we'll write that it always lies; if the monster is a Nilbog then we'll write that it tells the truth. By saying two monsters are the same we mean that they are either both Goblins or both Nilbogs. The clues are then:

A: F says A always lies
B: Exactly one of I, M tells the truth
C: D and L are the same as M
D: B = Y
E: T = E
F: X and Q tells the truth
G: Z != G
H: G always lies
I: M tells the truth
J: B says F tells the truth
K: L tells the truth
L: R always lies
M: E always lies
N: W always lies or Z tells the truth
O: A and Q both always lie
P: D = H
Q: O would say Q tells the truth
R: X and B both tell the truth
S: L always lies
T: C would say T tells the truth
U: I would say R always lies
V: R would say U tells the truth
W: I tells the truth or N lies
X: R would say S tells the truth
Y: K and S both always lie
Z: H always lies
  1. Consider clue I. If I is telling the truth then M always tells the truth. If I is lying then M is lying. Hence I = M (but we don't know whether they both lie or both tell the truth).
  2. Clue B says that I != M. Hence B is lying.
  3. Clue R says that B tells the truth. Hence R must be lying. (Note that we can't say anything about X from clue R.)
  4. Clue L says that L must be telling the truth. Hence K is also telling the truth (K's clue) and S is lying (S's clue).
  5. Clue Y says that both K and S both lie. But K tells the truth. So Y is lying. As both B and Y are lying, Clue D is true; hence D tells the truth.
  6. Consider clue X. Suppose that X lies. If X is lying then R would actually say that S lies. We know that R lies, this would actually mean that S tells the truth. But we know S lies, so our assumption that X lies is wrong. Hence X tells the truth.
  7. Consider clue F. Suppose that F is telling the truth. Then clue F tells us that X tells the truth (we already knew this) and Q tells the truth. Clue Q then tells us that O would say that Q is telling the truth (which indeed Q is), so O must also be telling the truth. Clue O tells us that both A and Q both lie. But this contradicts the fact that we've just argued that Q is telling the truth. Hence our assumption that F is telling the truth is wrong, so F must be lying.
  8. As F is lying, it's not true that both X and Q tell the truth. We know that X does tell the truth. So this tells us that Q must be lying.
  9. Knowing that Q is lying, clue Q tells us that O would actually say that Q lies. This is indeed the case, hence O is telling the truth.
  10. Clue O now tells us that A lies.
  11. Consider Clue J. We know B lies. As F lies, B would indeed say that F told the truth. Hence J is making a true statement, so is telling the truth.
  12. Consider Clue M. We'll consider the two cases (M tells the truth, M lies) separately. First suppose that M tells the truth. Then E must lie. Clue E says that T and E are different, hence T must tell the truth. Now consider the other case where M lies. In this case, clue M says that E is telling the truth; it then follows from clue E that T is also telling the truth. Hence, no matter whether M is telling the truth or lying, we must have that T is telling the truth.
  13. Clue T tells us that C is making a true statement. Hence C tells the truth.
  14. Clue C tells us that M is the same as D and L (who are both telling the truth). Hence M is telling the truth. Clue M then tells us that E is lying.
  15. Clue I is making a true statement about M. Hence I tells the truth.
  16. Consider clue U. Monster I tells the truth, and R does indeed lie. Hence U is telling the truth.
  17. Consider clue V. Suppose V tells the truth. Then R would indeed say that U tells the truth. We know that R lies, so this would mean that U lies. But U tells the truth, a contradiction. Hence V must lie.
  18. Consider clue Z. Suppose Z tells the truth. Then H lies. Clue H then tells us that G tells the truth. Clue G tells us that Z and G are different. But we've just argued that both Z and G tell the truth, a contradiction. Hence Z must lie.
  19. Clue Z then tells us that H tells the truth.
  20. Clue H then tells us that G lies. (Just to check: G lies, so clue G tells us that both Z and G are the same, which indeed they are.)
  21. As both D and H tell the truth, clue P implies that P tells the truth.
  22. Consider clue W. Suppose W always lies. Then clue W tells us that monster I always lies and N tells the truth. But we already know that monster I tells the truth, a contradiction. Hence W must tell the truth. (Note that, even though we know W tells the truth, clue W doesn't tell us anything about whether N lies or not.)
  23. Finally, consider clue N. If N is telling the truth then either W lies or Z tells the truth. But W tells the truth and Z lies, so neither of these possibilities can happen. Hence N must be lying.

Hence (denoting T for 'telling the truth' and L for 'lying') we can assign

ABCDEFGHIJKLM NOPQRSTUVWXYZ
LLTTLLLTTTTTT LTTLLLTTLTTLL

Reverting back to 'Goblins always lie' and 'Nilbogs always tell the truth' this gives

ABCDEFGHIJKLM NOPQRSTUVWXYZ
GGNNGGGNNNNNN GNNGGGNNGNNGG

so the required answer is GGNNGGGNNNNNNGNNGGGNNGNNGG

Puzzle 3

This is the so-called secretary problem . We must work out the probability that the strategy selects the best candidate as function of \(k\) and then find the value of \(k\) for which this is maximised.

Firstly we should assume that the candidates interview in a random order in which case the position of the best candidate will be uniformly distributed on the range \(\{1,\ldots,15\}\). Next, we note that if \(k=1\) then the first candidate will always be selected and this will be the best with probability \(1/15\).

For \(k > 1 \), given that best candidate has the \(j\)-th interview then the probability that that candidate is selected is \(0\) if \(j < k-1\). If \(j \geq k\), then the \(j\)-th candidate will be selected if the best candidate in the first \(j-1\) interviews was interviewed in the first \(k-1\) interviews. The position of the "second best" candidate will have a uniform distribution, with probability of interviewing in any of the \(j-1\) positions being equal to \(1/(j-1)\). The probability that the interview takes place in the first \(k-1\) interview is then $$ \sum_{i=1}^{k-1} \frac{1}{j-1} = \frac{k-1}{j-1}.$$

Hence, $$P(\mbox{Best candidate selected} | \mbox{Best candidate is in } j\mbox{-th position}) = \begin{cases} 0 & j < k \\ \frac{k-1}{j-1} & j \geq k.\end{cases}$$

From the laws of conditional probability $$P(\mbox{Best candidate selected}) = \sum_{j=1}^{15} P(\mbox{Best candidate selected} | \mbox{Best candidate is in } j\mbox{-th position}) \times P(\mbox{Best candidate is in } j\mbox{-th position}).$$ $$ \Rightarrow\quad P(\mbox{Best candidate selected}) = \sum_{j=k}^{15} \frac{k-1}{j-1} \frac{1}{15} = \frac{k-1}{15} \sum_{j=k}^{15} \frac{1}{j-1}.$$

Thus we can now tabulate the probabilities that each strategy selects the best candidate as a function of \(k\). $$ \begin{array}{ccccccccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ 0.0666667 & 0.216771 & 0.300208 & 0.350312 & 0.378194 & 0.38941 & 0.387292 & 0.374062 & 0.351309 & 0.320223 & 0.281729 & 0.236569 & 0.185348 & 0.128571 & 0.0666667 \end{array} $$ Thus, the value of \(k\) that selects the best candidate with maximum probability is when \(k = 6\).

Puzzle 4

If \(A\) is Professor Alice's cash amount (in pence), \(C\) is Professor Chuck's cash amount, then \(A - C\) is always divisible by the number \(L\) of lecturers. Indeed, initially \(A - C\) is \(0\), and \(A - C\) does not change when Alice and Chuck receive the same amount of cash from a lecturer; when Alice or Chuck gives \(X\) pence to each lecturer, \(A - C\) changes by \(LX\) which is a multiple of \(L\).

Since at the end of the month \(A - C\) is \(100000 - 101 = 99899 = 283 \times 353\) (a product of two primes), the divisor \(L\) of \(99899\) is either \(1\) (impossible as we know of at least two lecturers), or \(283\), or \(353\), or \(99899\) (impossible as there are only \(10, 000\) employees). The same reasoning applied to the difference between Lecturer Bob's and Lecturer Dave's amounts of cash shows that the number \(P\) of professors is also a divisor of 99899. Since \(1 < P < L\), the only possibility is \(P = 283, L = 353\). Hence the number of security guards is \(10000 - (283 + 353) = 9364\).

Puzzle 5

There are two parts to this problem. Which coins could make up the change and what is the volume of each coin. The change is of course 60 pence and this could be made up from any coins up to the value of 50 pence. Gathering data from the Royal Mint we find the following dimensions:

$$\begin{array}{lcc} \mbox{Coin} & \mbox{Diameter, } D \mbox{(mm)} & \mbox{Thickness, } h \mbox{(mm)} \\ \hline \\ 1 p & 20.3 & 1.65 \\ 2 p & 25.9 & 2.03 \\ 5 p & 18.0 & 1.7 \\ 10 p & 24.5 & 1.85 \\ 20 p & 21.4 & 1.7 \\ 50 p & 27.3 & 1.78 \\ \end{array}$$

We now need to work out the volume of each coin. For the coins with circular faces this is straightforward. The volume is simply the area of the circle multiplied by the thickness \( h \pi D^{2} / 4 \). The calculation is more difficult for the 20 and 50 pence pieces because they are actually Reuleaux heptagons (non-circular shapes of constant width). If you look carefully around the internet you will find a specimen exam question on this very problem. The question reveals that the face area of the 20 and 50 p coins is given by $$ \frac{D^{2}}{2} \left(\pi - 7 \tan (\pi/14)\right) \approx 0.7719 D^{2}.$$ and the volume is simply given on multiplication by the thickness.

Thus, we are now in a position to calculate the required volumes $$\begin{array}{lc} \mbox{Coin} & \mbox{Volume } (\mbox{mm}^{3})\\ \hline \\ 1 p & 534.030\\ 2 p & 1069.511 \\ 5 p & 432.597 \\ 10 p & 872.155\\ 20 p & 600.983\\ 50 p & 1024.074 \\ \end{array}$$ and evaluate the minimum volume of the change. Let us consider the possibilities for two or three coins. Four or more coins that sum to 60p will definitely lead to greater volumes.

\begin{array}{cc} \mbox{Coins} & \mbox{Volume } (\mbox{mm}^{3})\\ \hline 50p, 10p & 1896.229 \\ 50p, 5p, 5p & 1889.268 \\ 20p, 20p, 20p & 1802.949 \\ \end{array}

Thus, the minimum volume is achieved when you have three 20 pence pieces and it is 1803 mm\(^3\) to four significant figures.

Puzzle 6

The important point to recognise here is that the thickness of the wood can be used to make a box with a greater surface area than the 1.5 m\(^2\) provided by the upper surface of the sheet.

The maximum possible surface area occurs if there is an extra thickness of wood on both sides of every face. If \(l\) is the length of a side of the final cube and \(t\) the thickness of the wood then the total surface area that must be cut from the sheet surface is given by

  • six square "faces" of area \((l-2t)^2\),
  • 12 infill "edges" of area \((l-2t)t\),
  • 8 cubical "vertices" of area \(t^2\).

The total surface area of the box is therefore $$A = 6(l^2 - 4tl + 4t^2) + 12lt - 24t^2 + 8t^2 = 6l^2 -12 lt + 8 t^2,$$ which will be less than \(6l^2\) for sufficiently large \(l > \frac{2}{3} t\).

We now need to find six pieces with dimensions of the form \((l - a_{i} t) \times (l - a_{i+1} t)\) that sum to give \(A\). There are 12 different constants \(a_{1} \ldots a_{12}\), but they can only take the values 0, 1 or 2. We are not allowed fractional thicknesses owing to the restriction on the types of cuts that can be made. Thus comparing the sum of the areas of the six pieces to the expression for \(A\), we need to consider all possibilities where

$$\sum_{i=1}^{12} a_{i} = 12 \quad \mbox{and} \quad \sum_{i=1}^{6} a_{2i-1} a_{2i} = 8.$$

The product \(a_{2i-1} a_{2i}\) can only take the four possible values:

  • \(0\) made from the pairs \( \{a_{2i-1}, a_{2i}\} = \{0,0\}, \{0,1\}, \{0,2\}\),
  • \(1\) from the pair \(\{1,1\}\),
  • \(2\) from \(\{2,1\}\),
  • \(4\) from \(\{2,2\}\).

Considering the fact that the sum of products must be \(8\) we have the following possibilities for the values of the 6 products (exact assignment order doesn't matter)

$$\begin{array}{cccccc} a_1 a_2 & a_3 a_4 & a_5 a_6 & a_7 a_8 & a_9 a_{10} & a_{11} a_{12} \\ \hline \\ 4 & 4 & 0 & 0 & 0 & 0 \\ 4 & 2 & 2 & 0 & 0 & 0 \\ 4 & 2 & 1 & 1 & 0 & 0 \\ 4 & 1 & 1 & 1 & 1 & 0 \\ 2 & 2 & 2 & 2 & 0 & 0 \\ 2 & 2 & 2 & 1 & 1 & 0 \\ 2 & 2 & 1 & 1 & 1 & 1 \\ \end{array}$$

We now need to include the constraint that the sum of all coefficients must equal \(12\), which rules out the last two rows. The others lead to the following possibilities for coefficients (again the exact order of the assignment of pairs doesn't matter):

$$\begin{array}{cccccccccccc} a_{1} & a_{2} & a_{3} & a_{4} & a_{5} & a_{6} & a_{7} & a_{8} & a_{9} & a_{10} & a_{11} & a_{12} \\ \hline \\ 2 & 2 & 2 & 2 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 2 & 2 & 2 & 2 & 2 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 2 & 2 & 2 & 2 & 2 & 0 & 2 & 0 & 0 & 0 & 0 & 0 \\ 2 & 2 & 2 & 1 & 2 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 2 & 2 & 2 & 1 & 2 & 1 & 2 & 0 & 0 & 0 & 0 & 0 \\ 2 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 2 & 1 & 2 & 1 & 2 & 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ \end{array}$$

The question is now how can we arrange these pieces to waste the least amount of wood given the aspect ratio of the sheet. In fact each of these configurations can be arranged into a sheet of size \( (3l - 2t) \times (2l - 2t) \), and noting that $$ A = 2(3l - 2t)(l - t) - 2t(l - 2t),$$ we conclude that a surface area \(2t(l-2t)\) of the wood will be wasted if our sheet were \( (3l - 2t) \times (2l - 2t) \). However, the sheet has fixed dimensions of 1m by 1.5m and we now need to work out the value of \(l\) given that \(t = 3\)mm.

Identifying the bounding dimensions of the sheet we have that $$2l -2t = 1\mbox{m} \Rightarrow 2l = 1.006\mbox{m} \Rightarrow l = 50.3\mbox{ cm}$$ or $$ 3l - 2t = 1.5\mbox{m} \Rightarrow 3l = 1.506\mbox{m} \Rightarrow l = 50.2 \mbox{cm}$$ We must choose the shorter size in which case we obtain l = 50.2cm and then our total required surface area is $$A = 6(l-t)^{2} + 2 t^{2} = 6(0.499)^2 + 2 \times0.003^2 = 1.494024 \mbox{m}^2.$$ Thus the wasted wood area is \(1.5 - 1.494024 = 0.005976 m^2 = 59.76 \mbox{cm}^2\) which gives a volume of \( 59.76 \times0.3 = 17.928 \mbox{cm}^3\).

Note that if the sheet were exactly the right dimensions we would only have wasted \(2t(l-2t)t = 8.928 \mbox{cm}^3\). The additional excess comes about because we have a strip that is \(0.2\mbox{cm} \times 1.5\mbox{m}\) left over, which has a volume of \(9 \mbox{cm}^3\).

Puzzle 7

This problem is most easily solved by representing the problem as a directed graph. We connect each node (city) to other nodes by a directed edge if there is a discounted route available. The information presented in the table below is then represented by the graph below

It is now easy to see that every tour must start with the same loop from Rio to Beunos Aires, Santiago and then back to Rio. After this loop, there are some choices. Once a tour arrives in Lima there are three other possible loops that leave and return to Lima and one final flight from Lima. This leads to \(3! = 6\) possible tours for every possible combination of routes from Rio to Lima and a given departing flight from Lima.

In fact, there are six different ways to reach (and finally leave) Lima from Rio:

Route from Rio to Lima Exit flight from Lima
Rio → Bogatá → Rio → Lima Lima → Rio
Rio → Lima Lima → Rio
Rio → Lima Lima → Bogatá → Rio
Rio → Bogatá → Lima Lima → Rio
Rio → Bogatá → Lima Lima → Bogatá → Rio
Rio → Lima Lima → Rio → Bogatá → Rio.

Thus the total number of tours that cover all possible routes is \(6 \times 6 = 36\).

In fact this result can also be calculated by using a theorem in graph theory known as the BEST theorem. Application of this theorem requires more technical mathematics that the average A-level student is likely to know, but it is a very powerful result because it reveals that calculating the number of tours for similar problems of any size can be achieved in polynomial time. In other words it is feasible to solve such problems on a computer.

Puzzle 8

It is extremely difficult to work with infinity, so let's instead determine the probability that no e-mails are forwarded forever and then subtract that from one to find the desired probability.

Let us define \(e_n\) to be the probability that no e-mails are forwarded \(n\) times. Then $$ e_n=P(\mbox{e-mail not forwarded})+P(\mbox{email forwarded to 1 person}) \cdot e_{n-1} + P(\mbox{email forwarded to 2 people})\cdot e_{n-1}^2 + P(\mbox{email forwarded to 3 people})\cdot e_{n-1}^3.$$ The above expression follow from independence of the forwarding and simply states that once the email arrives at the next recipient it must not be forwarded \(n-1\) times. For multiple recipients, the independent probabilities of each recipient's email not being forwarded \(n-1\) times are then combined.

The required probabilities for the initial number of forwarded emails follows a binomial distribution $$ P(\mbox{e-mail not forwarded}) = \left(\frac{1}{2}\right)^{3} = \frac{1}{8},$$ $$ P(\mbox{email forwarded to 1 person}) = \frac{3}{8},$$ $$ P(\mbox{email forwarded to 2 people}) = \frac{3}{8},$$ $$ P(\mbox{email forwarded to 3 people}) = \frac{1}{8}.$$ Hence, $$e_n=\frac{1}{8}\left(1 + 3\cdot e_{n-1} + 3\cdot e_{n-1}^2 + e_{n-1}^3\right) = \frac{1}{8} \left(1 + e_{n-1}\right)^{3}.$$

We are interested in the limit \(e = \lim_{n\to\infty} e_{n}\), in which case: $$ e = \frac{1}{8}\left(1 + e\right)^{3},$$ which has three possible roots \(1, \sqrt{5}-2, -\sqrt{5}-2\). We note that \(e\) cannot be negative. The question is which of the other two roots is the correct limit of the sequence. Starting from \(e_{1} = \frac{1}{8}\) and iterating using a computer or graphically, we see that the sequence converges towards the smaller of the positive solutions, which is \(\sqrt{5}-2\). Hence, the probability that the system keeps forwarding the email among these three staff members indefinitely is equal to \(1-e=3-\sqrt{5}\approx 0.764\) to three decimal places.

Note that having four members of the office is the smallest number of people for which the solution is non-trivial. If the office has two or three members the probability that the e-mail is forwarded indefinitely is zero. If you increase the number of people in the office then the probability that the e-mail is forwarded indefinitely increases approaching the limit of 1.

MathsBombe 2017 is organised by the The School of Mathematics at the University of Manchester.
Contact us via mathsbombe@manchester.ac.uk with any queries.