BMO2 2022

The second and final round of this year’s British Mathematical Olympiad took place on Thursday.

Here are some thoughts on the problems. I wasn’t involved in choosing the problems, although I did write Q4. I’ll say a bit more about this geometry problem than about the other three, so I’ve put this first.

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 Four

Let me explain how I devised this problem. Let A’ be the point diametrically opposite A on the circumcircle of triangle ABC. (Sometimes called the antipode of A.) Now consider any line L through A’, and let P be the point where it meets the circumcircle again. I was particularly thinking about lines L where P lay on the same side of BC as A’, as depicted.

Because AA’ is a diameter, there is a right angle . So I considering intersecting L with the lines given in the question, since this would create two cyclic quadrilaterals, denoted in the figure.

Let’s just focus on . This cyclic quadrilateral gives us two equal angles in many different ways. But a particularly nice pair is the one shown, because ACPB is also cyclic, which confirms that the angle measure is . In particular, by extending to E on AC, we get a third cyclic quadrilateral , and hence find out that .

So four lines go through D: AP, BC, and the perpendiculars from to the opposite sides of the triangle.

How to turn this into a question? The steps outlined above are relatively clear because

• the right angle at P is essentially given;
• there are four other right angles, two involving which are given, then one involving being perpendicular to AC, and the same for and AB, which are to be deduced,

so the cyclic quadrilaterals just pop out directly. This would then be too straightforward for BMO2, and would also waste the fact that four lines meet at D. It would suffice to work with as we did above, and assert that the corresponding result also held for .

To move towards the form of the BMO2 question, we consider taking P=A’, so that line L is actually the tangent to the circumcircle. We still have the quadruple concurrency at D, but now D lies on AA’. It seems almost certain that we wouldn’t have this concurrency if we built the figure using the tangent from any point other than A’. So this will be the configuration for the problem.

As the writer, I know that the four lines meet when T=A’, so I know I can force T=A’ by insisting that three lines meet, and then set the problem asking to prove that the fourth goes through the same point. One could have stated that meet, and ask to prove that the meeting point lies on BC. I preferred the one I chose. Reflecting on the difficulty of the problem:

• It is hard to draw a diagram which looks right! Essentially you have to draw a few, and if T ends up close to A’ on one, the diagram will look right.
• Crucially, we now only have four right angles in the figure, so only one pair of (symmetric) cyclic quads can be read off immediately

I think the cleanest way to attack the problem is to extend AQ to meet the circumcircle at T’, with the goal of showing T’=T. Then cyclic gives cyclic (in an exact reversal of the argument in the prelude earlier). What we don’t know is that are collinear, but this follows since now we derive from this new cyclic quad. Consequently T’=T.

There are many routes for coming up with olympiad problems in geometry and other topics, and the scenario I’ve described isn’t particularly typical for myself and certainly isn’t necessarily standard for other problem setters. Nonetheless, I hope that’s an interesting insight into the origin story of a problem like this.

Problem One

This question reduces to establishing whether

has infinitely many solutions in (m,n). The technique for proving via ‘square sandwiching’ that this is normally not possible has been discussed previously on this blog here:

and here:

This is a good opportunity to reflect in more detail. Let be a polynomial with integer coefficients, and we consider whether the image contains infinitely many squares.

Clearly if for Q another polynomial with integer coefficients, then this holds. Square sandwiching establishes that the answer is no when P(x) is a monic quadratic (meaning that the coefficient of is one) unless P(x) is the square of a linear polynomial. The same holds if the leading coefficient is a square. Note that the general case where P(x) is negative except on a finite range (eg if P has even degree and negative leading coefficient) is also immediate.

But there are several cases where the answer is yes:

• For example, when , we have P(n) a square whenever .
• Indeed, note that has this property too!
• Amongst non-monic quadratics, note that works when n is not a square because of the theory of Pell’s equation.

We could have the alternative question: if is always a square, does this imply . Indeed, one could generalise this and ask: if does this imply that for some choice Q?

Our original setting with is classical, due to Polya, and is a good problem for any students reading this. The case is handled by Polya and Szego. The case of general R is more challenging, and though it can be treated without heavier concepts, is probably best left until one knows some undergraduate algebra. Readers looking for a paper may consult Davenport, Lewis and Schinzel Polynomials of certain special types (Acta Arith. 1964).

Problem Two

Rearranging to get

is a good first step, as y appears only on the LHS. As y varies, the LHS is therefore constant, and so we deduce that , ie f is linear on the even integers.

There were then a number of ways to proceed, bearing in mind one had to study the odd integers and solve for C. Taking x even in the given equation is a good next step, because (after some careful argument about C and divisibility by powers of 2) is already known, leading to an expression for f(x+1), ie some control over the odd integers.

There were a few possibilities for how to piece the odds and evens together, and extract the constant C. It’s worth mentioning that if the problem had studied functions from the non-negative integers to the non-negative integers, then C=0 would have been a possibility. You might like to consider whether this could lead to extra functions satisfying the given equation.

Problem Three

I personally found this quite difficult. We have a large number of 50-dimensional integer vectors with entries bounded by [0,2022] such that their sum is (n,n,…,n) and we are tasked to show that we can split the sum to obtain (m,m,…,m) and (n-m,n-m,…,n-m).

It seemed helpful to replace each vector with the 49-dimensional vector . We now have a large number of 49-dimensional integer vectors with entries bounded by [-2022,2022] with sum equal to the zero vector. Our task is to show that we can partition into two smaller sums with sum zero. (*)

It seems likely that the role of 2022 is not important, and will just determine how large n must be. I was hoping there might be a quick proof along the following lines: Let denote the collection of vectors, and some subsets, inducing sums respectively. Clearly if , and we might expect to be able to find such that . I was hoping one could then move some vectors around (eg from ) to produce disjoint sets A,B for which , but I couldn’t see any way to achieve this.

This doesn’t mean it’s impossible though of course! And perhaps a contestant will find a successful argument along these lines during the olympiad.

In fact, it seems that a careful induction (on the number of cards, ie the dimension of the vectors) is the best way to proceed, and I will leave that there.

Advertisement

BMO1 2021

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:

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 then its factors can be described as the set:

In particular, the number of such factors is , 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 to be some permutation of (11), or (5,1), or (3,2), or (2,1,1), which give the following valid M:

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 could be replaced by , since we are forced to include zero pieces of weight , and would similarly be forced to include zero pieces of weight for any . (%)

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 to make total weight n satisfies the relations:

(*)

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 . (That is, when n is even, and 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 , and trying to show that it is equal to

(*)

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 . 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 is equal, and all the angles are 60 or 120.

So we bear this in mind. I would consider proving that 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 and proceed directly to . It suffices to show that the blue angles are equal, which is equivalent to demonstrating that is cyclic.

To achieve this, we would like to show that the angle is equal to the red angle we’ve already discussed, and this follows by chasing round, using that is the centre of triangle ABC, and then the fact that is the external angle opposite in cyclic quadrilateral . 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 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 is the external angle bisector of . And this is true, since is the arc-midpoint of AB on !

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 . One could proceed by setting up inequalities involving the means of and 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 . 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

These lead to .

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 , it holds that , and that each string of Ps introduces a factor of , leading to

Note that , so there exists a choice of the s 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.

BMO2 2019

The second round of the British Mathematical Olympiad was taken on Thursday by the 100 or so top scoring eligible participants from the first round, as well as some open entries. Qualifying for BMO2 is worth celebrating in its own right. The goal of the setters is to find the sweet spot of difficult but stimulating for the eligible participants, which ultimately means it’s likely to be the most challenging exam many of the candidates sit while in high school, at least in mathematics.

I know that lots of students view BMO2 as something actively worth preparing for. As with everything, this is a good attitude in moderation. Part of the goal in writing about the questions at such length is because I think at this level it’s particularly easy to devote more time than needed to preparation, and use it poorly. This year time is tight at the end of semester, and so what follows is closer to a set of complete solutions than usual, for which apologies, although I hope it is still possible to get a sense of how one might have come across the solutions yourself. Of course, this means that what follows will certainly spoil the problems for anyone who hasn’t tried them by themselves already.

The copyright for the problems is held by BMOS, and reproduced here with permission.

Question 1

As if often the case in geometry questions, what you’ve been asked to prove here isn’t the most natural property of the configuration. A good first step would be to see if there are stronger statements which are true.You are asked to show that triangle BPE is isosceles, but you aren’t told which of the three vertices is the apex. In fact, the task is to show that or, alternatively, . It’s not in general true that BE is equal to BP=EP. Unless you’re very unlucky, you can establish this from one diagram.

Now, you don’t immediately know whether it’s going to be easier to show that two lengths are equal, or that two angles are equal. However, you know that P lies on the perpendicular bisector of BC, hence BP=CP, which is a big clue. In particular, this means that P would be the centre of the circle through BCE. This clearly implies the given result, so deciding to prove this instead is a good strategy.

There are now a number of ways to prove this. Note that D lies on the altitude from A, and the feet of the perpendiculars from D to sides AB and AC are both present in the configuration so (just as for the orthocentre diagram) we can calculate most of the angles involving {A,B,C,D,E}.

For example, ABDE is cyclic, so , hence . This shows that AB is tangent to the circumcircle of BCE. But then the line L is a radius of this circle, and so its centre must be P, the unique point on L which is equidistant from B and C.

Alternatively, we could directly calculate and . But BPC is isosceles so . In general, the converse of ‘angle at centre is twice angle at circumference’ does not hold, but when we know P is equidistant from B and C this does hold, and so the angle relations precisely confirm that P is the centre of the circle through BPE.

My intention had been that the triangle would be acute-angled, to reduce the number of diagram options based on the magnitude of . If pursuing this second approach, one would need to be careful to account for whether P is on the same side or the opposite side of BC to E. That said, unless you do something very exotic, it should be exactly the same argument or calculation, and such a case distinction probably isn’t very important.

Question 2

First, a short remark. As stated, if n=5, a piece could move 3 squares to the left then 4 squares up, by Pythagoras. Handling all such options is likely to be quite annoying, since some values of n can be written in this Pythagorean form, and others cannot. This brings us to some good general principles for olympiad problems which look like this one:

• A construction, when one exists, will probably be possible using simple versions of the allowed moves / structures.
• An argument why a construction is impossible should probably be based on ideas which treat the simple moves similarly to the more complicated moves.

The setup of the problem encourages you to think about dividing the board into sub-boards, each with dimensions .

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!

MOG 2018

I’m teaching a lecture course at Technion this coming semester, which is going to limit opportunities for travel somewhat for the next three months or so. It was therefore nice to take advantage of the new ultra-cheap Luton-Tel Aviv connection on Wizzair to make a whistlestop weekend trip to Cambridge. It was lovely to catch up with friends, colleagues and former students, including some people who fit into all those categories.

Among my various mathematical diversions over the weekend, about thirty of us spent most of Sunday marking the 2018 edition of the UK’s Mathematical Olympiad for Girls (MOG). You can find the paper without solutions here, and the paper with official solutions and commentary here.

I have had several blog posts on probabilistic, competitive and educational topics queued up over this summer which has alternated between extreme busyness and lethargy, but this felt like a good opportunity to break the drought and both start and finish a post on the same day!

I’m going to write some thoughts about Question 4, mostly about part a), which I hope might be useful to future students who perhaps find this post while preparing for next year’s edition of the competition. Here’s the statement:

Each of 100 houses in a row are to be painted white or yellow. The residents are quite particular and request that no three neighbouring houses are all the same colour.

a) Explain why no more than 67 houses can be painted yellow.

b) In how many ways may the houses be painted if exactly 67 are painted yellow?

---

Of all the questions on the paper, based on the fraction of the scripts which I saw, I suspect Q4a) is the one for which the most candidates will have scored significantly fewer points than they’d been hoping for.

I think this illustrates some useful guidance for maths competitions, and also illuminates some differences between maths and other subjects which candidates might not have thought about.

Many students wrote that because three houses in a row cannot be yellow, the way to get as many yellow houses as possible is to use a YYWYYW… pattern. Since 100 is not a multiple of three, you have to work out what to do with the final house, after you’ve coloured 99 using the pattern, and sometimes you can colour it yellow, and sometimes you can’t.

Finding and proving results about maxima

Before focusing on the qualities of this argument, it’s worth returning to the question statement. It’s in two parts, and (assuming the answer to the second part isn’t “none“) then the overall goal is to find the maximum number of yellow houses, and to count the number of ways to achieve this maximum number, presumably by characterising them somehow. If the question had just asked us to find the maximum, and had not told us what it is, we would have to:

• Decide on a value M, and show that there is a configuration with exactly M yellows.
• Show that no value >M of yellows is possible.

Note that, apart from deciding on the value of M, which really has to come at the start of the argument, you can do these steps in either order. And if you want to find the number of configurations achieving the maximum, you have to:

• Decide on a value M, and count the number of configurations with exactly M yellows, and check that this is positive!
• Show that no value >M of yellows is possible.

Again, you can perform these steps in either order. If the question is posed like this (with M unknown), you have no idea as you are attempting the paper whether finding the value of M is supposed to be easy or supposed to be a really significant part of the attack on the problem, so starting your solution with a sentence like “I’m going to show that M is the maximum” and continuing by giving your proof an exoskeleton like “First, I’ll show that M+1 (or >M) is impossible. [Do this. Then leave a gap.] Now, I’ll count the number of configurations with M yellows.” This leaves no ambiguity that you are doing the problem in the right way, and for someone reading it, it might be the case that the validity of your argument is almost instantly clear once the rough outline is established.

In any case, on MOG Q4, the question has been split into two parts deliberately, and you have been told what the value of the maximum is. In fact, the order is the opposite to what I’ve proposed in the bullet points above. But this just serves to emphasise that, even when or especially when the maximum is already given, the order of attack is not important. The two bullet points might be completely unrelated mathematical arguments, but they are certainly structurally unrelated.

Structuring your approach to MOG Q4

But, to return to MOG Q4, the first part is asking you to show that 68 or more yellow houses is not possible under the rules. The second part is where you are supposed to establish what all the 67 yellow configurations are, and on this occasion it may turn out that you re-use ideas established in part a) during the enumeration of part b).

Anyway, I’m going to repeat an earlier paragraph. Many students wrote that because three houses in a row cannot be yellow, the way to get as many yellow houses as possible is to use a YYWYYW… pattern. Since 100 is not a multiple of three, you have to work out what to do with the final house, after you’ve coloured 99 using the pattern, and sometimes you can colour it yellow, and sometimes you can’t.

Now that we’ve established some general principles, we can see why some students may have got themselves into knots that weren’t directly relevant to the question.

• The blue comment “sometimes you can colour it yellow, and sometimes you can’t” is just not relevant because at this stage we are trying to show that 68 (or more) is not possible. If at any point it becomes a discussion of whether one class of configurations leads to 66 or 67, this can’t be relevant to showing that 68 is not possible.
• The green sentence “because three houses in a row cannot be yellow, the way to get as many yellow houses as possible is to use a YYWYYW… pattern” is, as written, true, but dangerous. Because it’s not precise. As becomes clear in part b), there are actually lots of ways to get as many yellow houses as possible, and while all of them have this pattern most of the time, it is certainly not the case that you use this pattern for the first 99, and then make a decision about the final house. (Since this only gives one configuration.)
• The fact that 100 is not a multiple of 3 is crucial to the problem. If it had asked about 99 houses, you would have had more room just to work with a breakdown into 33 groups of three houses, and some of the argument would have been simpler. So an argument saying that 100/3 = 66.66…, which we can round up to 67 is not really explaining what’s going on. Of course we have to have a whole number of houses, but why you round up rather than down is all about the rules of colouring.
• Finally, the notion of an ‘iterated maximum’ is a generally erroneous argument. In such an argument, you argue that the maximum way to attack a subproblem is X, and once you have X, clearly the maximal way to finish is Y, so the maximum total is X+Y. This is wrong, because of course it’s possible there might be a non-maximum way X*>X to attack the subproblem, from which you can finish in Y*<<Y, so the total ends up being lower overall.
• In this example, the problem is not that the green statement is an erroneous iterated maximum. It’s just sounds like one. It can easily be made into a non-erroneous argument. But as soon as you start with a pattern, but then consider how to add something onto the end of it, you have essentially fallen into this trap unless you very carefully explain why taking the maximum for the first 99 houses plus the maximum for the final house must give a maximum overall.

Because the condition is a local one (meaning it tells you about rules governing two or three adjacent houses, not a global one affecting all houses in the street), it’s good to use a local argument. In the example:

(YYW)(YYW)…(YY*W)(YW*Y)…(YWY)(Y),

notice that it is not true that in every group of three consecutive houses, two are Yellow. (Look between the *asterisks*.) However, it is true that in every group of three consecutive houses, at most two are Yellow, and so in particular if we split as shown above, there are at most two yellows in all the three-brackets, and at most one at the end, giving at most 67 in total. The fact that the pattern changes from YYW to YWY does not affect this argument.

If you set it up this way, then this gives you a good headstart on part b). You might notice that the pattern can change from YYW to YWY (as in the previous example), but not the other way round. And what about WYY? Can this ever come up? You need to justify both aspects of this, and then clarify how to count the number of places where the pattern could change, having now established that all configurations have this form.

Other comments

The question setters produced a beautiful paper, and it was clear that one of their goals was to use multiple parts sensibly so as to suggest entrance routes into the problem. Many many students successfully used the factorisations discussed in the first parts of Q1, and even those who didn’t succeed seemed mostly to be trying to find differences of squares, rather than prime factors out of nowhere.

This principle applied elsewhere though, and in particular on Q3. I think some students thought Q3a) was supposed to involve three calculations, but in fact it required just giving a combinatorial justification for why the set of objects counted by b can be split into two, where one subset is counted by c and one by d. This argument, which might have been familiar to some through knowledge of Pascal’s triangle, applies equally well at other squares in the box, and also in three dimensions. If you don’t have the gap in the middle of the house, you can immediately apply this argument to Ghastly in part b). But in fact, even with the gap, you can make this work, because you are only really counting across *places you could have been just before in your path*, and the gap means that sometimes this is smaller than it would be without the gap.

There were other ways to do the question, such as counting all paths, and all paths through the gap, but all attempts using a b=c+d+e argument seemed quick and successful.

A couple of other tips to bear in mind on these sorts of questions.

• When you’re deep in a calculation, it’s easy to forget that you started with a problem of some kind, and you should always go back to check that your answer makes sense in the context of the problem! Even if fits the algebra, you should not have any of the following (among many other examples that can emerge after a small conceptual or calculation error):
  • A negative radius for a circle
  • A non-integer number of configurations
  • A probability >1
• You should also check for potential symmetries. While it’s dangerous to use symmetry excessively until you’re sure the situation genuinely is symmetric, it can be your friend in reducing errors. For example, maybe you found the final count in the far corner for Ghastly the ghost to be eg 18+16+12? But the three adjacent-to-far-corner cells are clearly equivalent from the starting point. Any difference between them can only be a feature of the argument you are trying. So they should have the same path count, and probably you made a small error in one of them.
• It’s also worth checking your answers feel roughly right for magnitude. In particular, again on Q3 , if you get a very large answer for part b), you should try to check against other options. How many total paths are there? (Ie, ignoring the gap.) If your answer is much bigger than this, you must have made a small mistake, probably multiplying where you should have been adding. It might well, for example, not feel right if you end up showing that the number of paths is greater than the number of atoms in the universe. This applies equally well for Q4. Note that 67! is an extremely large number, and is larger than 2^100, which is the total number of colourings without observing any of the consecutive rules, let alone the maximum condition.
• As a final point, it was good to see that many candidates were making a bona fide effort to get as many marks as possible. I would say, however, that just writing down a speculative answer is often less helpful than a single sentence explaining what you are trying to do. Pretty much any comment on patterns and a division into cases for Q4 would be useful, even if it wasn’t completely correct, whereas a guess at eg or similar for the final answer is probably less valuable, and draws attention to what you haven’t done, rather than any progress that you really have made.

Anyway, I hope that was interesting at some level to some girls potentially interested in taking MOG or any other challenging mathematics in the future.

BMO2 2018

The second round of the British Mathematical Olympiad was taken yesterday by the 100 or so top scoring eligible participants from the first round, as well as some open entries. Qualifying for BMO2 is worth celebrating in its own right. The goal of the setters is to find the sweet spot of difficult but stimulating for the eligible participants, which ultimately means it’s likely to be the most challenging exam many of the candidates sit while in high school, at least in mathematics.

I know that lots of students view BMO2 as something actively worth preparing for. As with everything, this is a good attitude in moderation. Part of the goal in writing about the questions at such length (and in particular not just presenting direct solutions) is because I think at this level it’s particularly easy to devote more time than needed to preparation, and use it poorly.

All these questions could be solved by able children. In fact, each could be solved by able children in less than an hour. You definitely count as an able child if you qualified or if your teacher allowed you to make an open entry! Others count too naturally. But most candidates won’t in fact solve all the questions, and many won’t solve any. And I think candidates often come up with the wrong reasons why they didn’t solve problems. “I didn’t know the right theorems” is very very rarely the reason. Olympiad problems have standard themes and recurring tropes, but the task is not to look at the problem and decide that it is an example of Olympiad technique #371. The task is actually to have as many ideas as possible, and eliminate the ones that don’t work as quickly as possible.

The best way to realise that an idea works is to solve the problem immediately after having the idea. For the majority of occasions when we’re not lucky enough for that to happen, the second-best way to realise that an idea works is to see that it makes the problem look a bit more like something familiar. Conversely, the best way to realise that an idea doesn’t work is to observe that if it worked it would solve a stronger but false problem too. (Eg Fermat’s Last Theorem *does* have solutions over the reals…) The second-best way to realise that an idea doesn’t work is to have the confidence that you’ve tried it enough and you’ve only made the problem harder, or less familiar.

Both of these second-best ideas do require a bit of experience, but I will try to explain why none of the ideas I needed for various solutions this year required any knowledge beyond the school syllabus, some similarities to recent BMOs, and a small bit of creativity.

As usual, the caveat that these are not really solutions, and certainly not official solutions, but they are close enough to spoil the problems for anyone who hasn’t tried them by themselves already. Of course, the copyright for the problems is held by BMOS, and reproduced here with permission.

Question One

I wrote this question. Perhaps as a focal point of the renaissance of my interest in geometry, or at least my interest in teaching geometry, I have quite a lot to say about the problem, its solutions, its origin story, the use of directed angles, the non-use of coordinate methods and so on. In an ideal world I would write a book about this sort of thing, and perhaps at some point I will.

Question Two

I also wrote this problem, though I feel it’s only fair to show the version I submitted to the BMO committee. All the credit for the magical statement that appears above lies with them. There is a less magical origin story as well, but hopefully with some interesting combinatorial probability, which is postponed until the end of this post.One quick observation is that in my version Joe / Hatter gets to keep going forever. As we shall see, all the business happens in the first N steps, but a priori one doesn’t know that, and in my version it forces you to strategise slightly differently for Neel / Alice. In the competition version, we know Alice is done as soon as she visits a place for a second time, but not in the original. So in the original we only have to consider ‘avoid one place’ rather than the multiple possibilities now of ‘avoid one place’ or ‘visit a place again’.

But I think the best idea is to get Alice to avoid one particular place whenever possible. At all times she has two possible options for where to go next, lets say in the language of the original statement. We lose nothing by assuming , and certainly it would be ridiculous for Joe / Hatter ever to choose . The only time Alice’s strategy doesn’t work is when both of these are congruent to , which implies , and thus we must have . In other words, Alice’s strategy will always work if N is odd.

I think it’s really worth noticing that the previous argument is weak. We certainly did not show that N must be odd for Alice to win. We showed that Alice can avoid a congruence class modulo an odd integer. We didn’t really need that odd integer to be N for this to work. In particular, if N has an odd factor p (say a prime), then the same argument works to show that we can avoid visiting any site with label congruent to 1 modulo p.

It’s actually very slightly more complicated. In the original argument, we didn’t need to use any property of . But obviously here, if modulo p and , then certainly modulo p. So we have to prove instead that Alice can ensure she never ‘visits 1 modulo p for the first time’. Which is fine, by the same argument.

So, we’ve shown that Neel / Alice wins if N is odd, or has an odd factor. The only values that remain are powers of 2. I should confess that I was genuinely a little surprised that Joe / Hatter wins in the power of 2 case. You can find a construction fairly easily for N=2 and N=4, but I suspected that might be a facet of small numbers. Why? Because it still felt we could avoid a particular site. In order for Alice’s strategy to fail, we have to end up exactly opposite the particular site at exactly the time when the next , and so maybe we could try to avoid that second site as well, and so on backwards?

But that turned out to be a good example of something that got very complicated quite quickly with little insight. And, as discussed at the beginning, that’s often a sign in a competition problem that your idea isn’t so good. (Obviously, when composing a problem, that’s no guarantee at all. Sometimes things are true but no good ideas work.) So we want other ideas. Note that for N=4, the sequence (2,1,2) works for Joe / Hatter, because that forces Alice / Neel to visit either (0,2,1,3) or (0,2,3,1). In particular, this strategy gave Alice no control on the first step nor the last step, and the consequence is that we force her to visit the evens first, then transfer to an odd, and then force her to visit the other odd.

We might play around with N=8, or we might proceed directly to a general extension. If we have a Joe / Hatter strategy for N, then by doubling all the s, we have a strategy for 2N which visits all the even sites in the first N steps. But then we can move to an odd site eg by taking . Just as in the N=4 case, it doesn’t matter which odd site we start from, since if we again double all the s, we will visit all the other odd sites. This gives us an inductive construction of a strategy for powers of two. To check it’s understood, the sequence for N=8 is (4,2,4,1,4,2,4).

Although we don’t use it, note that this strategy takes Alice on a tour of sites described by decreasing order of largest power of two dividing the label of the site.

BMO1 2017 – Questions 5 and 6

The first round of the British Mathematical Olympiad was sat yesterday. The questions can be found here and video solutions here. My comments on the first four questions are in the previous post.

Overall, I didn’t think any of the questions on this paper were unusually difficult by the standard of BMO1, but I found everything slightly more time-consuming than typical. I thought Question 5 was a great problem, and I tried lots of things unsuccessfully, first, and so wanted to discuss it in slightly more technical language. For Question 6 I made a decisive mistake, which I’ll explain, and which cost a lot of time. But in general, my point is that the back end of the paper was a little fiddlier than normal, and required longer written solutions, and perhaps many students might have had less time than expected to attack them anyway after details earlier in the paper.

Question Five

As I said before, I thought this question was quite challenging. Not because the solution is particularly exotic or complicated, but because there were so many possible things that might have worked. In my opinion it would not have been out of place at the start of an IMO paper, because it’s perfectly possible to have enough good ideas that eliminating the ones that don’t work takes an hour, or hours. Even though it slightly spoils the flow of the solution, I’m particularly trying to emphasise the tangents that didn’t work, mostly for reassurance to anyone who spent a long time struggling.

I was thinking about this question in terms of a 2Nx2N board, where N is even, and for the given question equal to 100. I spent a while thinking that the bound was 8N-4, corresponding to taking the middle two rows and the middle two columns, but not the 2×2 square which is their intersection. If you think of a comb as a ‘handle’ of 1xN cells, with an extra N/2 alternating cells (say, ‘teeth’) bolted on, then it’s clear this construction works because there’s never space to fit in a handle, let alone the teeth.

I couldn’t prove that this was optimal though. A standard way to prove a given bound K was optimal would be to produce a tiling on the board with K combs, where every cell is included in exactly one comb. But this is clearly not possible in this situation, since the number of cells in a comb (which is 150) does not divide the total number of cells on the board.

Indeed, the general observation that if you take a comb and a copy of the comb rotated by 180, the teeth of the second comb can mesh perfectly with the teeth of the first comb to generate a 3xN unit. I wasted a moderate amount of time pursuing this route.

[Note, it will be obvious in a minute why I’m writing ‘shaded’ instead of ‘coloured’.]

But in motivating the construction, I was merely trying to shade cells so that they intersected every possible 1xN handle, and maybe I could prove that it was optimal for this. In fact, I can’t prove it’s optimal because it isn’t optimal – indeed it’s clear that a handle through one of the middle rows intersects plenty of shaded cells, not just one. However, with this smaller problem in mind, it didn’t take long to come up with an alternative proposal, namely splitting the board into equal quarters, and shading the diagonals of each quarter, as shown.

It seems clear that you can’t fit in a 1xN handle, and any sensible tiling with 1xN handles contains exactly one shaded cell, so this shading (with 4N shaded cells) is optimal. But is it optimal for a comb itself?

Consider a shading which works, so that all combs include a shaded cell. It’s clear that a comb is contained within a 2xN block, and in such a 2xN block, there are four possible combs, as shown.

You need to cover all these combs with some shading somewhere. But if you put the shaded cell on a tooth of comb A, then you haven’t covered comb B. And if you put the shaded cell on the handle of comb A, then you haven’t covered one of comb C and comb D. You can phrase this via a colouring argument too. If you use four colours with period 2×2, as shown

then any comb involves exactly three colours, and so one of them misses out the colour of the shaded cell. (I hope it’s clear what I mean, even with the confusing distinction between ‘shaded’ and ‘coloured’ cells.)

Certainly we have shown that any 2xN block must include at least two shaded cells. And that’s pretty much it. We have a tiling with 2N copies of a 2xN block, and with at least two shaded cells in each, that adds to at least 4N shaded cells overall.

Looking back on the method, we can identify another way to waste time. Tiling a board, eg a chessboard with dominos is a classic motif, which often relies on clever colouring. So it’s perhaps lucky that I didn’t spot this colouring observation earlier. Because the argument described really does use the local properties of how the combs denoted A-D overlap. An attempt at a global argument might start as follows: we can identify 2N combs which don’t use colour 1, and tile this subset of the grid with them, so we need to shade at least 2N cells from colours {2,3,4}. Similarly for sets of colours {1,3,4}, {1,2,4}, and {1,2,3}. But if we reduce the problem to this, then using roughly 2N/3 of each colour fits this global requirement, leading to a bound of 8N/3, which isn’t strong enough. [1]

Question Six

A word of warning. Sometimes it’s useful to generalise in problems. In Q5, I was thinking in terms of N, and the only property of N I used was that it’s even. In Q4, we ignored 2017 and came back to it at the end, using only the fact that it’s odd. By contrast, in Q2, the values did turn out to be important for matching the proof bounds with a construction.

You have to guess whether 300 is important or not here. Let’s see.

I have a natural first question to ask myself about the setup, but some notation is useful. Let be the ordering of the cards. We require that is an integer for every . Maybe the values of these integers will be important, so hold that thought, but for now, replace with the divisibility statement that .

I don’t think it’s worth playing with small examples until I have a better idea whether the answer is 5 or 295. So the natural first question is: “what does it mean to have such that you can’t pick a suitable ?”

It means that there is no integer k in such that , which for now we write as

Consider the congruence class of modulo n. There are either or integers under consideration in this congruence class. If no such k exists, then all of the relevant integers in this congruence class must appear amongst . At this stage, we’re trying to get a feel for when this could happen, so lower bounds on n are most relevant. Therefore, if we get stuck when trying to find , we have

(*)

which is summarised more succinctly as

(**)

[Note, with this sort of bounding argument, I find it helpful to add intermediate steps like (*) in rough. The chance of getting the wrong direction, or the wrong choice of is quite high here. Of course, you don’t need to include the middle step in a final write-up.]

We can check that (**) is false when and true when . Indeed, both versions of (*) are true when .

So we know the minimum failure length is at least 17. But is there a failing sequence of length 17? At a meta-level, it feels like there should be. That was a very natural bounding argument for 17 (which recall corresponds to ), and it’s easy to believe that might be part of an official solution. If we achieve equality throughout the argument, that’s most of the way to a construction as well. It won’t be so easy to turn this argument into a construction for because there won’t be equality anywhere.

We have to hope there is a construction for . What follows is a description of a process to derive (or fail to derive) such a construction. In a solution, one would not need to give this backstory.

Anyway, in such a construction, let describe the congruence class modulo 18 which is exhausted by . I’m going to hope that because then the calculations will be easier since everything’s a multiple of 18. We haven’t yet used the fact that for a problem, we need . We definitely have to use that. There are 16 multiples of 18 (ie relevant integers in the congruence class), so exactly one of the terms so far, say , is not a multiple of 18. But then

which can’t happen. With a bit of experimentation, we find a similar problem making a construction using the other congruence classes with 16 elements, namely .

So we have to tackle a different class. If then our sequence must be

in some order. In fact, let’s add extra notation, so our sequence is

where is a permutation of {0,…,16}. And so we require

(%)

for . But clearly we can lop off that , and could ignore the 18. Can we find a permutation such that

This was where I wasted a long time. I played around with lots of examples and kept getting stuck. Building it up one term at a time, I would typically get stuck around k=9,10. And I had some observations that in all the attempted constructions, the values of were around 8 and 9 too when I got stuck.

I became convinced this subproblem wasn’t possible, and decided that would be enough to show that n=18 wasn’t a possible failure length. I was trying to show the subproblem via a parity argument (how must the s alternate odd/even to ensure all the even partial sums are even) but this wasn’t a problem. Then I came up with a valid argument. We must have

which means must be 128 = 15×8 + 8, ie . But then we also have , which forces $latex\lambda_{16}=8$ also. Which isn’t possible.

If this then hadn’t wasted enough time, I then tried to come up with a construction for n=19, for which there are lots more variables, and took a lot more time, and seemed to be suffering from similar problems, just in a more complicated way. So I became convinced I must have made a mistake, because I was forced down routes that were way too complicated for a 3.5 hour exam. Then I found it…

What did I do wrong? I’ll just say directly. I threw away the 18 after (%). This made the statement stronger. (And in fact false.) Suppose instead I’d thrown away a factor of 9 (or no factors at all, but it’s the residual 2 that’s important). Then I would be trying to solve

And now if you experiment, you will notice that taking seems to work fine. And of course, we can confirm this, using the triangle number formula for the second time in the paper!

This had wasted a lot of time, but once that thought is present, we’re done, because we can go straight back and exhibit the sequence

Then the sum so far is congruent to -1 modulo 18, but we have exhausted all the available integers which would allow the sum of the first 18 terms to be a multiple of 18. This confirms that the answer to the question as stated is 17.

At the start, I said that we should be cautious about generalising. In the end, this was wise advice. We definitely used the fact that 18 was even in the stage I over-reduced the first time. We also used the fact that there was at least one value of with an ‘extra’ member of the congruence class. So I’m pretty sure this proof wouldn’t have worked with 288 = 16×18 cards.

Footnotes

[1] – If shading were a weighted (or continuous or whatever you prefer) property, ie that each cell has a quantity of shading given by a non-negative real number, and we merely demand that the total shading per comb is at least one, then the bound 8N/3 is in fact correct for the total shading. We could look at a 2xN block, and give 1/3 shading to one cell of each colour in the block. Alternatively, we could be very straightforward and apply 2/3N shading to every cell in the grid. The fact that shading has to be (in this language) zero or one, imposes meaningful extra constraints which involve the shape of the comb.

BMO1 2017 – Questions 1-4

The first round of the British Mathematical Olympiad was sat yesterday. The questions can be found here. I recorded some thoughts on the questions while I was in Cyprus, hence the nice Mediterranean sunset above. I hope this might be useful to current or future contestants, as a supplement to the concise official solutions available. It goes without saying that while these commentaries may be interesting at a general level, they will be much more educational to students who have at least digested and played around with the questions, so consider trying the paper first. Video solutions are available here. These have more in common with this blog post than the official solutions, though inevitably some of the methods are slightly different, and the written word has some merits and demerits over the spoken word for clarity and brevity.

The copyright for these questions lies with BMOS, and are reproduced here with permission. Any errors or omissions are obviously my own.

I found the paper overall quite a bit harder than in recent years, or at least harder to finish quickly. I’ve therefore postponed discussion of the final two problems to a second post, to follow shortly.

Question One

A recurring theme of Q1 from BMO1 in recent years has been: “it’s possible to do this problem by a long, and extremely careful direct calculation, but additional insight into the setup makes life substantially easier.”

This is the best example yet. It really is possible to evaluate Helen’s sum and Phil’s sum, and compare them directly. But it’s easy to make a mistake in recording all the remainders when the divisor is small, and it’s easy to make a mistake in summation when the divisor is large, and so it really is better to have a think for alternative approaches. Making a mistake in a very calculation-heavy approach is generally penalised heavily. And this makes sense intellectually, since the only way for someone to fix an erroneous calculation is to repeat it themselves, whereas small conceptual or calculation errors in a less onerous solution are more easily isolated and fixed by a reader. Of course, it also makes sense to discourage such attempts, which aren’t really related to enriching mathematics, which is the whole point of the exercise!

Considering small divisors (or even smaller versions of 365 and 366) is sometimes helpful, but here I think a ‘typical’ divisor is more useful. But first, some notation will make any informal observation much easier to turn into a formal statement. Corresponding to Helen and Phil, let h(n) be the remainder when n is divided by 365, and p(n) the remainder when n is divided by 366. I would urge students to avoid the use of ‘mod’ in this question, partly because working modulo many different bases is annoying notationally, partly because the sum is not taken modulo anything, and partly because the temptation to use mod incorrectly as an operator is huge here [1].

Anyway, a typical value might be n=68, and we observe that 68 x 5 + 25 = 365, and so h(68)=25 and p(68)=26. Indeed, for most values of n, we will have p(n)=h(n)+1. This is useful because

and now we know that most of the bracketed terms are equal to one. We just need to handle the rest. The only time it doesn’t hold that p(n)=h(n)+1 is when 366 is actually a multiple of n. In this case, p(n)=0 and h(n)=n-1. We know that 366 = 2 x 3 x 61, and so its divisors are 1, 2, 3, 6, 61, 122, 183.

Then, in the big expression above, seven of the 365 bracketed terms are not equal to 1. So 358 of them are equal to one. The remaining ones are equal to 0, -1, -2, -5, -60, -121, -182 respectively. There are shortcuts to calculate the sum of these, but it’s probably safer to do it by hand, obtaining -371. Overall, since p(366)=0, we have

So, possibly counter-intuitively, Helen has the larger sum, with difference 13, and we didn’t have to do a giant calculation…

Question Two

Suppose each person chooses which days to go swimming ‘at random’, without worrying about how to define this. Is this likely to generate a maximum or minimum value of n? I hope it’s intuitively clear that this probably won’t generate an extreme value. By picking at random we are throwing away lots of opportunity to force valuable overlaps or non-overlaps. In other words, we should start thinking about ways to set up the swimming itinerary with lots of symmetry and structure, and probably we’ll eventually get a maximum or a minimum. At a more general level, with a problem like this, one can start playing around with proof methods immediately, or one can start by constructing lots of symmetric and extreme-looking examples, and see what happens. I favour the latter approach, at least initially. You have to trust that at least one of the extreme examples will be guess-able.

The most obvious extreme example is that everyone swims on the first 75 days, and no-one swims on the final 25 days. This leads to n=75. But we’re clearly ‘wasting’ opportunities in both directions, because there are never exactly five people swimming. I tried a few more things, and found myself simultaneously attacking maximum and minimum, which is clearly bad, so focused on minimum. Just as a starting point, let’s aim for something small, say n=4. The obstacle is that if you demand at most four swimmers on 96 days, then even with six swimmers on the remaining four days, you don’t end up with enough swimming having taken place!

Maybe you move straight from this observation to a proof, or maybe you move straight to a construction. Either way, I think it’s worth saying that the proof and the construction come together. My construction is that everyone swims on the first 25 days, then on days 26-50 everyone except A and B swim, on days 51-75 everyone except C and D swim, and on days 76-100 everyone except E and F swim. This exactly adds up. And if you went for the proof first, you might have argued that the total number of swim days is 6×75 = 450, but is at most 4n + 6(100-n). This leads immediately to , and I just gave the construction. Note that if you came from this proof first, you can find the construction because your proof shows that to be exact you need 25 days with six swimmers, and 75 days with four swimmers, and it’s natural to try to make this split evenly. Anyway, this clears up the minimum.

[Less experienced contestants might wonder why I was worried about generating a construction despite having a proof. Remember we are trying to find the minimum. I could equally have a proof for which would be totally totally valid. But this wouldn’t show that the minimum was n=10, because that isn’t in fact possible (as we’ve seen), hence it’s the construction that confirms that n=25 is the true minimum.]

It’s tempting to go back to the drawing board for the maximum, but it’s always worth checking whether you can directly adjust the proof you’ve already given. And here you can! We argued that

to prove the minimum. But equally, we know that on the n days we have at least five swimmers, and on the remaining days, we have between zero and four swimmers, so

(*)

which gives . If we have a construction that attains this bound then we are done. Why have I phrased (*) with the slightly childish multiple of zero? Because it’s a reminder that for a construction to attain this bound, we really do need the 90 days to have exactly five swimmers, and the remaining ten days to have no swimmers. So it’s clear what to do. Split the first 90 days into five groups of 15 days. One swimmer skips each group. No-one swims in the final ten days, perhaps because of a jellyfish infestation. So we’re done, and .

At a general level, it’s worth noting that in the story presented, we found an example for the minimum which we turned into a proof, and then a proof for the maximum, which we then analysed to produce a construction.

Note that similar bounding arguments would apply if we fiddled with the numbers 5, 75 and 100. But constructions matching the bounds might not then be possible because the splits wouldn’t work so nicely. This would make everything more complicated, but probably not more interesting.

Question Three

It’s understandable that lots of students attempting this paper might feel ill-at-ease with conventional Euclidean geometry problems. A good first rule of thumb here, as in many settings, is “don’t panic!”, and a more specific second rule of thumb is “even if you think you can calculate, try to find geometric insight first.”

Here, it really does look like you can calculate. A configuration based on a given isosceles triangle and a length condition and a perpendicular line is open to several coordinate approaches, and certainly some sensible trigonometry. It’s also very open to organised labelling of the diagram. You have three equal lengths, and a right-angle, as shown.

The key step is this. Drop the perpendicular from A to BC, and call its foot D. That alone really is the key step, as it reduces both parts of the question to an easy comparison. It’s clear that the line AD splits the triangle into two congruent parts, and thus equal areas and perimeters. So it is enough to show that triangle BMN has the same area as triangle ABD, and that their outer-perimeters (ie the part of its perimeter which is also the perimeter of ABC) are the same.

But they’re congruent, so both of these statements are true, and the problem is solved.

My solution could be as short as two or three lines, so for the purposes of this post all that remains is to justify why you might think of the key step. Here are a few possible entry routes:

• You might notice that line AD induces the required property for triangle ABD.
• You might try to find a triangle congruent to AMN, and come up with D that way.
• There’s already a perpendicular in the question so experimenting with another one is natural, especially since the perpendicular from A has straightforward properties.
• AMN is a right angle, and so constructing D gives a cyclic quadrilateral. We didn’t use that directly in the proof above, but constructing cyclic quadrilaterals is usually a good idea.
• If you were trying a calculation approach, you probably introduced the length AD, or at least the midpoint D as an intermediate step.

On the video, Mary Teresa proposes a number of elegant synthetic solutions with a few more steps. You might find it a useful exercise to try to come up with some motivating reasons like the bullet points above to justify her suggestion to reflect A in M as a first step.

Question Four

I wasn’t paying enough attention initially, and I calculated . This made life much much more complicated. As with IMO 2017 Q1, if trying to deduce general behaviour from small examples, it’s essential to calculate the small examples correctly!

Once you engage your brain properly, you find that , and of course is not allowed, since it must be positive. So , and a similar calculation suggests . It’s clear that the set of values for depends only on , so if you take , then you’re back to the situation you started with at the beginning. If you choose to continue the exploration with , you will find , at which point you must be triggered by the possibility that triangle numbers play a role here.

As so often with a play-around with small values, you need to turn a useful observation into a concrete statement, which could then be applied to the problem statement. It looks like in any legal sequence, every term will be a triangle number, so we only need to clarify which triangle number. An example of a suitable statement might be:

Claim: If , the k-th triangle number, then .

There are three stages. 1) Checking the claim is true; 2) checking the claim is maximally relevant; 3) proving it. In this case, proving it is the easiest bit. It’s a quick exercise, and I’m omitting it. Of course, we can’t prove any statement which isn’t true, and here we need to make some quick adjustment to account for the case k=1, for which we are forced to take .

The second stage really concerns the question “but what if ?” While there are deductions one could make, the key is that if is a triangle number, the claim we’ve just made shows that is always a triangle number, so this question is irrelevant. Indeed the claim further shows that , and also that for some odd value of k. To be fully rigorous you should probably describe a sequence which attains each odd value of k, but this is really an exercise in notation [2], and it’s very obvious they are all attainable.

In any case, the set of possible values is , which has size 1009.

Final two questions

These are discussed in a subsequent post.

Footnotes

[1] – mod n is not an operator, meaning you shouldn’t think of it as ‘sending integers to other integers’, or ‘taking any integer, to an integer in {0,1,…,n-1}’. Statements like 19 mod 5 = 4 are useful at the very start of an introduction to modular arithmetic, but why choose 4? Sometimes it’s more useful to consider -1 instead, and we want statements like modulo p to make sense even when . 19 = 4 modulo 5 doesn’t place any greater emphasis on the 4 than the 19. This makes it more like a conventional equals sign, which is of course appropriate.

[2] – Taking for $1\le n\le k$, and thereafter if k is odd, and $a_n=T_{k+1}$ if k is even will certainly work, as will many other examples, some perhaps easier to describe than this one, though make sure you don’t accidentally try to use !

BMO2 2017

The second round of the British Mathematical Olympiad was taken yesterday by about 100 invited participants, and about the same number of open entries. To qualify at all for this stage is worth celebrating. For the majority of the contestants, this might be the hardest exam they have ever sat, indeed relative to current age and experience it might well be the hardest exam they ever sit. And so I thought it was particularly worth writing about this year’s set of questions. Because at least in my opinion, the gap between finding every question very intimidating, and solving two or three is smaller, and more down to mindset, than one might suspect.

A key over-arching point at this kind of competition is the following: the questions have been carefully chosen, and carefully checked, to make sure they can be solved, checked and written up by school students in an hour. That’s not to say that many, or indeed any, will take that little time, but in principle it’s possible. That’s also not to say that there aren’t valid but more complicated routes to solutions, but in general people often spend a lot more time writing than they should, and a bit less time thinking. Small insights along the lines of “what’s really going on here?” often get you a lot further into the problem than complicated substitutions or lengthy calculations at this level.

So if some of the arguments below feel slick, then I guess that’s intentional. When I received the paper and had a glance in my office, I was only looking for slick observations, partly because I didn’t have time for detailed analysis, but also because I was confident that there were slick observations to be made, and I felt it was just my task to find them.

Anyway, these are the questions: (note that the copyright to these is held by BMOS – reproduced here with permission.)

Question One

I immediately tried the example where the perpendicular sides are parallel to the coordinate axes, and found that I could generate all multiples of 3 in this way. This seemed a plausible candidate for an answer, so I started trying to find a proof. I observed that if you have lots of integer points on one of the equal sides, you have lots of integer points on the corresponding side, and these exactly match up, and then you also have lots of integer points on the hypotenuse too. In my first example, these exactly matched up too, so I became confident I was right.

Then I tried another example ( (0,0), (1,1), (-1,1) ) which has four integer points, and could easily be generalised to give any multiple of four as the number of integer points. But I was convinced that this matching up approach had to be the right thing, and so I continued, trusting that I’d see where this alternate option came in during the proof.

Good setup makes life easy. The apex of the isosceles triangle might as well be at the origin, and then your other vertices can be or similar. Since integral points are preserved under the rotation which takes equal side to the other, the example I had does generalise, but we really need to start enumerating. The number of integer points on the side from (0,0) to (m,n) is G+1, where G is the greatest common divisor of m and n. But thinking about the hypotenuse as a vector (if you prefer, translate it so one vertex is at the origin), the number of integral points on this line segment must be .

To me, this felt highly promising, because this is a classic trope in olympiad problem-setting. Even without this experience, we know that this gcd is equal to G if m and n have different parities (ie one odd, one even) and equal to 2G if m and n have the same parity.

So we’re done. Being careful not to double-count the vertices, we have 3G integral points if m and n have opposite parities, and 4G integral points if m and n have the same parity, which exactly fits the pair of examples I had. But remember that we already had a pair of constructions, so (after adjusting the hypothesis to allow the second example!) all we had to prove was that the number of integral points is divisible by at least one of 3 and 4. And we’ve just done that. Counting how many integers less than 2017 have this property can be done easily, checking that we don’t double-count multiples of 12, and that we don’t accidentally include or fail to include zero as appropriate, which would be an annoying way to perhaps lose a mark after totally finishing the real content of the problem.

Question Two

(Keen observers will note that this problem first appeared on the shortlist for IMO 2006 in Slovenia.)

As n increases, obviously decreases, but the bracketed expression increases. Which of these effects is more substantial? Well is the number of multiples of k which are at most n, and so as a function of n, this increases precisely when n is a multiple of k. So, we expect the bracketed expression to increase substantially when n has lots of factors, and to increase less substantially when n has few factors. An extreme case of the former might be when n is a large factorial, and certainly the extreme case of the latter is n a prime.

It felt easier to test a calculation on the prime case first, even though this was more likely to lead to an answer for b). When n moves from p-1 to p, the bracketed expression goes up by exactly two, as the first floor increases, and there is a new final term. So, we start with a fraction, and then increase the numerator by two and the denominator by one. Provided the fraction was initially greater than two, it stays greater than two, but decreases. This is the case here (for reasons we’ll come back to shortly), and so we’ve done part b). The answer is yes.

Then I tried to do the calculation when n was a large factorial, and I found I really needed to know the approximate value of the bracketed expression, at least for this value of n. And I do know that when n is large, the bracketed expression should be approximately , with a further correction of size at most n to account for the floor functions, but I wasn’t sure whether I was allowed to know that.

But surely you don’t need to engage with exactly how large the correction due to the floors is in various cases? This seemed potentially interesting (we are after all just counting factors), but also way too complicated. An even softer version of what I’ve just said is that the harmonic function (the sum of the first n reciprocals) diverges faster than n. So in fact we have all the ingredients we need. The bracketed expression grows faster than n, (you might want to formalise this by dividing by n before analysing the floors) and so the s get arbitrarily large. Therefore, there must certainly be an infinite number of points of increase.

Remark: a few people have commented to me that part a) can be done easily by treating the case , possibly after some combinatorial rewriting of the bracketed expression. I agree that this works fine. Possibly this is one of the best examples of the difference between doing a problem leisurely as a postgraduate, and actually under exam pressure as a teenager. Thinking about the softest possible properties of a sequence (roughly how quickly does it grow, in this case) is a natural first thing to do in all circumstances, especially if you are both lazy and used to talking about asymptotics, and certainly if you don’t have paper.

Question 3

I only drew a very rough diagram for this question, and it caused no problems whatsoever, because there aren’t really that many points, and it’s fairly easy to remember what their properties are. Even in the most crude diagram, we see R and S lie on AC and AD respectively, and so the conclusion about parallel lines is really about similarity of triangles ARS and ACD. This will follow either from some equal angles, or by comparing ratios of lengths.

Since angle bisectors by definition involve equal angles, the first attack point seems promising. But actually the ratios of lengths is better, provided we know the angle bisector theorem, which is literally about ratios of lengths in the angle bisector diagram. Indeed

     (1)

and so it only remains to show that these quantities are in fact all equal. Note that there’s some anti-symmetry here – none of these expressions use B at all! We could for example note that AP/PD = BP/PC, from which

     (2)

and correspondingly for R and Q, and work with symmetric expressions. I was pretty sure that there was a fairly well-known result that in a cyclic quadrilateral, where P is the intersection of the diagonals

     (3)

(I was initially wondering whether there was a square on the LHS, but an example diagram makes the given expression look correct.)

There will be a corresponding result for Q, and then we would be almost done by decomposing (2) slightly differently, and once we’d proved (3) of course. But doing this will turn out to be much longer than necessary. The important message from (3) is that in a very simple diagram (only five points), we have a result which is true, but which is not just similar triangles. There are two pairs of similar triangles in the diagram, but they aren’t in the right places to get this result. What you do have is some pairs of triangles with one pair of equal angles, and one pair of complementary angles (that is, in one, and in the other). This is a glaring invitation to use the sine rule, since the sines of complementary angles are equal.

But, this is also the easiest way to prove the angle bisector theorem. So maybe we should just try this approach directly on the original ratio-of-lengths statement that we decided at (1) was enough, namely . And actually it drops out rapidly. Using natural but informal language referencing my diagram

and we are done. But whatever your motivation for moving to the sine rule, this is crucial. Unless you construct quite a few extra cyclic quadrilaterals, doing this with similar triangles and circle theorems alone is going to be challenging.

Remark: If you haven’t seen the angle bisector theorem before, that’s fine. Both equalities in (1) are a direct statement of the theorem. It’s not an intimidating statement, and it would be a good exercise to prove either of these statements in (1). Some of the methods just described will be useful here too!

Question 4

You might as well start by playing around with methodical strategies. My first try involved testing 000, 111, … , 999. After this, you know which integers appear as digits. Note that at this stage, it’s not the same as the original game with only three digits, because we can test using digits which we know are wrong, so that answers are less ambiguous. If the three digits are different, we can identify the first digit in two tests, and then the second in a further test, and so identify the third by elimination. If only two integers appear as digits, we identify each digit separately, again in three tests overall. If only one integer appears, then we are already done. So this is thirteen tests, and I was fairly convinced that this wasn’t optimal, partly because it felt like testing 999 was a waste. But even with lots of case tries I couldn’t do better. So I figured I’d try to prove some bound, and see where I got.

A crucial observation is the following: when you run a test, the outcome eliminates some possibilities. One of the outcomes eliminates at least half the codes, and the other outcome eliminates at most half the codes. So, imagining you get unlucky every time, after k tests, you might have at least possible codes remaining. From this, we know that we need at least 9 tests.

For this bound to be tight, each test really does need to split the options roughly in two. But this certainly isn’t the case for the first test, which splits the options into 729 (no digit agreements) and 271 (at least one agreement). Suppose the first test reduces it to 729 options, then by the same argument as above, we still need 9 tests. We now know we need at least 10 tests, and so the original guess of 13 is starting to come back into play.

We now have to make a meta-mathematical decision about what to do next. We could look at how many options might be left after the second test, which has quite a large number of cases (depending on how much overlap there is between the first test number and the second test number). It’s probably going to be less than 512 in at least one of the cases, so this won’t get us to a bound of 11 unless we then consider the third test too. This feels like a poor route to take for now, as the tree of options has branching at rate 3 (or 4 if you count obviously silly things) per turn, so gets unwieldy quickly. Another thought is that this power of two argument is strong when the set of remaining options is small, so it’s easier for a test to split the field roughly in two.

Now go back to our proposed original strategy. When does the strategy work faster than planned? It works faster than planned if we find all the digits early (eg if they are all 6 or less). So the worst case scenario is if we find the correct set of digits fairly late. But the fact that we were choosing numbers of the form aaa is irrelevant, as the digits are independent (consider adding 3 to the middle digit modulo 10 at all times in any strategy – it still works!).

This is key. For , after k tests, it is possible that we fail every test, which means that at least options remain for each digit, and so at least options in total. [(*) Note that it might actually be even worse if eg we get a ‘close’ on exactly one test, but we are aiming for a lower bound, so at this stage considering an outcome sequence which is tractable is more important than getting the absolute worst case outcome sequence if it’s more complicated.] Bearing in mind that I’d already tried finishing from the case of reduction to three possibilities, and I’d tried hard to sneak through in one fewer test, and failed, it seemed sensible to try k=7.

After 7 tests, we have at least 27 options remaining, which by the powers-of-two argument requires at least 5 further tests to separate. So 12 in total, which is annoying, because now I need to decide whether this is really the answer and come up a better construction, or enhance the proof.

Clearly though, before aiming for either of these things, I should actually try some other values of k, since this takes basically no time at all. And k=6 leaves 64 options, from which the power of two argument is tight; and k=5 leaves 125, which is less tight. So attacking k=6 is clearly best. We just need to check that the 7th move can’t split the options exactly into 32 + 32. Note that in the example, where we try previously unseen digits in every position, we split into 27 + 37 [think about (*) again now!]. Obviously, if we have more than four options left for any digit, we are done as then we have strictly more than 4x4x4=64 options. So it remains to check the counts if we try previously unseen digits in zero, one or two positions. Zero is silly (gives no information), and one and two can be calculated, and don’t give 32 + 32.

So this is a slightly fiddly end to the solution, and relies upon having good control over what you’re trying to do, and what tools you currently have. The trick to solving this is resisting calculations and case divisions that are very complicated. In the argument I’ve proposed, the only real case division is right at the end, by which point we are just doing an enumeration in a handful of cases, which is not really that bad.

BMO1 2016 – the non-geometry

Here’s a link to yesterday’s BMO1 paper, and the video solutions for all the problems. I gave the video solution to the geometric Q5, and discuss aspects of this at some length in the previous post.

In these videos, for obvious educational reasons, there’s a requirement to avoid referencing theory and ideas that aren’t standard on the school curriculum or relatively obvious directly from first principles. Here, I’ve written down some of my own thoughts on the other problems in a way that might add further value for those students who are already have some experience at olympiads and these types of problems. In particular, on problems you can do, it’s worth asking what you can learn from how you did them that might be applicable generally, and obviously for some of the harder problems, it’s worth knowing about solutions that do use a little bit of theory. Anyway, I hope it’s of interest to someone.

Obviously we aren’t going to write out the whole list, but there’s a trade-off in time between coming up with neat ideas involving symmetry, and just listing and counting things. Any idea is going to formalise somehow the intuitive statement ‘roughly half the digits are odd’. The neat ideas involve formalising the statement ‘if we add leading zeros, then roughly half the digits are odd’. The level of roughness required is less in the first statement than the second statement.

Then there’s the trade-off. Trying to come up with the perfect general statement that is useful and true might lead to something like the following:

‘If we write the numbers from 0000 to N, with leading zeros, and all digits of N+1 are even, then half the total digits, ie 2N of them, are odd.’

This is false, and maybe the first three such things you try along these lines are also false. What you really want to do is control the numbers from 0000 to 1999, for which an argument by matching is clear, and gives you 2000 x 4 / 2 = 4000 odd digits. You can exploit the symmetry by matching k with 1999-k, or do it directly first with the units, then with the tens and so on.

The rest (that is, 2000 to 2016) can be treated by listing and counting. Of course, the question wants an actual answer, so we should be wary of getting it wrong by plus or minus one in some step. A classic error of this kind is that the number of integers between 2000 and 2016 inclusive is 17, not 16. I don’t know why the memory is so vivid, but I recall being upset in Year 2 about erring on a problem of this kind involving fences and fenceposts.

As with so many new types of equation, the recipe is to reduce to a type of equation you already know how to solve. Here, because {x} has a different form on different ranges, it makes sense to consider the three ranges

as for each of these ranges, we can rewrite in terms of standard functions without this bracket notation. On each range we can solve the corresponding equation. We then have to check that each solution does actually lie in the appropriate range, and in two cases it does, and in one case it doesn’t.

Adding an appropriately-chosen value to each side allows you to factorise the quadratics. This might be very useful. But is it an invitation to do number theory and look at coprime factors and so on, or is a softer approach more helpful?

The general idea is that the set of values taken by any quadratic sequence with integer coefficients and leading coefficient one looks from a distance like the set of squares, or the set , which you might think of as ‘half-squares’ or ‘double triangle numbers’ as you wish. And by, ‘from a distance’ I mean ‘up to an additive constant’. If you care about limiting behaviour, then of course this additive constant might well not matter, but if you care about all solutions, you probably do care. To see why this holds, note that

so indeed up to an additive constant, the quadratic on the LHS gives the squares, and similarly

and so on. To solve the equation , over the integers, one can factorise, but another approach is to argue that the distance between adjacent squares is much more than 6 in the majority of cases, which leaves only a handful of candidates for n and m to check.

The same applies at this question. Adding on 9 gives

which is of course the same as

Now, since we now that adjacent squares and ‘half-squares’ are more than one apart in all but a couple of cases, we know why there should only be a small number of solutions. I would call a method of this kind square-sandwiching, but I don’t see much evidence from Google that this term is generally used, except on this blog.

Of course, we have to be formal in an actual solution, and the easiest way to achieve this is to sandwich between adjacent squares and , since it is very much clear-cut that the only squares which differ by one are zero and one itself.

I really don’t have much to say about this. It’s not on the school curriculum so the official solutions are not allowed to say this, but you have to use that all integers except those which are 2 modulo 4 can be written as a difference of two squares. The easiest way to show this is by explicitly writing down the appropriate squares, treating the cases of odds and multiples of four separately.

So you lose if after your turn the running total is 2 modulo 4. At this point, the combinatorics isn’t too hard, though as in Q1 one has to be mindful that making an odd number of small mistakes will lead to the wrong answer! As in all such problems, it’s best to try and give a concrete strategy for Naomi. And it’s best if there’s something inherent in the strategy which makes it clear that it’s actually possible to implement. (Eg, if you claim she should choose a particular number, ideally it’s obvious that number is available to choose.)

One strategy might be: Naomi starts by choosing a multiple of four. Then there are an even number of multiples of four, so Naomi’s strategy is:

• whenever Tom chooses a multiple of four, Naomi may choose another multiple of four;
• whenever Tom chooses a number which is one (respectively three) modulo 4, Naomi may choose another which is three (respectively one) modulo 4.

Note that Naomi may always choose another multiple of four precisely because we’ve also specified the second condition. If sometimes Tom chooses an odd number and Naomi responds with a multiple of four out an idle and illogical sense of caprice, then the first bullet point would not be true. One can avoid this problem by being more specific about exactly what the algorithm is, though there’s a danger that statements like ‘whenever Tom chooses k, Naomi should choose 100-k’ can introduce problems about avoiding the case k=50.

I started this at the train station in Balatonfured with no paper and so I decided to focus on the case of just m, m+1 and n, n+2. This wasn’t a good idea in my opinion because it was awkward but guessable, and so didn’t give too much insight into actual methods. Also, it didn’t feel like inducting on the size of the sequences in question was likely to be successful.

If we know about the Chinese Remainder Theorem, we should know that we definitely want to use it here in some form. Here are some clearly-written notes about CRT with exercises and hard problems which a) I think are good; b) cite this blog in the abstract. (I make no comment on correlation or causality between a) and b)…)

CRT is about solutions to sets of congruence equations modulo various bases. There are two aspects to this , and it feels to me like a theorem where students often remember one aspect, and forget the other one, in some order. Firstly, the theorem says that subject to conditions on the values modulo any non-coprime bases, there exist solutions. In many constructive problems, especially when the congruences are not explicit, this is useful enough by itself.

But secondly, the theorem tells us what all the solutions are. There are two stages to this: finding the smallest solution, then finding all the solutions. Three comments: 1) the second of these is easy – we just add on all multiples of the LCM of the bases; 2) we don’t need to find the smallest solution – any solution will do; 3) if you understand CRT, you might well comment that the previous two comments are essentially the same. Anyway, finding the smallest solution, or any solution is often hard. When you give students an exercise sheet on CRT, finding an integer which is 3 mod 5, 1 mod 7 and 12 mod 13 is the hard part. Even if you’re given the recipe for the algorithm, it’s the kind of computation that’s more appealing if you are an actual computer.

Ok, so returning to this problem, the key step is to phrase everything in a way which makes the application of CRT easy. We observe that taking n=2m satisfies the statement – the only problem of course is that 2m is not odd. But CRT then tells us what all solutions for n are, and it’s clear that 2m is the smallest, so we only need to add on the LCM (which is odd) to obtain the smallest odd solution.