Social Distancing

The answer is 63.

Define the d-distance between points $ (x_1,y_1) $ and $ (x_2,y_2) $ be $ 2|x_1-x_2|+|y_1-y_2| $ . Then two people at positions $ (x_1,y_1) $ and $ (x_2,y_2) $ satisfy the social distancing regulations if $ d((x_1,y_1),(x_2,y_2)) $ is greater than or equal to 2.

Around a person at point $ (x_1,y_1) $ we draw a diamond whose boundary is all those points $ (x_2,y_2) $ for which the d-distance between $ (x_1,y_1) $ and $ (x_2,y_2) $ is exactly 1. The question then is of how many diamonds we can draw such that their centres are all inside (or on the edge of) our rectangle and that no two diamonds overlap.

The answer is 63, which we get by a periodic tiling, achieved by placing people at $ \[(0,0), (0,2), (0,4),\] \[(0.5,1),(0.5,3), (0.5,5),\] \[(1,0),(1,2), (1,4)\] \[(1.5, 1),(1.5,3),(1.5,5)\] \[.\] \[.\] \[.\] \[(10,0),(10,2),(10,4)\]

Barry and Bruce

The answer is $ (3-\sqrt(5))/2=0.382 $

Let Bruce choose an altitude with probability of success a, Barry one with probability of success b.

Bruce's chance of winning is $ a(1-b)/(a+b-ab) $ if $ b < a $ , and $ a/(a+b-ab) $ if $ b>a $ .

If Barry chooses $ b < a $ , they may as well choose $ b=a-\epsilon $ for arbitrarily small epsilon, and Bruce's chance of winning is then $ (1-a)/(2-a) $ , a decreasing function of a.

If Barry chooses $ b>a $ , they may as well choose $ b=1 $ , and Bruce's chance of winning is then a, an increasing function of a. Bruce should therefore choose a probability such that $ a = (1-a)/(2-a) $ , which gives $ a = (3-\sqrt(5))/2 $

Cut and Project Sets

The answer is 5.830 to three decimal places, to complete accuracy it would be $ \frac{3+5\sqrt{3}}{2} $ . We initially had an incorrect answer of 5.330, thanks to miscalculating $ \frac{3+5\sqrt{3}}{2} $ , we're really sorry about this.

A point $ (a,b) $ projects to point at distance $ a \cos 30 + b \sin 30=\frac{a\sqrt{3}+b}{2} $ from the origin along the line. It's height in the strip (i.e. its projection onto the perpendicular line) is $ (b \cos 30-a \sin 30)=\frac{b\sqrt{3}-a}{2} $

We think about nearest neighbours which come from pairs $ (c,d) $ and $ (e,f) $ . If $ (c-e,d-f)=(a,b) $ then the corresponding dots will be at distance $ \frac{a\sqrt{3}+b}{2} $ from each other. To make this less than 0.1 we need $ a\sqrt{3} $ to be within distance 0.2 of an integer, this first happens when $ a=3, b=5 $ , $ 3\sqrt{3}-5=0.196 $ .

The height difference in the strip is then $ \frac{3+5\sqrt{3}}{2}\approx 5.830 $ . So in order to be able to make this move $ (c,d)\to(c+3,b-5) $ we need the strip to have at least this length.

Promotions

The answer is 132, which is the 6th Catalan number (see the excellent Wikipedia article on Catalan numbers).

Looking carefully at the promotion rules, the set of paths turns into the problem of having paths on the integer lattice from (0,0) to (6,6) which always take one step right or one step up and which never cross above the diagonal. This is one way to describe the set of Catalan numbers. Let $ C_n $ be the number of paths on the integer lattice from $ (0,0) $ to $ (n,n) $ which always take one step right or one step up and never cross the diagonal.

$ C_1=1 $

To compute $ C_2 $ we split into two cases, the case of paths from $ (0,0) $ to $ (2,2) $ which visit $ (1,1) $ , and the case of paths which don't visit $ (1,1) $ . There is one type of each, so $ C_2=2 $ .

To compute $ C_3 $ , we split into the case of paths from $ (0,0) $ to $ (3,3) $ which don't pass visit $ (k,k) $ for $ k=1 $ or $ 2 $ , the set of paths which visit $ (1,1) $ and possibly $ (2,2) $ , and the set of paths which visit $ (2,2) $ but not $ (1,1) $ . These cases all have expressions in terms of lower Catalan numbers.

For example, observe that legal paths from $ (0,0) $ to $ (3,3) $ which pass through $ (1,1) $ can be split into legal paths from $ (0,0) $ to $ (1,1) $ , there are $ C_1 $ such paths, followed by legal paths from $ (1,1) $ to $ (3,3) $ , there are $ C_2 $ such paths. So in total there are $ C_1C_2 $ such paths of this type.

Continuing in this manner one can compute $ C_6 $ , which is 132.

(The astute reader will have noticed the Catalan connection from the Seat dealership in the photo illustrating the problem, Seat of course being headquartered just outside Barcelona, in Catalonia.)

Empty Seats

The answer is 2.98

Let $ E_n $ be the expected number of unoccupied seats.

Let m be in $ \{1,…,n-1\} $ and assume that the first couple sit in seats $ m $ and $ m+1 $ . Then there are $ m-1 $ free seats to the left of them and $ n-(m+1) $ free seats to the right of them. The expected number of unoccupied seats at the end of the process is the expected number of unoccupied seats to the left of them, plus the expected number of unoccupied seats to the right of them. Thus, assuming the first couple sit in position $ m $ and $ m+1 $ , the the expected number of unoccupied seats is $ E_{m-1}+E_{n-(m+1)} $ .

Summing over all the possible choices of $ m\in\{1,..,n-1\} $ , each picked with probability $ 1/(n-1) $ , we get \[E_n = \frac{1}{n-1}\sum_{m=0}^{n-1} (E_{m-1}+E_{n-(m+1)})\]

For each $ j $ in $ 0,\cdots,n-2, $ $ E_j $ appears twice in the above summation. So \[E_n=\frac{1}{n-1}\sum_{m=0}^{n-2} 2E_m.\]

We can directly compute $ E_0=0, $ $ E_1=1 $ , and then use the formula for higher terms, giving \[E_2=0\] \[E_3=1\] \[E_4=2/3\] \[E_5=1\] \[E_6=16/15\]

If you want to speed up calculating a bit you can notice that the summation for $ E_n $ looks a bit like the summation for $ E_{n-1} $ , exploiting this gives \[E_n=(\frac{1}{n-1})(2 E_{n-2}+(n-2)E_{n-1}).\]

Flipping Hexagons

The answer is 1068.

To see the answer to this question, it’s worth thinking about all the possible positions that our tile can be in after two steps. We see that the tile may be

• In its original position, and not rotated at all
• Immediately adjacent to the original tile, and rotated by either 120 or 240 degrees
• Two steps away from the original tile, by doing the same move twice (e.g. two steps north of the original tile), and not rotated at all
• Two steps away from the original tile but by applying different moves, e.g. going north and then north west, rotated either 120 degrees or 240 degrees.

One could think of every different position the tile could be in, 31 different positions if we include the different rotations, but it makes the problem easier if we just classify all of the possible positions as being as one of the four types above. We label these four positions A, B, C and D respectively.

Since there is a symmetry to the problem, if we are to be back at our starting position after six steps we must also be in one of the four positions above after four steps. So we really need to calculate the number of ways of getting from a tile of type i to a tile of type j in two steps. For example, from our original position (position A) we have one way of getting to each of the six positions labelled with a C, so we think of there being six ways of going from A to C. Similarly, there are six ways of going from A back to A.

For the rest of the solution we use matrices, but if you are not familiar with matrices then it is possible to think of all paths from 0 to 0 in six steps just by labelling them in terms of where the path is after two steps and four steps, and then multiplying together the possible ways from position i to position j to count all paths.

We build a $ 4x4 $ matrix M with the entry in position (i,j) being the number of ways to get from position i to position j in two steps. We get the matrix \[ M=\begin{pmatrix} 6&1&1&1\\12&11&6&4\\6&3&8&2\\12&4&4&8\end{pmatrix} \] Then the number of paths from our original position back to itself in six steps is just the top left entry of M^3, which is 1068.

Getting Out of Bed

The answer is 10/17

First we note that, if we are to end up with the alarm off, the light off and the water unspilled, we can never knock over the glass of water. So the set of intermediate states we can pass through can be labelled

• A= alarm on, light off, glass upright
• B = alarm on, light on, glass upright
• C= alarm off, light on, glass upright
• D= alarm off, light off, glass upright.

There are infinitely many paths from A to D, one way to solve the problem is to find a way to write down the infinite set of possible paths, sum up this infinite set of probabilities and reach the answer.

Alternatively, we let $ P_A $ be the probability that we would eventually reach state D, starting at state A, $ P_B $ be the probability that we would eventually reach state D starting at B, and $ P_C $ is the probability that we would eventually reach state C starting at C.

From position C, Ralph manages to turn off the light and reach position D with probability $ 1/2 $ . With probability $ 1/4 $ he turns on his alarm and reaches state B. With probability $ 1/4 $ he upsets his water and so fails.

Thus $ P_C=1/2 + 1/4 P_B $

Similarly $ P_A=1/2 + 1/4 P_B $

$ P_B= 3/8 P_A + 3/8 P_C $

Solving these equations gives $ P_A=10/17 $

Apollonian Circle Packings

The answer is 20.

Rather than keeping track of the radius, we keep track of the inverse radius, 1/radius, and so count how many circles have inverse radius <150. If we have three circles of inverse radius $ k_1, k_2 $ and $ k_3 $ then, by solving a quadratic equation for $ k_4, $ we see \[k_4=k_1+k_2+k_3+ 2\sqrt{k_1k_2+k_2k_3+k_3k_1}\] The hard part is to think about how to encode all of the information. If a hole is labelled $ (k_1,k_2,k_3) $ , then by filling it with a circle of radius $ k_4 $ we will generate holes labelled $ (k_1,k_2,k_4) $ , $ (k_1,k_3,k_4) $ and $ (k_2,k_3,k_4) $ . So to count circles, we draw a tree starting with label (2,2,3) and keeping going until we generate labels $ (k_1,k_2,k_3) $ where the corresponding $ k_4 $ would be larger than 150. This tree can be worked out by hand, in the end we see there are 20 circles.

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