BMO1 2018

The first round of the British Mathematical Olympiad was sat yesterday. The paper can be found here, and video solutions here. Copyright for the questions is held by BMOS. They are reproduced here with permission.

I hope any students who sat the paper enjoyed at least some of the questions, and found it challenging! The following commentaries on the problems are not official solutions, and are not always full solutions at all, but contain significant steps of solutions, so would be best saved until after you have attempted the problems, if you are planning to do so. I’ve written quite a lot about Q5 because I found it hard (or at least time-consuming) and somewhat atypical, and I’ve written a lot about Q6 because there was a lot to say. I hope at least some of this is interesting to some readers of all levels of olympiad experience.

Question 1

A list of five two-digit positive integers is written in increasing order on a blackboard. Each of the five integers is a multiple of 3, and each digit {0,1,…,9} appears exactly once on the blackboard. In how many ways can this be done? (Note that a two-digit number cannot begin with zero.)

It’s a trope of BMO1 that the first question must be doable by some sort of exhaustive calculation or listing exercise. Of course, that is rarely the most efficient solution.

However, there is normally a trade-off between eliminating all listing, and reducing to a manageable task.

The key observation here is that writing the integers in increasing order is really just a way to indicate that order of the choices doesn’t matter. Even if that seems counter-intuitive. The question wants to know how many ways to choose these five numbers. The order of choice doesn’t matter since we’re going to put them in ascending order on the blackboard anyway.

You want to make your choices with as much independence as possible. So it would, for example, be a bad idea to choose the smallest number first. How many possibilities are there where the smallest number is 24? What about 42? What about 69? These are all different, and some are zero, so will make the computation very taxing.

However, you might notice that the digits {0,3,6,9} have to go together to form two numbers, and the rest have to pair up with one digit from {1,4,7} and one from {2,5,8}. You might know that an integer is divisible by 3 precisely if its digit sum is divisible by 3, but in this context you wouldn’t lose too much time by simply listing everything! These tasks are now completely separate, so you can take the number of ways to pair up {0,3,6,9} and multiply by the number of ways to pair up {1,4,7} and {2,5,8}. You need to take care over the ordering. It does (obviously) matter which is the first digit and which is the second digit in a number!

Question 2

For each positive integer $n\ge 3$ , we define a n-ring to be a circular arrangemet of n (not necessarily different) positive integers such that the product of each integer with its two neighbours is n. Determine the number of integers n in the range $3\le n\le 2018$ for which it is possible to form an n-ring.

It’s sometimes a good idea to try small examples in problems, but sometimes small examples can have features which distract from the most important aspects of the setup, which are best studied in large examples. Here, for example, having some good notation, eg $(a_1,a_2,\ldots,a_n)$ for the integers on the ring is essential, and then converting the statement into this language. Here, this means $a_{k}a_{k+1}a_{k+2}=n$ for every k. (The indices cycle in the obvious way, but that doesn’t matter too much at this stage.)

The key bit is for every k. So, combining for different values of k, we find $a_ka_{k+1}a_{k+2}=a_{k+1}a_{k+2}a_{k+3}$ . Since everything is positive, this means $a_{k+3}=a_k$ , and so in fact $(a_1,a_2,a_3)$ determines the entire n-ring, as $a_1=a_4=a_7=\ldots$ and so on.

Note now that if n is not a multiple of 3, then in fact as we chase this equality round the circle, we will visit every site before getting back to $a_1$ . You might choose to phrase this formally, but the key deduction is that all the values must be equal. It then follows that this is only possible if n is also a cube, for which $(n^{1/3},n^{1/3},\ldots,n^{1/3})$ works.

If n is a multiple of 3, it turns out to be possible to make an n-ring. It’s not your responsibility to explain why the argument above doesn’t apply in this case. All you have to do is give an example. Note that it’s not enough just to assert that the argument above doesn’t work. It’s possible that multiple of 3s don’t work, but you need a different argument. An example is $(n,1,1,n,1,1,n,1,\ldots)$ .

Question 3

Ares multiplies two integers which differ by 9. Grace multiplies two integers which differ by 6. They obtain the same product T. Determine all possible values of T.

Students who have studied past papers or comments on this blog (cf Q3 here, and the second bullet on Q3 here) may have found the mathematical content of this question familiar. Also BMO1 2011/12.

The main interest is why this situation described can’t happen when the couple choose large integers. I chose to parameterise the integers as $(n-3, n+3),(m+5,m-4)$ , and so one has to solve $n^2-9=m^2+m-20$ , ie

$n^2=m^2+m-11.$

The LHS of this is a square. Let’s call integers of the form m(m+1) antisquares. Note that the squares and the anti-squares are alternating as we go through the integers, and they are increasingly widely separated as their values get large. In particular, there are only a few square-antisquare pairs which differ by 11.

There are a number of ways to establish what this handful of small solutions could be in a square-sandwiching argument such as this, but ultimately one can always just check a small collection.

Question 4

Let $\Gamma$ be a semicircle with diameter AB. The point C lies on the diameter AB and points E,D lie on the arc BA, with E between B and D. Let the tangents to $\Gamma$ at D and E meet at F. Suppose that $\angle ACD=\angle ECB$ .

Prove that $\angle EFD=\angle ACD+\angle ECB$ .

My first thought was that there was a typo in the question. Why would you be asked to prove some relation involving the sum of two angles, which you have been told are equal? (Ie rather than $2\angle ACD$ ?) But in fact it’s completely natural, you are being encouraged to think about the angles separately.

We have two tangents. These must be encoding an angle relation. Perhaps this is via the alternate segment theorem, but it didn’t feel like C was part of any particularly relevant alternate segments, so it was better to mark in the centre of the semi-circle O. Then I have the property that the tangents are perpendicular to the radii. Conveniently, there are loads of isosceles triangles involving O, which seems a promising fit for a condition involving two other equal angles.

At this point, several things dropped out all at once. Firstly, the required statement is equivalent to showing that CDFE is cyclic; secondly that ODFE is known to be cyclic. Finally, that the equal angles in ODE plus the given equal angles are consistent with OCDE being cyclic.

This sort of cascade of deductions is fairly common in geometry problems when you add some extra structure which turns out to be relevant. It’s best to take a pause to work out what you actually need to show. It will suffice to show OCDE is cyclic, and we don’t need to have F on the diagram any more. We have two sets of equal angles.

One option is to argue that wherever circle ODE hits AB for a second time will have the equal angle property required of C. And one can show that C is unique, since $\angle ACD$ is decreasing as C moves from A to B. I think this is a dangerous approach, and doesn’t work in some other situations.
I think a better option is to start from the unusual point. That is, consider the second intersection point of circle CDE and line AB, say X. Using the two circle theorems, we find $\angle XDE=\angle DEX$, so X lies on the perpendicular bisector of DE. But we know that this must meet AB at O, so we have shown X=O.

Alternatively, one could notice that Daniel has specifically given us a semi-circle, but there’s no reason not to complete it into a circle. All the more so when we notice that the given angle equality says that DC and EC are reflections of each other in the normal to AB at C. In other words, if we extend these to E’ and D’ respectively on the other half of the circle, the four angles at C are all equal, ie D’ ie the reflection of D in AB.

Earlier, we said that we didn’t have any interesting ways to use the alternate segment theorem, but now we definitely do, since we can study the angles $\angle FED=\angle ED'D$ . In particular, we can shown that triangles FED and CD’D are similar, from which the required angle equality follows.

I thought this was a super problem, and would be really instructive for anyone studying in future years. Note how in both methods, a small but carefully-chosen addition to the configuration can be motivated by what’s actually present, and then completely opens up the problem, much more so than lengthy angle calculations (or whatever) straight from the start.

Question 5

Two solid cylinders are mathematically similar. The sum of their heights is 1. The sum of their surface areas is $8\pi$ . The sum of their volumes is $2\pi$ . Find all possibilities for the dimensions of each cylinder.

I didn’t enjoy this question very much, and I doubt I would have got many marks for what I did in my first 90 minutes. If $\alpha$ is the scale factor, one can reduce the information given in the problem to the three equations:

$(1+\alpha)h = 1,\quad (1+\alpha^2) r(h+r) = 4,\quad (1+\alpha^3) r^2h=2,$ (*)

or something similar to this. Note that the first equation determines h as a function of $\alpha$ , and given this, then the third equation determines r as a function of $\alpha$ . So in principle one could then substitute the resulting expressions for h and r in terms of $\alpha$ into the second equation, and obtain a giant equation involving $\alpha$ alone, which one hopefully can then solve. We know it will be a polynomial in $\alpha$ , at least after we do enough multiplying up.

But surely this isn’t the right way to do the problem? It seems likely that the numbers have been chosen with some artistry, so that insight into what’s going on in the setup will streamline this calculation. My main guesses were:

There’s some easily guessable (for example integer-valued) solution, eg $\alpha=2$ , or even $\alpha=1$ , and finding this will open the door into a better recasting of the main equations (*);
One can come up with an inequality involving the LHS side of the second equation, given the outer relations. This felt like a very strong guess, especially since such questions have appeared before (indeed Jeremy is also the author of Q2 on BMO2 2014).
Given a relation about third powers of (h,r) and a relation about h, it seemed reasonable that there was some AM-GM relation involving the quadratic term in the second equation. It seemed particularly likely that the value 4 might be the equality case, and one could then chase through the argument to find all the solutions.

To be honest, I was so convinced that the second point must be the correct way to do the problem that even when I found examples where the objective function was both >4 and <4, it seemed more likely I’d made a calculation mistake than the idea was wrong.

More fool me, because it turns out that the best way is really to multiply everything out, or some proxy for this. As James explains in the video, this leads to

$P(\alpha)=\alpha^6-3\alpha^5 - 5\alpha^4+10\alpha^3 - 5\alpha^2 - 3\alpha+1=0.$

A couple of observations about this equation:

The coefficients are symmetric. Ie the coefficients of $\alpha,\alpha^5$ are the same, etc.
I can’t guess any roots.

However, the first observation does tell us something about the structure of the roots. Because if we study $P(\frac{1}{\alpha})$ we get an expression which looks like the original polynomial, especially if we multiply up. Precisely, we have

$P(\frac{1}{\alpha}) = \frac{P(\alpha)}{\alpha^6},$

and so if $\alpha$ is a root, so is $1/\alpha$ .

We could have made this observation much much earlier, because $\alpha$ is defined as the scale factor, but we didn’t say whether it was greater or less than 1. So whenever we have two suitable similar cylinders, we can consider the scale factor from the larger to the smaller, or from the smaller to the larger. Both of these must satisfy the relation, and they are reciprocals.

It turns out that writing $t=x+1/x$ is a useful approach in general for such symmetric polynomials. This is because a symmetric polynomial P of degree 2d can be written as:

$P(x)= x^d Q(x+\frac{1}{x}),$

where Q is a polynomial of degree d. In particular, this means that the roots of P (which do not include zero since P is symmetric so must have non-zero constant term), can be found by taking all roots c of Q, then solving x+1/x = c, obtaining a pair $(\alpha,1/\alpha)$ .

We’ll show this in practice soon, but for now, let’s just say that applying this to the degree-6 polynomial for $\alpha$ leads to a cubic for $t=\alpha+1/\alpha$ , and one of the roots is 4, which is spottable.

With this insight in mind, one could repose the original equations we stated in terms of $z$ and $1/z$ instead of $\alpha$ and 1. So in fact we would have

$(z+1/z) h =1,\quad (z^2+1/z^2)r(h+r)=4,\quad (z^3+1/z^3)r^2h=2.$

Note that $z^2+1/z^2=(z+1/z)^2-2$ and $z^3+1/z^3=(z+1/z)^3-3(z+1/z)$ , and so it is slightly more manageable to manipulate once we have rewritten with $t=z+1/z$ as

$th=1,\quad (t^2-2)r(h+r)=4,\quad (t^3-3t)r^2h=2.$

Note, for example, that using the first equation to remove h from the third equation is the same as in the original setup with $(1+\alpha^k)$ s, but here the expressions are nicer.

Overall, I think this question was rather off-piste for an olympiad paper, and I have sympathy (in the sense that I literally did the same) with any students who spent significant time trying to find more conventional inroads, since the usual advice is to look for that rather than start a giant calculation.

For what it’s worth, this notion of studying polynomials based on symmetry properties of their roots exposes the tip of a very deep and very interesting iceberg in mathematics. Such things are extremely far from the focus of either olympiad or research sections of this blog, but if any budding (or senior…) Galois theorists are reading this and would like to contribute something accessible as a long footnote, please do get in touch!

Question 6

Ada the ant starts at a point O on a plane. At the start of each minute she chooses North, South, East, or West, and marches 1 metre in that direction. At the end of 2018 minutes, she finds herself back at O. Let n be the number of possible journeys which she could have made. What is the highest power of 10 which divides n?

The main part of this question is enumerating n, the number of paths with length n from the origin back to itself. This is a nice and well-known problem. Two observations:

The fact that 2018 is even is important.
In one dimension, this problem is clear, because one must have the same number of +1s as -1s in the walk, but these can be placed in any order, giving $\binom{2k}{k}$ possibilities for walks with 2k steps.

In two dimensions, it’s a bit more complicated because we have to take the same number of N steps as of S steps, but this number could be anything from 0 up to k.

One neat idea is to view the walk from the perspective of axes given by the diagonals of the original axes. Then each NESW step corresponds to a step of length $1/\sqrt{2}$ on each of the diagonal axes. For example, going E corresponds to taking a step towards NE and a step towards SE. Then, by studying NE/SW and SE/NW axes separately, one obtains $\binom{2k}{k}^2$ as the total number of choices.

I like this sort of argument, where one saves work by giving a combinatorial reinterpretation of the given situation, which opens up easier lines of attack. But for now, if you hadn’t seen the diagonal axes or something like it before, then I imagine that is quite a big step, and perhaps it’s good to see that this wasn’t necessary.

Suppose that we take m+m N-S steps, and (1009-m)+(1009-m) E-W steps. Then the number of such paths is

$\binom{2018}{2m}\binom{2m}{m}\binom{2018-2m}{1009-m},$

based on counting first the number of ways to steps the steps into NS vs EW, and then without those classes. But of course, we could have done this decomposition in any order, and the multinomial coefficient giving this total number of ways,

$\binom{2018}{m,m,1009-m,1009-m} := \frac{2018!}{m!\cdot m!\cdot (1009-m)!\cdot (1009-m)!}$

is worth knowing, and doesn’t depend on the order you proceed.

Note that $m!\cdot (1009-m)!$ looks useful, because it’s related to some choice of 1009 objects. So we can rewrite as

$\frac{2018!}{1009!\cdot 1009!}\times \left(\frac{1009!}{m!\cdot (1009-m)!}\right)^2 = \binom{2018}{1009}\binom{1009}{m}^2.$ (*)

This is great, because when we sum over m, we now just have to calculate $\sum_{m=0}^{1009} \binom{1009}{m}^2.$

This is one of the harder exercises I put on my first sheet of combinatorial problems at the annual camp for new students, and there are several approaches, none involving heavy manipulation of factorials (!), but all rely on first writing $\binom{1009}{m}^2$ as $\binom{1009}{m}\binom{1009}{1009-m}$ since this is leads to more natural combinatorial interpretations. In any case, for example by considering how to choose a team of size k out of a group of k boys and k girls, we find

$\binom{2k}{k}=\sum_{m=0}^k \binom{1009}{m}\binom{1009}{1009-m}=\sum_{m=0}^k \binom{1009}{m}^2.$

So when we return to (*) and sum over m, again we obtain $\binom{2018}{1009}^2$ . In fact, this argument precisely matches the diagonal projection argument. When we resplit the multinomial coefficient based on choosing 1009 objects, this precisely corresponds to grouping NE/SW moves and NW/SE moves.

There are a vast number of interesting things one can say about nearest-neighbour walks on $\mathbb{Z}^d$ , but as a probabilist one must mention the classical result describing the behaviour of a random walk, where the next step is chosen uniformly at random from the 2d options.

By the ‘projecting onto the diagonal’ argument, one can see that the case d=2 really consists of two independent copies of the case d=1, and similarly for larger d. In particular, each of the coordinate processes returns to the origin infinitely often (we say ‘almost surely’ to mean ‘with probability one’, because of course it is an option, albeit a very improbable one, that for example the walk goes straight off to $+\infty$ without ever backtracking.). But if we study whether it returns to the origin ‘often enough’ for large times that it it’s likely that both (or all in higher dimension) coordinate processes are zero, then it turns out that d=2 is just ok for this (in the sense that the mean time until it’s at the origin is infinite, but it does happen with probability one), while for $d\ge 3$ it fails, and the walk almost surely visits the origin only finitely many times. This argument can then be applied to any finite collection of points near the original, and it becomes meaningful to say the walk ‘escapes’. (Or, is transient.)

As Kakutani (of the product martingale theorem) said, and was subsequently quoted as the dedication on every undergraduate pdf about random walks: “A drunk man will find his way home, whereas a drunk bird may get lost forever.” Whether a random walk is a good model for either of these effects remains a topic of considerable scientific interest.

One can say a bit more, looking at the progress of the walk once you’ve zoomed really far out, so that it just looks like a random curve in the plane. It turns out that from this perspective, the so-called Brownian motion that you see doesn’t feel the coordinate axes that you started from. It’s invariant under rotating the plane, essentially because this is true of products of the normal distribution (perhaps familiar to some readers as the bell curve) that approximately describes the value of each coordinate.

In high generality, the properties of the random walk discussed before are truly properties of the plane itself (or $\mathbb{R}^d$ itself) rather than the fine details of the coordinate system used to describe it. This is then the entrance point into a huge area of research, namely studying the properties of spaces based on the properties of random processes defined on those spaces. And rather than try and squeeze a characterisation of any of the crowning achievements of probability into a footnote to an olympiad paper review, I’ll stop there.

4 thoughts on “BMO1 2018”

olympiadpreparation on December 1, 2018 at 9:08 am said:

Very detailed and descriptive post with questions and illustrations of British Maths Olympiad Exam. Thanks for the informative post, please keep on writing such a useful post for the students preparing for Mathematical Olympiads. All the best!

Reply ↓
Alastair Horn on December 1, 2018 at 1:39 pm said:

I honestly wouldn’t have posed that question 5 to my worst enemy.
The nastiest thing I found is that it’s perfectly possible to get a polynomial in h, instead of in alpha. This wouldn’t have any symmetry or quite frankly any hope. I spent two hours on this problem in the exam, after completing the first 4 in 1.5 hrs, and at no point did I think a nasty polynomial in alpha would be useful because a) I’m not even supposed to find alpha and b) it’s gonna have square roots in that need eliminating.
I’d also started off with the assumption that alpha was more than 1. In my opinion you need to cotton on to the fact that the symmetry will exist before you start finding that polynomial, else it seems dreadfully undesirable. I actually did know in the back of my mind how to solve those symmetrical polynomials but it would never in a million years have occurred to me that it would be symmetric.
Credit to anyone who solved this, especially if they managed it in less than an hour.
Personally, it ruined my day.

Reply ↓
- Amrit Lohia on January 1, 2019 at 11:29 am said:
  
  If I recall correctly, you can write u = h^2 + h, and then polynomial in h reduces to a cubic that easily factorises. That’s how I solved it, and it seemed fairly natural at the time, because the way I derived the polynomial gave me expressions like h^2 + (h+1)^2 = 2h^2 + 2h + 1 = 2u+1, (h+1)^3 – h^3 = 3h^2 + 3h + 1 = 3u + 1, and (2h+1)^2 = 4h^2 + 4h + 1 = 4u + 1.
  
  Reply ↓
Pingback: BMO2 2022 | Eventually Almost Everywhere

Eventually Almost Everywhere

A blog about probability and olympiads by Dominic Yeo

BMO1 2018

4 thoughts on “BMO1 2018”

Leave a Reply Cancel reply

Share this:

Like this:

Related

4 thoughts on “BMO1 2018”

Leave a Reply Cancel reply