BMO1 2021

Posted on by

The first round of the British Mathematical Olympiad was sat on Thursday by roughly 2000 pupils in the UK, and a significant number overseas on Friday.

For obvious reasons, much of the past 18 months has been dominated by logistical rather than academic problems, so it’s refreshing to be returning to the traditional format of this exam, even if the marking has been stayed online.

I wasn’t involved in setting in this paper, so here are some thoughts on the problems. These aren’t supposed to be official solutions, and it’s entirely possible that I’m missing the most natural approach or framing. Students reading this in future years are advised, as always, that such commentaries are normally more valuable after attempting and digesting the problem yourself first.

Note that the copyright to the problems is retained by BMO, and I’m reproducing here with permission. The paper can be found in its original format here.

Problem One

If one exhibits eighteen (= 6 x 3) explicit examples of relevant sums of consecutive positive odd numbers, one has finished the problem. An exhaustive search is impractical and uninteresting. However, beyond that, we would also like to find integers N which we are convinced have this property without needing to explicitly decompose them into the desired sum format.

Let’s study such a sum. We need an even number of odd numbers to end up with an even sum. Probably the algebraically neatest way is to set up such a sum symmetrically as:

2n-k, 2n-(k-2),\ldots,2n-1,2n+1,2n+3,\ldots, 2n+k,

for k an odd number. The sum of this sequence of consecutive odd numbers is 2n(k+1). So, we seek integers N which can be written as 2nm, where m is an even number, in as many ways as possible. Note that if we have an integer N which can be factorised as a product of two distinct even numbers we are forced to take the larger as 2n, and the smaller as m, since we require 2n-k to be strictly positive.

It’s equivalent to finding integers M which are less than 100 and have lots of factors (then multiplying by 4 to recover an N), and there are a few ways to do this, including now potentially by exhaustive search. It is useful to remember that is M can be factorised into primes as M=p_1^{a_1}\ldots p_k^{a_k} then its factors can be described as the set:

\{1,p_1,p_1^2,\ldots,p_1^{a_1}\}\times \{1,p_2,p_2^2,\ldots,p_2^{a_2}\}\times\cdots \times \{1,p_k,p_k^2,\ldots,p_k^{a_k}\},

In particular, the number of such factors is (a_1+1)(a_2+1)\ldots(a_k+1), independently of the choice of the primes. This gives a recipe for constructing all integers M<100 with at least twelve factors. We could take (a_i) to be some permutation of (11), or (5,1), or (3,2), or (2,1,1), which give the following valid M:

M=2^5\times 3 = 96, \; M=2^3\times 3^2 = 72, \; M=2^2\times 3\times 5 = 60, M=2^2\times 3 \times 7 = 84,\; M=3^2\times 2 \times 5 = 90,

and the corresponding valid N are 240, 288, 336, 360, and 384.

For what it’s worth, this problem took me a while. I spent a long time saying things like “we need numbers that can be written as 4n and as 8n and as…” and aiming to conclude “all multiples of 24 greater than 24 x ?? will work”, but this didn’t ever generate enough examples of one class.

Problem Two

In order to have won exactly 30% of the games so far, the number of games so far must be a multiple of 10, and the same is true for 70% success rate. The other success rates have similar constraints, but the multiples are smaller. After ten games, of course Arun cannot have simultaneously won both 30% and 70% of the total! So we need at least twenty games.

It feels as if we should be able to include the other success percentages so long as we can make 30% and 70% work. But can we do this in twenty games? This would require Arun to win 3 out of the first 10, and 14 out of the first 20 (or the exact opposite), and after some head-scratching, this is impossible, since it would require winning eleven out of the ten games between these observations. This is a nice observation, and we now know the answer must be at least thirty. Given that we have made some nifty, rigorous deductions already, one might speculate that this is the true answer. To verify this, we just have to give a construction, and there are a number of ways to achieve this, for example such that Arun wins

  • One of the first two
  • Two of the first five
  • Three of the first ten
  • Twelve of the first twenty
  • Twenty-one of the first thirty

To get full credit, almost any justification that a construction exists for 30 games would be fine – but one must be given. Otherwise how do you know that the true bound isn’t 40 or 50 because there’s some other reason why 30 fails?

Problem Three

Facing this problem for the first time, there’s a temptation to try values smaller than 2021, and this may well be useful. If nothing else, such experiments may well lead to a conjecture of the general form of the answer. Personally, I find it relatively easy to make mistakes when dealing with small numbers, and would turn to this as a second strategy after trying more theoretical routes first.

First note that the condition 0\le n\le 11 could be replaced by n\ge 0, since we are forced to include zero pieces of weight 2^{11}=2048, and would similarly be forced to include zero pieces of weight 2^n for any n\ge 11. (%)

When counting a potentially complex set, we should start by seeing whether there is anything which we can control effectively. For example, I don’t think it is clear how to control the number of pieces of weight 64 in a configuration. However, powers of two lend themselves well to inductive arguments (if you take the powers of two and multiply them all by two, you still have powers of two!) and to studying parity (that is, whether a number is odd or even).

In this case, note that you must have either one or three of the pieces with weight one to ensure the total weight is odd. Similarly, if the goal had been 2022, we would need either zero or two of these pieces to ensure the total weight is even.

So that settles the number of pieces of weight one, and it remains to solve the problem for total weight 2018 and 2020 with the extra condition that we are no longer allowed to use any pieces of weight one. A way to capture this is to divide everything in the problem by two. So we are now trying to capture all the ways to generate weights 1009 and 1010.

We can reformulate this more generally, and assert that the number of configurations f(n) to make total weight n satisfies the relations:

f(2n)=f(2n+1)=f(n)+f(n-1). (*)

It would be quite tiresome to solve backwards in a binary search fashion, but perhaps this is where trying some small examples turns useful. Either by observation on the original problem, or by thinking about (*) with some initial condition like f(0)=f(1)=1, we find that f(n)=\lfloor n/2\rfloor +1. (That is, f(n)=\frac{n+2}{2} when n is even, and f(n)=\frac{n+1}{2} when n is odd.)

As a final aside, this question is an excellent exercise in using generating functions in an olympiad context. A couple of points are worth making:

  1. It is important to decide whether you’re including f(0) as an example, much more so than in the original argument. As we’ll see, it works better if you do include it, and will avoid an awkward sequence of algebra steps.
  2. Figuring out the answer, for example from small-ish cases, will make a generating function argument easier unless you are very fluent with manipulating rational functions. In this case, we would be studying \sum_{n=0}^\infty f(n)x^n, and trying to show that it is equal to

\sum (\lfloor n/2\rfloor +1)x^n = (1+x)(1+2x^2+3x^4+\ldots) = \frac{(1+x)}{(1-x^2)^2}. (*)

Many readers who’ve played around a bit with generating functions may find it easier to go from the left to the right than vice versa.

Writing down a direct generating function for f(n) and showing it matches up with (*) remains a good exercise. It is helpful to bear in mind the discussion at (%).

Problem Four

Since I last blogged regularly, I have given a series of masterclass on Euclidean geometry three times, including twice in an online format.

Part of the point of this masterclass is to get younger students to think in more general terms about what they are doing when they are solving geometry problems, even when they are straightforward. In a competition, time is tight, and anything that gets the job done is good, but there’s still value in reflecting on these ideas here. Two ideas in the first session are:

  • Attacking the conclusion coherently
  • Clean angle chasing

and this problem offers a good example of both of these in practice.

We’ll start with attacking the conclusion coherently. We’ve got to prove that a triangle is equilateral. How can we achieve this? There are a number of ways:

  • Prove all three lengths are equal
  • Prove that all three angles are equal
  • Prove that two angles are equal to 60 degrees.
  • Prove that one angle is equal to 60, and (any) two lengths are equal
  • Prove that one angle is equal to 60, and the other two angles are equal

It’s important to keep all of these in mind as one explores the configuration. It’s genuinely unclear at the very start which of these characterisations of equilateral triangles will be most appropriate. Note though, that the configuration is symmetric in the roles of D and E, so that, for example, proving that the angle at D is 60 would be sufficient, since by symmetry the angle at E would also be 60, and we would conclude.

As regards clean angle chasing, the main moral here is to avoid angle arithmetic unless you are convinced it’s necessary. Ideally one keeps track of what could be determined in terms of other quantities, and only attempts the algebra/arithmetic once you are sure that it will work. It certainly isn’t helpful to have diagrams littered with angle measures like 240^\circ - \theta - \frac{\alpha}{2}. Equality is the best thing to aim for. Try and demonstrate and notate equal angles wherever possible.

For example, here, even before introducing C,D,E, there is plenty of structure which might useful. Essentially every length in the configuration involving (O_1,O_2,A,B) is equal, and all the angles are 60 or 120.

So we bear this in mind. I would consider proving that \angle DO_1E=60^\circ with the following figure.

There are number of ways to complete the argument. Here are a couple of more obscure ones that illustrate my approach.

Firstly, let’s ignore the result that \angle DO_1E=60^\circ and proceed directly to \angle O_2DO_1=60^\circ. It suffices to show that the blue angles are equal, which is equivalent to demonstrating that ADO_2O_1 is cyclic.

To achieve this, we would like to show that the angle \angle AO_2D is equal to the red angle we’ve already discussed, and this follows by chasing round, using that O_1 is the centre of triangle ABC, and then the fact that AO_2D is the external angle opposite \angle ABC in cyclic quadrilateral ABCO_2. Indeed, note that this use of an equal external angle rather than ‘opposite angle is 180 – […]’ is the textbook example of clear angle chasing, where focusing on equality rather than arithmetic massively cleans up many diagrams.

As a second, rather overblown way to complete the argument, let’s show that the angles at D and E are equal, without calculating them. Since O_1D,O_1E are angle bisectors, we have two pairs of equal angles as shown.

It would suffice to show that these measures are themselves equal. This is saying that line ECO_2D is the external angle bisector of \angle ACB. And this is true, since O_2 is the arc-midpoint of AB on \Gamma_1!

I hope these observations are interesting. But, to reiterate, this level of complexity is unnecessary, and arguments by congruent triangles or direct angle chasing are perfectly satisfactory too!

Problem Five

The punchline of this problem is that m(N) is an integer precisely if N is a triangle number, from which it is quick to count the number of such N.

But how to arrive that this punchline? It is reasonably clear that the N-set with minimal mean must have the form (1,2,\ldots,k, N). One could proceed by setting up inequalities involving the means of (1,2,\ldots,k-1,N) and (1,2,\ldots,k,k+1,N) to establish a relationship between k and N.

But there is a more direct route. A useful, and very intuitive result about means is the following. If you have a set of numbers with mean x, and you add into the set a new number y, then the mean of the new larger set is between x and y. In particular, if y>x, then the new mean is larger than x.

In particular, consider the mean of (1,2,\ldots,k,N). If it is less than k, then removing k gives a smaller mean. If it is greater than k+1, then adding k+1 gives a smaller mean. So since the mean is an integer, it must be equal to k or k+1. That is, we have

\frac{1+2+\ldots+k+N}{k+1}=k\text{ or }k+1.

These lead to N=\frac{k(k+1)}{2}\text{ or }\frac{(k+1)(k+2)}{2}.

Problem Six

There must be some significance to the choice of 71 terms, and the 999,999 but it’s hopeless to try and see this immediately. In this scenario, it really is helpful to play around with semi-small examples.

Note that the second term is 1 regardless of whether we view this as P for PREVIOUS or S for SUM. However, if we then have an S, our sequence starts 1,1,2,2… or 1,1,2,4,… and these are bad, as once we have two even consecutive even numbers, we are doomed to see even numbers forever.

So once we have a common factor, that common factor is retained. How would we introduce a factor of, say, 11? Well, if you take 1,1,1,1,1,1,1,1,1,1,1 then take an S, you get 11, and afterwards you get either 11 or 22.

This gives a clue of the right way to set up the problem. For definiteness, we consider the second term to be an S. If you then consider a sequence of Ss and Ps, and write down the number of Ps between successive Ss (which may be zero) as a list p_1,p_2,p_3,\ldots, it holds that \sum p_i=70, and that each string of p_i Ps introduces a factor of p_i+1, leading to

\prod (p_i+1)=999,999=3^3\times 7\times 11\times 13\times 37.

Note that 2\times 3 + 6+10+12+36=70, so there exists a choice of the p_is that satisfies these relations simultaneously. (And if we had replaced 71 by a smaller choice, this would have been impossible.)

The actual answer to the problem is obtained by studying how to rearrange the blocks of SPPP…s, but the main challenge lies in reducing to this form.

I thought this was a hard problem for BMO, and was impressed to see some solutions under exam conditions.

Leave a comment