For this puzzle we need simply count up all the possibilities, but we can be slightly smart about how we do the counting.

Firstly, look at all words that start with an 'A'; there are 9! of these in total, but only 9!/(2!2!) different words, due to there being two 'B's and two 'M's.

Now look at all words that start with a 'B'. This time, there is only one repeated letter (the 'M'), so there are 9!/2! different words.

With the same reasoning as above, there are 9!/(2!2!) words that start with an 'E' or an 'H'. So after,

9!/2!2! + 9!/2! + 9!/2!2! + 9!/2!2!

words we are finally at words that start with an 'M'.

If the words are listed in alphabetical order, then the next letter must be an 'A'. Now look at all words that start 'MAB'; there are 7! such words. Then in each case there are 7!/2! words that start MAE, MAH, MAM, MAO, MAS. So after

9!/2!2! + 9!/2! + 9!/2!2! + 9!/2!2! + 7! + 5 * 7!/2!

words we are finally at words that start with 'MAT'.

There are then 6! words that start 'MATB' followed by 6!/2! words that start 'MATE'. Thus after

9!/2!2! + 9!/2! + 9!/2!2! + 9!/2!2! + 7! + 5 * 7!/2! + 6! + 6!/2!

words we are finally at words that start with `MATH'.

There are then 5! words that start 'MATHB' followed by 5!/2! words that start with each of 'MATHE', 'MATHM' and 'MATHO'. So after

9!/2!2! + 9!/2! + 9!/2!2! + 9!/2!2! + 7! + 5 * 7!/2! + 6! + 6!/2! + 5! + 3 * 5!/2!

words we are finally at words that start with 'MATHS'.

The next set of words in alphabetical order must start 'MATHSB'. There are then 3! words that start with each of 'MATHSBB', 'MATHSBE' and 'MATHSBM'. So after

9!/2!2! + 9!/2! + 9!/2!2! + 9!/2!2! + 7! + 5 * 7!/2! + 6! + 6!/2! + 5! + 3 * 5!/2! + 3 * 3!

words we are finally at words that start with 'MATHSBO'.

There are then 2! words that start with 'MATHSBOB' and another 2! words that start with 'MATHSBOE' before we finally get to 'MATHBOM'. The next word in alphabetical order is 'MATHSBOMBE', so this appears in place 9!/2!2! + 9!/2! + 9!/2!2! + 9!/2!2! + 7! + 5 * 7!/2! + 6! + 6!/2! + 5! + 3 * 5!/2! + 3 * 3! + 2! + 2! + 1 = 472643.

Alternatively, if you like coding there is a beautiful algorithm to find the next permutation of a sequence in lexicographic (alphabetical) order, see the Wikipedia Page.

Call the 4 cities A,B,C,D. First note that A,B,C,D lie on the four corners of a rectangle (this follows from Pythagoras' Theorem).

Next note that the motorway network must be formed by a union of straight lines. By symmetry, the network must be horizontally and vertically symmetric. Divide the rectangle up into 4 equal subrectangles, as illustrated.

The network must go through the vertical dashed line at least once. Suppose the network went from the point A to the point P. Then by symmetry the network would also go from D to P'. As the network must contain a path from the top two rectangles to the bottom two rectangles, then it must contain a path from P to P'. However, one could get a shorter network by going from A to Q and from D to Q (here Q is the centre of the rectangle). Hence the network must pass through the centre of the rectangle.

Hence the network must take the following form in each rectangle.

and so takes the form

We want to find the value of t that minimises the length l(t) of this network. First note that by Pythagoras' Theorem

l(t) = 4 (t² + (106.5)²)^1/2 + 285 - 2t.

Differentiating this with respect to t to find the minimum shows that the minimum is achieved when t = 106.5/3^1/2. Substituting this back into the formula for l(t) shows that the network with shortlest length has length 652.927 miles. Thus the motorway network costs

652.927 * 30 = 19588 million pounds (rounded to the nearest million).

This is a particular example of a very general problem in mathematics called the Steiner tree problem. Click here to read more about Steiner graphs. There is a lot of theoretical work in computer science on Steiner trees; also, soap films are surprisingly good at finding Steiner trees (see here for example).

First draw up a grid as illustrated below.

Now go through the clues, inserting crosses to indicate where there is no match (for example, clue 3 tells you to put a cross in the box corresponding to 600 pages and 5 books) and inserting ticks where there is a match. Note that 'or' is the exclusive or (for example: clue 3 also tells you that Fabled Lands is not a 3-book series).

Once you have filled out the grid with the information in the clues, you can then infer other relations allowing you to complete more of the grid. A detailed explanation of how to solve such puzzles is given here.

J.P. Pratman	The Vampire Saga	200 pages	2 books
Lewis Scorcher	Games of Bones	300 pages	3 books
Noel Garman	The Dark Instruments	600 pages	4 books
Claire Cassandric	Circleworld	400 pages	5 books
Stephanie Mower	Fabled Realms	500 pages	6 books

In total there are

2*200+3*300+4*600+5*400+6*500=8700 pages.

An alternative method is via Prolog, a programming language that is well suited to solving logic problems.

Let's introduce a Cartesian coordinate system with origin at the centre of the cube and such that the faces of the cube are aligned with coordinate planes x,y,z = ± 1, so that the cube sides are all of length 2. The shortest distance of the centre of the bubble to any face is the distance to that face in the direction of its normal. We let the bubble centre be at the position (x,y,z) and then the distances to the faces are 1-x, 1+x, 1-y, 1+y, 1-z and 1+z.

The required probabilities are given by a constant of proportionality, α, multiplied by each distance. Summing all probabilities must give one, which means that α = 1/6. Thus, we have the probabilities associated with each face being (1-x)/6, (1+x)/6, (1-y)/6, (1+y)/6, (1-z)/6 and (1+z)/6. Note that we recover a fair die when x=y=z=0. Given the labelling of faces on a standard die we can, in fact, only adjust the relative probabilities between the pairs 1 and 6; 2 and 5; and 3 and 4. You can also use this observation as a starting point to work out the required probabilities because the probabilities of throwing 1 or 6; 2 or 5; and 3 or 4 each remain fixed at 1/3.

The volume of the our chosen cube is 8, which means that the volume of the of the sphere is (8 x 25 π/12)/100. Hence, the volume of bubble is π/6 = 4/3π r³, which means that r³ = 1/8, and so the radius of the bubble is r = 1/2. The expected value of a single roll is minimised when bias towards 1, 2 and 3 (as opposed to 6, 5 and 4) is maximised. Based on the given radius of the sphere, the largest possible values of x, y and z are 1/2. Thus we have the maximum possible probabilities of rolling 1, 2 and 3 each being 1/4 and the probabilities of rolling 4,5 and 6 each being 1/12.

The expectation of the sum of two such dice follows from computing the probabilities of each possible sum

Sum, Xi	Probability, Pi
2	9/144
3	18/144
4	27/144
5	24/144
6	21/144
7	18/144
8	13/144
9	8/144
10	3/144
11	2/144
12	1/144

The expected value is E = Σ_i X_i P_i, which gives E = 5.5.

As a side note, the most likely outcome is 4; unlike the situatino for fair dice this is not the same as the expected value.

This puzzle is a type of problem sometimes called an alphametic or cryptalgorithm. This puzzle is a variation on puzzles in which the entire sum is written using letters because these standard puzzles can easily be solved using online tools. Straightforward logic can be used to solve the problem; indeed the programming language Prolog mentioned above can also be used to solve such puzzles effectively.

Firstly, we note that we can rearrange the sum to write BOMBE - MATHS = .....

We need each letter to represent a different digit between 1 and 8 and each dot must also lie between 1 and 8.

In order for the word MATHSBOMBE to have the highest possible numerical value, we need M to be as large as possible. We cannot have a negative number in the place of a dot, so we must choose M=7 and B=8.

Ideally, we now want A to be 6, but if we do so then because the value of O must be less than 6, the first unknown dot would be 0, which is not allowed. Hence, we must choose A = 5 and O = 6.

For the next term, we already have that M = 7, so we are free to choose T = 4 which gives our sum as 8678E - 754HS and then by similar logic we pick H = 3, E = 2 and S = 1 giving

MATHSBOMBE = 7543186782

This puzzle is about multiplication mod 10. Modular arithmetic mod n involves performing normal arithmetic operations but then only looking at the remainder after by division by n. You can read more about modular arithmetic here. Modular arithmetic is also used in Puzzle 8.

To perform modular arithmetic mod 10 you perform normal arithmetic and just keep track of the rightmost digit. For example, 3*4 = 12 = 2 mod 10. The graphs in the puzzle describe how multiplication by each number 0,1,...,9 works when working mod 10. The first (top left) graph describes how multiplication mod 10 by A works, the second (top right) graph describes how multiplication mod 10 by B works, etc.

Multiplication by H leaves every digit alone; hence H must be 1. Multiplication by T maps every digit to T; hence T must be 0. The easiest way to determine the values of the other letters is to work out how multiplication by each digit works and then compare these to the graphs in the puzzle. (For example, the graph for multiplication by 3 is given below.)

There are two possible solutions: either

• M=6, A=5, T=0, H=1, S=8, B=3, O=7, E=2, X=4, Q=9,
• M=6, A=5, T=0, H=1, S=2, B=3, O=3, E=8, X=4, Q=9.

These give two possibilities for MATHSBOMBE: 6501837632 or 6501273678. Of these, the highest is 6501837632.

First note that we have to end on the centre E square. Consider the top right quarter of the diamond:

M
A	M
T	A	M
H	T	A	M
S	H	T	A	M
B	S	H	T	A	M
O	B	S	H	T	A	M
M	O	B	S	H	T	A	M
B	M	O	B	S	H	T	A	M
E	B	M	O	B	S	H	T	A	M

Start at the 'E' in the bottom left hand corner. Look at the 'B's on the diagonal immediately next to the 'E'. For each one of these 'B's there is exactly one route to the 'E'. Now look at the 'M's on the next diagonal. There is exactly one route to the 'E' for both of the 'M's on edge, but 2 routes for the 'M' in the middle (one via each 'B').

In general, we'll write P(n,m) for the number of different ways from the letter in the nth column and mth row (counting from the bottom left hand corner) to the 'E' in the bottom left hand corner. To get to the 'E' in the bottom corner we must first move either one square left or one square down. This tells us that P(n,m) = P(n-1,m) + P(n,m-1) (with the convention that P(-1,m)=0 and P(n,-1)=0). If you calculate and draw in a table of values of P(n,m) you'll see that they form Pascal's triangle:

1
1	9
1	8	36
1	7	28	84
1	6	21	56	126
1	5	15	35	70	126
1	4	10	20	35	56	84
1	3	6	10	15	21	28	36
1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1

Thus the total number of ways to spell out 'MATHSBOMBE' in the top right triangle of the diamond is the sum of the numbers 1, 9, 36, 84, 126,... on the longest diagonal side. One can just type these into a calculator to work this sum out, but one can be a bit smarter: the sum of the numbers on the kth line of Pascal's triangle is 2^k. So the total number of ways to spell out 'MATHSBOMBE' in this triangle is 2^9 = 512.

But this only counts the number of ways of spelling out 'MATHSBOMBE' in the top right triangle; there are four triangles altogether. In total, there are 4*2^9 – 4 = 2044 ways of spelling out 'MATHSBOMBE'. (We had to subtract 4 as we counted the strings that go straight along the horizontal and vertical lines to the central 'E' twice each.)

As hinted in the wording, this is a code enciphered using the RSA algorithm. The algorithm is described here and relies on properties of modular arithmetic, see solution to Puzzle 6; in particular modular exponentiation.

The process of encryption is to take the message, converted into an integer (call this m), and compute M = m^e mod n. The encoded message is then M. In this case n = 3127, which was termed the key length. The public key is e = 17, and so M = m¹⁷ mod 3127.

In order to decrypt, we need to find an integer, d, such that M^d mod n = m. This can always be done by a completely brute force computation. Alternatively, the RSA algorithm requires that n = pq where p and q are two different primes. Using the square root of n as a starting point, it's relatively quick to determine that 3127 = 53 x 59. The difficulty of this prime factorisation is what makes RSA secure for sufficiently large values of n.

Now we know p = 53 and q = 59, we can work out the Euler totient function φ(3127) = (p-1)(q-1) = 52 x 58 = 3016. The required value of d is the modular (multiplicative) inverse of e, mod φ(n). In other words 17 d = 1 mod 3016, which means that 17 d - 3016 a = 1, where a is another unknown integer. The solution to this problem can be found using Euclid's algorithm (extended version), or a brute force approach.

Euclid's algorithm is a simple method for computing the greatest common divisor (highest common factor) of two numbers. Thus, if we want to compute the highest common factor of 17 and 3016 we proceed as follows:

3016/17 ≈ 177.412 ⇒ 3016 = 177 x 17 + 7,

17/7 ≈ 2.429 ⇒ 17 = 2 x 7 + 3,

7/3 ≈ 2.333 ⇒ 7 = 2 x 3 + 1,

which means the highest common factor of 3016 and 17 is 1. Two numbers that have a highest common factor of 1 are said to be coprime. Now reversing the steps of the algorithm we have that

1 = 7 - 2 x 3 = 7 - 2 x (17 - 2 x 7) = 5 x 7 - 2 x 17

1 = 5 x (3016 - 177 x 17) - 2 x 17 = 5x 3016 - 887 x 17 = 1

The extended version of the algorithim tidies up the calculation so that the backsubstitution is not required at the cost of keeping track of some auxilliary variables. From the final line, we deduce that d = -887 = 2129 mod 3016.

Whichever method is used, the result is that d = 2129. Then taking each number in the message turn, we compute M^d, which gives

715 1515 1504 402 225 2505 506 618 1815 1513 1320 2008 805 513 1301 120 2008 819 1902 215 1513 1302 205

The remaining challenge is to convert these numbers back into letters. The encoding here is actually very straight forward. Each number represents two letters with a standard conversion 1=A, 2=B and so on. Hence, the message reads

GO OO OD DB BY YE EF FR RO OM MT TH HE EM MA AT TH HS SB BO OM MB BE

which reveals the message GOODBYE FROM THE MATHSBOMBE. Note that the repetition of letters between chunks is a form of error correction in case any information gets corrupted.

Mathsbombe Competition 2016 is organised by the The Department of Mathematics at The University of Manchester.
© The University of Manchester 2012–2016, All Rights Reserved
Contact us | Privacy notice