From the people behind the Alan Turing Cryptography Competition.
Applications now open for Making Maths at Manchester 2017, a two-day event for year 12 maths students.
You are reading the website of the 2017 edition of the MathsBombe, which ended on Saturday 29th April at 11:59 pm

# Solutions.

## Puzzle 1

The answer can be calculated by using restricted versions of Pascal's triangle. Suppose the M is placed on the left-most black square. Then there are 1+1 = 2 possible positions for the A, 2+1 = 3 possible positions for the A and T, etc. Note that the construction of these numbers follows the same rules as for constructing Pascal's triangle, subject to only using a 10x10 grid. For the total number of ways of arranging the tiles to spell MATHSBOMBE with the first M on the left-most black square is then the sum of the numbers appearing in the bottom row of the following table:

1
1 1
2 1
2 3 1
5 4 1
5 9 5 1
14 14
6
1
14 28 20 7 1
42 48 27 8 1
42 90 75 35 9
For the M starting on the 2nd black square we have
1
1 1
1 2 1
1 3 3 1
4 6 4 1
4 10 10 5 1
14 20 15 6 1
14 34 35 21 7
48 69 56 28 7
48 117 125 84 35
For the M starting on the 3rd black square:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5
6 15 20 15 5
6 21 35 35 20
27 56 70 55 20
27 83 126 125 75
For the M starting on the 4th black square:
1
1 1
1 2 1
1 3 3
1 4 6 3
1 5 10 9
1 6 15 19 9
1 7 21 34 28
8 28 55 62 28
8 36 83 117 90
And finally for the M starting in the rightmost corner:
1
1
1 1
1 2
1 3 2
1 4 5
1 5 9 5
1 6 14 14
1 7 20 28 14
1 8 27 48 42

The total number of ways of arranging the tiles to spell MATHSBOMBE is the sum of the numbers appearing in the bottom row of the above five tables, i.e.

(42+90+75+35+9) +
(48+117+125+84+35) +
(27 + 83 + 126 + 125 + 75) +
(8 + 36 + 83 + 117 + 90) +
(1+ 8 + 27 + 48+ 42) = 1556.

## Puzzle 2

First we must find out how many coins there are. Reading carefully through the text the number of coins x must satisfy the two equations

x mod 39 = -4,
x mod 37 = 1.

These two equations can be solved using the Chinese remainder theorem or a lot of trial and error to obtain

x = 815 mod 1443.

We know that there must be fewer than 10,000 coins and so the possible solutions are

815,
2258,
3701,
5144,
6587,
8030,
9473,
with corresponding prime factorisations
5, 163,
2, 1129,
3701,
2, 2, 2, 643,
7, 941,
2, 5, 11, 73,
9473.

The only number for which there is a factor, or product of factors, between 20 and 40 is 2*11 = 22. Hence there were 8030 coins in total, and the 22 goblins remaining each received 365 coins.

## Puzzle 3

At first sight, it appears that there is not enough information to answer this problem, but the point is that it doesn't matter what the value of the 60 coins is. Thus, the worst case is actually that we get a different coin for each turn of the handle until we get up to 59 coins for every denomination. The next turn of the crank must then guarantee 60 coins of identical value.

There are eight possible denominations: 1p, 2p, 5p, 10p, 20p, 50p, £1 and £2, which means that the number of turns required is

8 x 59 + 1 = 473.

## Puzzle 4

First imagine you have a small circle of radius $$r$$ rotating (without slipping or sliding) along a straight line of length $$l$$. Then the centre of the circle also moves a length $$l$$, which means that perimeter traced out by rotations of the circle is also $$l$$ and the total number of times that the small circle will rotate is $$\frac{l}{2\pi} r$$.

The thing that makes this puzzle difficult is that when the circle moves along a line that is not straight the centre of the circle must travel further than the length of the line along which it is rolling, which means that you get more rotations than you would expect.

Let's work out the distance moved by the centre of the circle as it rolls around the MATHSBOMBE discs, which we shall choose to have radius 2, so that the smaller disk has radius 1. Draw a decagon with vertices at the centres of the MATHSBOMBE discs. Then the total length of the outside of the MATHSBOMBE chain is given by the sum of the external angles of the decagon. The sum of the external angles of an n-sided polygon is $$(n+2)\pi$$. Hence the total length of the outside of the MATHSBOMBE chain is $$24\pi$$. However, the distance moved by the centre of smaller circle is different because

• it is further away from the centre of rotation,
• it cannot reach all parts of the outside of the MATHSBOMBE chain

We can work out the angle moved by the centre of the smaller circle when it moves round one of the MATHSBOMBE discs (assuming the MATHSBOMBE discs form a regular n-gon) by using the the diagram below.

The angle $$\alpha$$ is given by $$\cos^{-1} 2/3$$ by using the right-angled triangle formed by constructing a perpendicular to the line joining the centres of the two MATHSBOMBE discs. Hence the angle

$$\theta = 2\pi - 2 \alpha - 8\pi/10 = 12\pi/10 - 2\cos^{-1} 2/3.$$

The small circle must move through this angle ten times and, this is the amazing part, the total angle moved by the centre of the circle does not depend on the details of how the MATHSBOMBE disks are arranged. This is because the sum of exterior angles of any decagon must always sum to $$12\pi$$ and the local geometry when the smaller disk reaches its closest approach to two neighbouring circles is the same for any configuration. Thus the distance moved by the centre of the circle is

$$D = 10 \times 3 \times \left(12 \pi/10 - 2\cos^{-1} 2/3 \right)= 36\pi - 60 \cos^{-1} 2/3.$$

Now the smaller circle has radius 1 so the number of rotations it makes is $$D/2\pi$$, which yields $$18 - (30/\pi) \cos^{-1} 2/3 \approx 9.97.$$

to two decimal places.

## Puzzle 5

This question generated an awful lot of comments by students convinced that the answer had to be 1/3 and/or that the question had been badly worded because it didn't use the magic phrase "given that". The whole point of this question is that you have indeed been given additional information by being told that the hatchling picked for cleaning is a ma. This information should be taken into account. For example, consider the extreme case when no ma hatched during the day. If a ma hatchling is chosen to be cleaned the next morning then the probability that the egg that hatched overnight contained a ma has to be 1.

Firstly, we must work out the number of hatchlings born during the day. Let x by the number of ma, y be the number of na and z be the number of muna. Then we have three simultaneous equations

x + y + z = 100,
x = y + 20,
4z = x + y,

which have the solution x = 50 ma, y = 30 na, z = 20 muna.

Now we need to do some conditional probability:

$$P(\mbox{ma born } | \mbox{ ma selected}) = \frac{P(\mbox{ma born and ma selected})} {P(\mbox{ma selected})}.$$

The probability that we select a ma is given by

ma born and ma selected = 51/101 x 1/3 = 51/303,
na born and ma selected = 50/101 x 1/3 = 50/303,
muna born and ma selected = 50/101 x 1/3 = 50/303.

Thus the total probability that a ma is selected is 151/303.

Then using the conditional probability formula above we obtain the required answer

P(ma born | ma selected) = (51/303) / (151/303) = 51/151.

## Puzzle 6

These solutions can be worked out by systematic trial and error or by writing a small computer program. There are four possible solutions:
DUUDUDDUUDD
DUUDUDDUUDU
UDDUDUUDDUD
UDDUDUUDDUU
so the one that we want is the last one.

## Puzzle 7

First note the rules:

1. The route has to go through all four towns in order: Pythagaby, Gaussington, Wileshaven and Ollerenshaw.
2. The route can only go horizontally and vertically; no diagonals.
3. The route cannot double back on itself (in particular, it cannot pass through 4 small squares that make up a large 2x2 square).
4. The route must be one continuous line.
5. The route cannot pass through mountains.
6. The route cannot contain 4 or more squares in a row, either horizontally or vertically.
7. There must be exactly 6 squares between Pythagaby and Gaussington, exactly 15 squares between Gaussington and Wileshaven, and exactly 5 squares between Welshed and Ollerenshaw (not including the towns themselves).
8. Each square that the railway passes through can only be adjacent (horizontal and vertical) to at most two other squares containing the railway.

This problem can be solved by writing a computer program to compute all possible paths that satisfy the constraints, or by considering the case by case analysis below:

First consider the stretch from Pythagaby to Gaussington.

Suppose first the route leaves Pythagaby through B1. If the route continues through C1 then it must then go via C2 (rule 6), it which case it would then reach Gaussington in 4 squares or violate rule 3 (by going B2). Hence the route must go through B2. A similar argument then shows that any route that then goes via C2 or via B3 then C3 and doesn't violate rule 3 must have length 4; the route can't go via B3 then B4 as this violates rule 6. Hence the route leaves Pythagaby via A2.

Following A2, the route cannot go via A4 (rule 6), nor is there a valid route that goes via C2. Hence the route must go through B3 and there are exactly 2 ways of doing this (A2 -> A3 -> B3, A2 -> B2 -> B3). There are now 3 squares left to get to Pythagaby; these must be B4 -> C4 -> D4.

Note that the route cannot go through C3, B5, C5 (rule 3) or E4, D1 (rule 6). These also rule out A4, A5, B1, C1, C2

In summary: there are two routes from Pythagaby to Gaussington and both go via D4.

Note next that any route of length 6 from Wileshaven to Ollerenshaw must, at each stage, go either down or to the right. This means that the route from Wileshaven must leave via either H5 or H7. The route from Gaussington to Wileshaven must enter Wileshaven via G7, G5 or H6. We shall treat each case separately.

Case 1: The route enter Wileshaven through G7 and leaves via H6.

If the route enters Wileshaven via G7 then it must have come from Gaussington via the mountain pass E5, E6. So as to not violate Rule 3 or Rule 6, the route cannot go through E4 or G5, so must go through F4 and F5.

There are two possible ways the route can leave Gaussington on the way to Wileshaven: through either D2 or E3. We can rule out D2 as follows: The shortest route from D2 to F4 that doesn't violate Rule 3 or Rule 6 is D2 E2 E1 F1 G1 G2 G3 F3. It is then impossible to get from E6 to Wileshaven in the required 15 squares.

Hence the route must leave Gaussington via E3. The next square is either E2 or F3. If it's E2, then the shortest valid route to F4 is F2 G2 G3 G4. The route from E2 to E6 is then 10 squares long, and the only way to get to Wileshaven within 15 squares is to go horizontally from E5 to E8, violating Rule 6. Hence the route must leave Gaussington via E3 and F3.

Can the route enter Wileshaven via H7 and G7? The answer is no: the shortest such route that doesn't violate Rule 3 or Rule 6 is D6 D7 D8 E8 F8 F9 G9 H9 H8 H7 and this has length 17. Hence the route must enter Wileshaven via G8. So as to not violate Rule 6, it must then have come from F8.

This fixes 9 of the 15 squares on a valid route from Gaussington to Wileshaven. It's now straightforward to check that there is only one valid route: E6 E7 D7 D8 D9 E9 F9 F8 G8 G7.

Note that, by Rule 3, the route cannot go via H7 or H8.

In order to work out the number of routes from Wileshaven to Ollerenshaw, we need to work out the number of valid routes from I6 to J9 that go through 4 squares (there are no valid routes via H5. We can’t go via J5 or I9 (Rule 6). Hence there are just two valid routes from Wileshaven to Ollerenshaw in this case: H6 I6 I7 then either J7 or I8, then J8.

Hence there are two valid routes from Gaussington to Ollerenshaw that enter Wileshaven through G7.

Hence there are four valid routes form Pythagaton to Ollerenshaw that enter Wileshaven through G7.

Case 2: The route enter Wileshaven through G5.

In this case, the route cannot go via the mountain pass E5 E6.

We argue that the route must go via the mountain pass at J3. If not, then any route that takes more than 5 squares from Gaussington to Wileshaven must go via G3. The route from G3 to Wileshaven must go via either F3 or H3 and then get to Wileshaven in another 2 squares. There are not enough squares left for a route of 15 squares from Gaussington to Wileshaven that satisfy the rules.

So the route must go via J3 (and hence also through J2 and J4). By Rule 6 this means the route cannot go via J1 or J5 and so must also go through I2 and I4.

The route cannot go from I4 to Wileshaven via G3. We can't have G3 G4 (as then G3 G4 G5 G6 violates Rule 6), so such a route must go via F3 G3 H3. There is then no valid route from Gaussington to I6 via columns 1 and 2. So as to not violate Rule 3, we would have to use more than 4 squares in a row from column 1, violating rule 6.

Hence the route from I4 to Wileshaven is either I4 H4 H5 G5 or I4 I5 H5 G5. (I4 H4 G4 violates Rule 6; I4 I5 I6 violates Rule 3 if we are to enter Wileshaven via G5.)

Thus there are only 2 valid routes from I2 to G5 and both use up 8 squares. Note also that as the route goes through H5, it cannot also go via H6 without violating Rule 3.

It remains in this case to find the number valid routes from Gaussington (leaving via D2 or E3) to I2 that use exactly 7 squares. The simplest way to do this is to exhaustively write down all the possibilities and check them against Rules 3 and 6. There are 7 such routes:

1: D2 E2 F2 F1 G1 H1 H2
2: D2 E2 F2 F3 G3 H3 H2
3: E3 E2 F2 F1 G1 H1 H2
4: E3 E2 F2 G2 G1 H1 I1
5: E3 F3 F2 G2 G1 H1 I1
6: E3 F3 F2 F1 G1 H1 H2
7: E3 F3 F4 G4 H4 H3 H2

However, as the route from J3 to Wileshaven must go via I4, the 7th of these is not valid. Note also that route 2 passes through H3, which means that the route I4 H4 H5 G5 would violate rule 8.

Hence, in this case, there are 5 valid routes from Gaussington to H3 with 2 valid routes from J3 to Wileshaven and one additional valid route from Gaussington to Wileshave. Hence there are 5x2 + 1 = 11 valid routes from Gaussington to Wileshaven that enter Wileshaven via G5.

It remains to calculate the number of valid routes from Wileshaven to Ollerenshaw in this case. As the route passes through H5, we cannot leave Wileshaven via H6. So we must leave via G7.

To avoid violating Rule 6, we must then go via H7. By Pascal's triangle, there are 6 routes of length 4 from H7 to J9; however, one of these (H7 I7 J7) violates Rule 6. So there are 5 routes altogether.

Hence there are 11 x 5 = 55 valid routes from Gaussington to Ollerenshaw that enter Wileshaven via G5.

Hence there are 2 x 55 = 110 valid routes from Pythagaton to Ollerenshaw that enter Wileshaven via G5.

Case 3: The route enters Wileshaven via H6.

We first claim that the route must go via the mountain pass at J3. We can do this using the greedy algorithm: let's construct the longest valid route from H6 back to Gaussington. Note that the route cannot go via the mountain pass at E5 E6. Also the route cannot go via F5 or G5. The longest possible valid route from H6 back to Gaussington is then H6 I6 I5 I4 H4 H3 H2 G2 G1 F1 E1 E2 D1/E3, which does not have length 15.

Hence the route must go via J3. As in Case 2, it must therefore also go via J2 and J4 and cannot go via J1 or J5. Hence it must go through I2 and I4.

The only valid routes from I4 to H6 have length 2 and there are precisely 3 of them:

1: I4 H4 H5 H6
2: I4 I5 H5 H6
3: I4 I5 I6 H6

All these routes use exactly 8 squares from I2 to H6, it remains to calculate the number of valid routes of length 7 from Gaussington (leaving via D2 or E3) to I2 that use exactly 7 squares. We did this in Case 2 above and found 7 of them. Again, only 6 of these are valid, with the catch that route 1 from I4 to H6 cannot be used with route 2 from Gaussington to I2.

Hence there are 3 x 5 + 2 = 17 valid routes from Gaussington to Wileshaven that enter Wileshaven via H6.

In this case we must leave Wileshaven via G7. This, and Rule 6, then forces us to take G8 H8. We can't go via J8 without violating Rule 6. So there are exactly 2 valid routes from H8 to Ollerenshaw.

Hence there are 2 x 17 = 34 valid routes from Gaussington to Ollerenshaw that enter Wileshaven via H6.

Hence there are 2 x 34 = 68 valid routes from Pythagaton to Ollerenshaw that enter Wileshaven via H6.

Hence there are a total of 4+110+68 =

182

valid routes from Pythagaton to Ollerenshaw.

## Puzzle 8

This problem requires some careful consideration of how to compute the probabilities and knowledge of how to evaluate infinite sums.

Let's consider a slightly more general case, in which $$p$$ is the probability of success over wifi, and $$q$$ is the probability of success over bluetooth.

We now calculate the probability that the signal arrives in n seconds for all integer values of n

$$P(\mbox{arrives in 1 second}) = wp,$$ $$P(\mbox{arrives in 2 seconds}) \equiv K =$$ $$w (1-p) p \quad \mbox{[wifi both times, first fails, second arrives]}$$ $$\quad\quad\quad\quad + (1-w)wp(1-q) \quad \mbox{[bluetooth first time fails and successful wifi second]}$$ $$+ (1-w)q \quad \mbox{[successful bluetooth first]}.$$

A little algebra reveals that the quantity K defined above is $$K = w w(1-p) p + (1-w) w p(1-q) + (1-w)q = (1 - pw)(q(1-w) + pw)$$

Now we can calculate the general case
P(arrives in n seconds) = P(doesn't arrive in n-2 seconds)*P(arrives in 2 seconds)
$$= L^{n-2} K,$$ where $$L = [w(1-p) + (1-w)(1-q)]$$ is probability that signal does not arrive.

Note that $$K = (1-pw)(1-L)$$.

Before we carry on, let's perform a quick sanity check. The sum of the probabilities for all possible arrival times is

$$S = wp + \sum_{n=0}^{\infty} L^n K$$

Now this is a standard infinite sum for a geometric progression so

$$S = wp + K/(1-L) = wp + (1-pw)(1-L)/(1-L) = wp + 1 - pw = 1,$$ as expected.

Now, the expected arrival time is the sum of all probabilities weighted by the corresponding arrival time

$$E = wp + \sum_{n=2}^{\infty} n L^{n-2} K.$$ $$\Rightarrow\quad E = wp + L^{-1} K \sum_{n=2}^{\infty} n L^{n-1}$$

and the sum is an arithmetico-geometric sequence, which has the value

$$\sum_{n=1}^{\infty} n L^{n-1} = 1/(1-L)^2.$$ $$\Rightarrow\quad \sum_{n=2}^{\infty} n L^{n-1} = 1/(1-L)^2 - 1.$$

Hence,

$$E = wp + L^{-1} K [1/(1-L)^2 - 1],$$

which can be simplified to

$$E = \frac{1 + q(1-w)}{pw + q(1-w)}$$

Now we simply use our given values of $$p$$ and $$q$$

$$E = \frac{1.5 + 0.5w}{0.5 + (0.05-0.5)w} = \frac{3 - w}{1 + (0.1-1)w}.$$

The above expression gives the expected arrival time as a function of the probability $$w$$. Note that this function increases monotonically with $$w$$. We wish to find the largest value of $$w$$ that ensures that $$E \leq 5$$. The required value occurs when $$E = 5$$ in which case $$5 = \frac{3 - w}{1 - 0.9w} \Rightarrow w = 4/7 = 0.571 \mbox{(to 3 d.p.)}$$

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