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

# Solutions

Puzzle 1:

First we calculate that $$\phi^2=1+\phi$$, $$\phi^3=1+2\phi$$ and $$\phi^4=2+3\phi$$, just by iterating the equation $$\phi^2=1+\phi$$. It's no accident that the coefficients that you see in these equations are Fibonacci numbers! Then it is not so hard to work through lexicographically and list all of the arrangements that give $$4+7\phi$$. Written in the form $$(a_5,a_4,a_3,a_2,a_1)$$) they are $\begin{array}{c} (0,0,0,7,4)\\ (0,0,1,6,3)\\ (0,0,2,5,2)\\ (0,0,3,4,1)\\ (0,0,4,3,0)\\ (0,1,0,5,3)\\ (0,1,1,4,2)\\ (0,1,2,3,1)\\ (0,1,3,2,0)\\ (0,2,0,3,2)\\ (0,2,1,2,1)\\ (0,2,2,1,0)\\ (0,3,0,1,1)\\ (0,3,1,0,0)\\ (1,0,0,4,2)\\ (1,0,1,3,1)\\ (1,0,2,2,0)\\ (1,1,0,2,1)\\ (1,1,1,1,0)\\ (1,2,0,0,0)\\ (2,0,0,0,1) \end{array}$ So there are 21 in total.

Puzzle 2:

In the solutions, we’ll refer to the Goblins/Nilbogs as A,B,C, etc and replace ‘is a Nilbog’ by ‘tells the truth’ and ‘is a Goblin’ by ‘is lying’ where appropriate.

Junction 1. A: You should go left if and only if I’m a Nilbog.

If A a Nilbog then A is telling the truth and you should go left.

A’s statement is in the form of ‘P if and only if Q’. This is equivalent to ‘not P if and only if not Q’, which is ‘You should go right if and only if I’m a Goblin’. If A is a Goblin then A is telling you to go right, which must be a lie. Prince Kevin should go left.

Junction 2. A: At least one of us is a Goblin. B: Go left

If A is a Goblin then ‘at least one of us is a Goblin’ is a lie. So both A and B must be Nilbogs, which is a contradiction.

So A is a Nilbog and is telling the truth. So B must be Nilbog, and is therefore lying. Prince Kevin should go right.

Junction 3. A: Either I’m a Goblin or B is a Nilbog B: Go left

Suppose A is lying. The negation of ‘P or Q’ is ‘not P and not Q’. Hence A is telling the truth and B is lying. But this contradicts that A is lying.

Hence A is telling the truth. So one of P (I am lying) or Q (B is telling the truth) is true. P is false, so Q must be true. Hence B is telling the truth. Go left.

Junction 4. A: If I am telling the truth then so is B B: Go left

If A is telling the truth then B is also telling the truth. Go left.

Suppose A is lying. Then we have 'false imples anything' which is true. So B is telling the truth.

It’s impossible to deduce whether A is a Goblin or a Nilbog, but either way, go left.

Junction 5. A: I am lying but B isn't B: Go left

If A is telling the truth then A is confessing to lying, a contradiction. So A is lying. So it's not true that B isn't lying, i.e. B is lying. Go right.

Junction 6. A: All of us lie B: Exactly one of us tells the truth C: Go left

If A tells the truth then B's statement must also be true, but this contradicts A. So A is lying. So there exists at least one monster who tells the truth.

Suppose B is lying. Then there exist at least 2 people who tell the truth (there cannot be zero by the above) and these must be B,C (as we already know A is lying). So B must be telling the truth.

Hence C lies. Go right.

Junction 7. A: All of us lie B: Exactly one of us lies C: Go left

Solution If A tells the truth then B's statement must also be true, but this is a contradiction. So A is lying. So there exists at least one monster who tells the truth and 0,1,2 monsters who lie.

Suppose B is lying. Then there are 0 or 2 or 3 people who lie. By A, this means that there are 0 or 2 people lying. But both A and B are lying, so C must be telling the truth.

Suppose B is telling the truth. Then A is the one person who lies, so C must also be telling the truth.

So we can't determine what B is, but C must always tell the truth. Go left.

Junction 8. A: B is lying B: A and C either both tell the truth or both lie. C: Go left

Suppose A is telling the truth. Then B is lying. So A and C are different types of monster. So C is lying.

Suppose A is lying. Then B is telling the truth. So A and C are the same type of monster. So C is lying

Go right.

Junction 9. A: At least one of us lies B: That's true! C: Go left

If A lies then there are no Goblins. But this contradicts A being a Goblin. So A tells the truth. So there is at least one Goblin. B agrees that A makes a true statement, so B is telling the truth. So C is the Goblin. Go right.

Junction 10. A: B tells the truth B: If A tells the truth then so does C C: Go left

Suppose A tells the truth. Then B tells the truth. Hence C tells the truth.

Suppose A lies. Then B lies. B says ‘P implies Q’ where P = ‘A tells the truth’, Q = ‘C tells the truth’. P is false. So P implies Q is true. This contradicts B lying. So A tells the truth.

Go left.

Junction 11. A: B lies and C tells the truth B: A would say that I lie C: B, C either both tell the truth or both lie D: Go left D: both B and C agree with D to go left.

Suppose A tells the truth - then B lies and C tells the truth - B is making a true statement, so this is a contradiction - so A lies.

We know that A lies. - So either B tells the truth or C lies, or both. - If B tells the truth then A, a liar, would say that B lies. So B is telling the truth. - If C tells the truth then B and C are different, a contradiction. So C lies.

If D is telling the truth then we have a contradiction: B (who tells the truth) and C (a liar) can't both say the same thing.

So D is lying. Go right.

Junction 12. A: C and E tell the truth B: C and B are different C: B lies D: A tells the truth E: A and C are either both telling the truth or both lie, E: F tells the truth. F: Go left.

If C tells the truth: - then B lies - so C and B are the same type of monster, a contradiction So C lies - so B tells the truth.

Suppose D tells the truth - then A tells the truth - so C tells the truth, which is a contradiction

Hence D lies. - So A lies - so at least one of C and E lie. - E is telling the truth. - So F is telling the truth.

Go left

Puzzle 3:

Since $$\alpha=\frac{1+\sqrt{3}}{2}$$ we see that $2\alpha^2-2\alpha-1=0.$ Then $\alpha=1+\frac{1}{2\alpha}=1+\frac{1}{2+\frac{1}{\alpha}}=1+\frac{1}{2+\frac{1}{1+\frac{1}{2\alpha}}}=1+\frac{1}{2+\frac{1}{1+\frac{1}{2+\frac{1}{\alpha}}}}$ In particular, $\frac{r_{n+2}}{s_{n+2}}=1+\frac{1}{2+\frac{1}{\frac{r_n}{s_n}}}=1+\frac{r_n}{2r_n+s_n}=\frac{3 r_n+s_n}{2r_n+s_n}.$ We have $\frac{r_2}{s_2}=\frac{4}{3}$ and so iterating the above formula nine times gives $$r_{20}$$ and $$s_{20}$$, for example by, $\left(\begin{array}{c}r_{20}\\s_{20}\end{array}\right)=\left( \begin{array}{cc} 3 & 1\\ 2 & 1\end{array}\right)^9 \left( \begin{array}{c}4\\3\end{array}\right)$ Then $\frac{r_{20}}{s_{20}}=\frac{564719}{413403}\approx 1.36602540378438$ so $$r_{20}=564719$$.

Puzzle 4:

Each chip is identical and behaves independently, so the optimal strategy for shaking or turning over the chips depends only on $$n$$, the number of chips remaining to be turned over (turned over' means that the chip is the opposite way up from it was taken out of the oven). For each value of $$n$$ ($$0 \leq n \leq 10$$), the optimal strategy specifies whether it is best to shake the tray or turn over a single chip.

Let $$t(n)$$ be the expected time required, under the optimal strategy, to turn over the $$n$$ chips that remain to be turned over. If no chips remain to be turned over, then the expected time until we reach this state is zero, so $$t(0)=0$$. Since all ten chips initially need to be turned, the answer to the puzzle is $$t(10)$$.

Let $$p(n)$$ be the probability that $$n$$ chips remain to be turned over after the tray has been shaken. Because the probability of each chip turning over is $$1/2$$, after a shake each chip has a probability $$1/2$$ of being turned over, independent of whether it was turned over or not prior to the shake. The probability $$p(n)$$ is therefore given by a Binomial distribution, $$p(n) = {10\choose n}\frac{1}{2^{10}}.$$

Suppose $$n>0$$ chips remain to be turned over. If we turn over a single chip (that has not already been turned) and then follow the optimal strategy, then the expected time to turn over the $$n$$ chips is $$t_T(n) = 1 + t(n-1),$$ i.e. expected time to turn over $$n$$ chips is the one second required to turn over a chip, plus the expected time to turn over $$n-1$$ chips using the optimal strategy. If instead we shake the pan and then follow the optimal strategy, the expected time to turn over the $$n$$ chips is $$t_S(n) = 1 + \alpha,$$ where $$\alpha =\sum_{i=0}^{10} p(i)t(i).(*)$$

This corresponds to the one second required to shake the pan, plus the expected time remaining following the optimal strategy after the pan is shaken.

The optimal strategy when $$n$$ chips remain to be turned is to choose whichever of these actions leads to the smallest expected time, so \begin{align} t(n) &= \min\left(t_T(n), t_S(n)\right)\nonumber\\ &= \min\left(1 + t(n-1), 1 + \alpha \right)(**) \end{align} where the first argument of the $$\min$$ function is smaller than the second if the optimal strategy is to turn of a single chip, and the second argument is smaller if the optimal strategy is to shake the tray.

Suppose that, for some $$n$$, the optimal strategy for $$n$$ chips remaining is to shake the tray. Then $$t(n) = t_S(n) = 1+\alpha.$$ Using **, $$t(n+1) = \min(2+\alpha, 1+\alpha) = 1+\alpha = t_S(n).$$

So, if the optimal strategy for $$n$$ chips remaining is to shake the tray, then the optimal strategy for $$n+1$$ chips remaining is also to shake the tray. This observation implies that the optimum strategy is of the form: `If more than $$N$$ chips remain to be turned over, shake the tray, otherwise turn over a single chip'', for some $$N$$ to be found, and consequently, $$t(n) = \begin{cases} t_T(n) = n, & \mbox{for } n\leq N, \\ t_S(n)=1+\alpha, & \mbox{for } n>N.\end{cases}$$

Equation * then gives $$\alpha =\sum_{i=0}^{N-1} p(i)i + \sum_{i=N}^{10} p(i)(1+\alpha),$$ which rearranges to $$\alpha = \frac{\sum_{i=0}^{N-1} p(i)i + \sum_{i=N}^{10} p(i)}{1-\sum_{i=N}^{10} p(i)}(***)$$

In addition, evaluating ** at $$n=N+1$$ gives $$t(N+1) = 1+\alpha = \min(1+t(N), 1+\alpha) = \min(1 + N, 1+\alpha),$$ which tells us that $$\alpha \leq N$$, while evaluating ** at $$n=N$$, gives $$t(N) = N = \min(1+t(N-1), 1+\alpha) = \min(N, 1+\alpha),$$ which tells us that $$N\leq 1+\alpha$$. Thus $$N-1 \leq \alpha \leq N. (****)$$

It just remains to find a value of $$N$$ ($$0\leq N \leq 10$$), such that $$\alpha$$ as given by ***, satisfies ****. Some numerical calculation is required, which is doable by hand but easier with a calculator, spreadsheet or programming language. We find the only solution is $$N=5$$, $$\alpha=4.61755\ldots$$. The answer to the problem, rounded to 3 d.p, is then $$t(10) = 1+\alpha = 5.618$$.

Puzzle 5:

When written concisely the solution is very short, but there's a lot of thinking that goes before that. The hard bit of the problem is to work out how to write the multiple operations of the second computer as one operation, and how to partition the space of sequences in such a way as to describe what happens to the third digit. This is quite tough.

After a bit of messing around, we notice that any sequence will either start $001(01)^k1$ for some $$k\geq 0$$, or $001(01)^k00$ for some $$k\geq 0$$. In the first case this will be turned into $001(01)^k1\to 00110^{2k}\to 010000\cdots,$ and any subsequent digits can't affect what happens at the start. Thus digit 3 is 0. In the second case the sequence will be left unchanged by the second machine and so the third digit is 1. We are in case 1 with probability $\frac{1}{2}\sum_{k=0}^{\infty} \left(\frac{1}{2}\right)^{2k}=\frac{1}{2}\dfrac{1}{1-\frac{1}{4}}=\frac{2}{3}.$ and case 2 with probability $\frac{1}{4}\sum_{k=0}^{\infty} \left(\frac{1}{4}\right)^k=\frac{1}{4}\frac{1}{1-\frac{1}{4}}=\frac{1}{3}$ Thus the answer is $$0.333$$ to 3dp.

Puzzle 6:

The A3 sheet is 297mm by 420mm. Poker-size cards are approximately 64mm by 89mm but their exact size will not affect the answer. The diagonal of a card is less than one half of 297mm so rule 1 guarantees that each card is wholly within the sheet.

We first construct a shape S which is guaranteed to be within the region covered by all the 52 cards. Rule 2 implies that the circle C of radius 20mm in the centre of the sheet is fully covered by every one of the 51 "normal" cards, except the Queen of Spades Q♠. At most two sides of Q♠ intersect C, and Q♠ covers the concentric circle of radius 10mm. We can therefore slide Q♠ without rotation, so that the 10mm circle (shown by the dashed line in the diagram) touches two sides of Q♠:

The shape S, shaded in the above diagram, is where Q♠ overlaps with the inside of the circle C. The exact shape T covered by all the 52 cards contains S. We do not know what T is, but can estimate the perimeter of T from below using the following crucial observation:

### Observation

if a convex shape S is contained inside a shape T, then perimeter(S) ≤ perimeter(T).

### Discussion

"Convex shape S" means that for each pair of points X,Y of S, the whole segment XY lies in S. A familiar case of a convex shape is a convex polygon. It is not difficult to see why a convex polygon lying inside T has perimeter not exceeding the perimeter of T: the following diagram shows that T can be "trimmed" by straight lines containing the sides of S, and each trimming decreases the perimeter of T, which is reduced to the perimeter of S after a few trimmings.

In our case, the convex shape S is not a polygon, but convex polygons of perimeter arbitrarily close to that of S can be inscribed in S so the observation is still valid.

The above Observation shows that the perimeter or the required shape T is greater than or equal to the perimeter of S. Let us calculate the perimeter of S; we use the following diagram.

The perimeter of S is the length of ABCDEFG:

• The arc FA is one quarter of a circle centred at Z of radius 6mm (the corner of a card) so the length of the arc FA is 3π mm.
• AB = OE − ZF = 10mm − 6mm = 4mm.
• In the right-angled triangle OBC, OC = 20mm and OB = 10mm is one half of OC, so it is a 30-60-90 triangle. The angle BOC is 60° and BC = 10√3 mm.
• The angle COD is 360°−60°−90°−60° = 150° so the length of the arc COD of radius 20mm is (150/360)×2π×20mm = 50π/3 mm.
• DE = BC = 10√3 mm and EF = AB = 4mm.

The perimeter of S is therefore 3π + 4 + 10√3 + 50π/3 + 10√3 + 4 which is 8+20√3+59π/3 mm = 104.43mm (2 decimal places).

It remains to observe that, using a large number of cards and making sure that the cards except Q♠ touch the circle C, Herman can make sure that the shape T covered by all the cards is quite close to S. Instead of the arc of C, the shape will contain a section of a regular polygon circumscribed around C, as in the following diagram:

If n+1 cards plus Q♠ are used, they form part of the boundary of a regular polygon with inradius 20mm and central angle 150°/n. Hence the perimeter of the resulting shape T is 3π + 2×4 + 2×10√3 + 20n×2 tan 150°/(2n) = 52.07 + 40n tan 75°/n millimetres. For n=25 this gives 104.48mm, and this quantity decreases when n increases.

Hence whatever Herman does, the perimeter of the cut-out shape T is at least 104.43mm, and Herman can make it less than 104.48mm (2 d.p.). The least perimeter is therefore 104 to the nearest millimetre.

Puzzle 7:

In order to calculate this we need to work out some points that remain in $$E$$. It is not so hard to see that the boundary of any of the shapes $$E_n$$ is never thrown away and so remains in $$E$$. (bonus question, can you think of any points which are in $$E$$ but which do not appear as a point on the boundary of any $$E_n$$? The area that we want is the area of $$E_0$$, plus the area of $$F$$ outside of $$E_0$$, minus the area of all the things inside $$E_0$$ which are not in $$F$$. We can write this as $$T(L) + 3 L a + \pi a^2 - \sum_{n=0}^7 3^n T(2^{-n-1} L - 2 sqrt(3) a)$$

where $$T(x) := \sqrt{3} x^2 / 4$$ is the area of an equilateral triangle of side length $$x$$, $$L = 1cm,$$ $$a = 0.001cm$$.

The first term is the original triangle, the second term two terms are the additional parts outside the initial triangle, and the sum is the triangles subtracted from this. $$n=0$$ to $$7$$ is the range of recursion over which the side length of the 'subtracted' triangles $$2^{-n-1} L - 2 \sqrt{3} a$$ is positive.

Our original (wrong) solution was not as simple as this, rather than subtracting anything we partitioned the area into the area outside of $$E_0$$, the area of all completely filled triangles inside $$E_0$$ and the area of all partially filled triangles inside $$E_0$$.

Unfortunately our calculation for the completely filled triangles was off by a factor of $$4/3$$. This is because when calculating whether a triangle was completely filled we used only that the boundary of $$E_0$$ was contained in $$E$$, and did not use the stronger fact that the boundary of $$E_1$$ is in $$E$$.

Puzzle 8:

As $$F_n = F_{n−1} + F_{n−2}$$ we know that $$Fn/Fn−1 → \phi$$, the golden mean, as $$n → ∞$$. (Here, $$\phi=\frac{1+\sqrt{5}}{2}$$).

Suppose that $$F_{m−1} + F_{m−2} = F_m = 1000000$$. We expect $$F_{m−1}/F_{m−2}$$ to be approximately $$\phi$$, so we expect $$F_{m−1}$$ to be approximately $$\phi × 1000000 \approx 618034$$ and $$F_{m−2}$$ to be approximately $$381966$$. Write $$F_{m−1} = 618033 + r$$, $$F_{m−2} = 381966 − r$$ for some integer (positive or negative) r.

Iterating the recurrence relation we see that $$F_{m−3} = 236068 + 2r, F_{m−4} = 145898 − 3r, . . . .$$

Note that each F_{n} must be positive, so we get a sequence of inequalities of the form $$−618033 < r < 381966 \mbox{ from }F_{m−1}, F_{m−2} > 0$$ $$−118034 < r < 381966 \mbox{ from }F_{m−2}, F_{m−3} > 0$$ $$−118034 < r < 48633 \mbox{ from }F_{m−3}, F_{m−4} > 0$$ and so on.

Note that each pair of inequalities gives more precise information about r. If we continue this, we obtain $$F_{m−18} = 144 − 2584r, F_{m−19} = 154 + 4181r,$$ with inequalities $$−54/4181< r <144/2584.$$

As $$r$$ is an integer, this tells us that $$r = 0$$ (actually, we discover this from much earlier inequalities in this sequence). We then have that F_{m−20} = −10\), which is impossible. Hence any value of $$m \leq 20$$ satisfies the condition in the problem. The largest value is $$m = 20$$ and in this case $$F_1 = 154, F2 = 144$$.

Solution: 154, 144. (Note: 144, 154 is incorrect.)

MathsBombe Competition 2020 is organised by the The Department of Mathematics at The University of Manchester.