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 BP=EP or, alternatively, \angle BEP=\angle PBE. 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 \angle BED=\angle BAD = 90-\hat{B}, hence \angle AEB=\hat{B},\,\angle EBA=\hat{C}. 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 \angle BEC=180-\hat{B} and \angle CBP=90-\hat{B}. But BPC is isosceles so \angle BPC=2\hat{B}. 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 \hat{B}. 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 n^2 sub-boards, each with dimensions n\times n. Continue reading

Advertisements

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!

Continue reading

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 \binom{67}{33} 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.

Balkan MO 2018 – UK Team Blog

The Balkan Mathematical Olympiad is a competition for secondary school students organised annually by eleven countries in Eastern Europe on a rotating basis. The 2018 edition was held near Belgrade, Serbia over the period 7-12 May 2018. The UK was grateful to be invited as a guest nation.

Our participation is arranged by the UK Maths Trust, as part of a broader programme to introduce the country’s most enthusiastic young mathematicians to regular problem-solving, challenging mathematics, and several annual opportunities to participate in competitions. For the Balkan MO, we have a self-imposed rule that students may attend at most once, so that as many as possible might enjoy the experience of an international competition.

The non-geometry problems of the contest are discussed at length in this blog post, and the geometry problem which appeared as Q1 is discussed at considerable length, along with some background on harmonic ranges, in this blog post. A full report encapsulating all these aspects, is available here.

This post covers the non-mathematical aspects of the contest, which was enjoyed by all the UK students.

Problem selection

The programme of this competition is a scaled down version of the IMO. The leaders gather in suburban Belgrade on Monday night to select four problems from a shortlist compiled by the organisers. To recreate the students’ experience, it makes sense to start by trying these without reference to solutions. Some of the questions are UK submissions, so I can briefly astonish my colleague Vesna with almost instant fluency, before admitting that I wrote or edited the corresponding solutions.

Making the choice occupies Tuesday morning. As always, it feels slightly like a shot in the dark, as one night is not really sufficient to get a feeling for twenty problems, especially the hardest ones. In the end, there was clearly a unique good hard problem, but unfortunately it had to be rejected because it was too similar to a recent problem from a well-known source. Some of us have been investing considerable energy in finding natural Euclidean arguments to the geometry problem chosen as Q3, but once Greek leader Silouanos outlines the role of harmonic ranges, it is hurriedly moved to Q1. I think the resulting set of four questions are attractive, but with a rather compressed difficulty range, and certainly not in the right order for the UK students, whose geometric toolkits probably don’t yet include the ideas needed to access the `easy’ solutions.

In any case, it’s interesting to discuss with the leaders from some of the eleven Balkan full member countries. Our opinions differ concerning which styles of problem give an advantage to extensively-trained problems. I personally feel that Q2 and Q3 are accessible even to students (or adults!) without much mathematical background, whereas here is a prevailing view that no problem with combinatorial flavour is ever ‘easy’. By contrast, many of the ideas required for a short solution to either Q1 or Q4 might be considered obscure even by serious olympiad enthusiasts, though feature on the school curriculum, at least for the most able children, in many of these countries.

We have to finalise the wording of the problems, and there are many many proposed improvements to Q2 and Q3. The final problem, unsurprisingly, requires considerably less attention. That’s our job done for the British delegation, while the other leaders get to work producing versions in their own languages, including Bosnian and Serbian, the (non-)differences between which can happily fill one dinner’s worth of interesting conversation.

The contest

On Wednesday morning, we are transferred to the contestant site, in the rolling hills just outside the south-east city limits of Belgrade. An extremely brief opening ceremony takes place in a room slightly smaller than the number of people attending the competition. The UK team look happy enough perched on a table. Two local violinists play Mozart with a gypsy flourish, before Teodor von Burg, a former Serbian olympiad star and graduate of Exeter College, Oxford, speaks briefly about the usual cliches of such speeches, and the additive paradox of wishing everyone good luck before a competition, then ends rapidly to avoid indulging such cliches himself.

After the contestants fan out to various exam rooms spread through the hotel, the contest begins and they are allowed to ask queries about the problems for 30 minutes. Many many students ask ‘what does exactly the same route mean?’ and ‘what if Alice and Bob play forever?’, but some variety is provided when Aron shares his detailed dilemma about the exact usage of carbon paper. (FAO future UK students: this is not to become a habit, please…)

After Monday’s 2am start, I am overdue a nap. There has been some room-swapping, and mine is reserved for ‘Professor Mr Jill Parker’. Whomever the bed truly belongs to, I leave it in time to meet the team outside the exam with Jill and Vesna. As we’d predicted, many are enthusiastic about Q2 and Q3, but have been frustrated by the geometry. Tom crowd-sources an investigation to recover a result about the incentre claimed by Alex, who perhaps now regrets, in his rush to move to other questions, not offering more of such details himself. No-one claims anything beyond observations in the number theory, so we suggest they keep thinking about it through the afternoon.

A brief excursion

Agnijo and Nathan had done their research on Belgrade, and had asked about the possibility of visiting the Nikola Tesla museum. The team have a guide, Sandra, a maths undergraduate, and I’m extremely impressed that she and some of her colleagues are able to organise a visit downtown and guided tour of this museum at essentially no notice for them, along with Italy, Bosnia and Azerbaijan. Vesna and I diverge to make a start on marking in a cafe, rejoining in time for the museum, where Giles apparently learns what ‘Azerbaijan’ is, and we all learn about Tesla’s extraordinary life story, and get to see the original Tesla coil (briefly) in action. Agnijo and Tom have been primed with fluorescent tubes, which do indeed glow as lightning surges between the century-old coil and its crowning sphere. Other exhibits, including highlights from Tesla’s wardrobe (pre-dating \emph{geek chic}, it would seem), and an imitation ticket from Belgrade to New York, are perhaps less fascinating.

But the roar of 10^6 Volts is still in our ears as we stroll across the city centre, where Alex confidently identifies several churches as the orthodox cathedral they’d visited earlier, and eyes are drawn to the faded but strident protest banners outside the parliament. We choose a restaurant in bohemian Skadarska street, where prices are low, and availability of protein and itinerant accordion players is high. The team are trying to be polite about their hotel’s food, but I sense this variation is welcome. Giles pokes gingerly at a deep-fried pork slab, which erupts with multiple cheeses. The ‘Serbian sword‘ could be retitled ‘as many meat items on a stick as possible (plus 1/8 of a pepper)’.

We return to Avala feeling sleepily satisfied. Tom and Agnijo discuss the GCSE question ‘prove using algebra that the product of two odd numbers is odd’, and whether you can or should prove it without algebra. The taxis clearly sense our post-prandial vulnerability, and operate a creative attitude to receipts, and to powers of ten. But this round of ambiguous paperwork and mathematical corrections is just the prelude for Vesna and myself, who have a cosy night in with the scripts.

Coordination

At a competition, the leaders of each team study their own students’ work, and agree an appropriate mark with a team of local coordinators. The UK has an easier workload: we do not have to provide translations, since our students write in English, though some of them might like to note that in a question about parity, mixing up the words `odd’ and `even’ as if flipping a coin does make it harder to convince the reader you know what you’re talking about.

We start with 9am geometry, where the coordinators are proposing giving Aron 8 or 9 out of 10 as part of a crusade against citing configurational properties as ‘well-known’. Aron has, in fact, outlined a proof of his (fairly) well-known fact, and if the proposal is to award 6 or 7 without this, then the marking team’s entire day is guaranteed to be a continuous series of wars. I think the penny drops shortly after our meeting, and Aron gets upgraded to 10/10 at 9.30. Unfortunately, what remains of the crusade will deny Alex any credit at all for his unjustified claim about the incentre, despite its role in an appealing synthetic solution.

The middle two questions have a wide range of arguments. The British work on Q3 is actually pretty good, and even in the two scripts with small corners missing have organised their cases very clearly, and the coordinators (who initially want to give all full marks) can see that the students already had the ingredients to fix their minor errors. Q2 is more challenging. Once we have worked out where the good bit begins, Nathan’s solution is clearly superb, and once we’ve worked out which of his mysterious side-comments to ignore, Giles has all but the final details of a really imaginative solution, and Agnijo is flawless. Aron seems keen to make an even number of really confusing mistakes on this paper, so on this question has mixed up ‘horizontal’ and ‘vertical’ as if flipping a coin, though the coordinators are more sympathetic than I would have been. Tom claims that his solution is ‘very poorly written’, which is very far from the case, but after rolling back and forth through his logic a few times, we agree that a couple of cases of q are inadvertently missing.

The students return from their short excursion in time to hear their scores before dinner, and though Alex is a bit disappointed about the non-acceptance of his ‘lemma’, everyone is broadly pleased with themselves, as they should be. I get my first experience of the infamous hotel salad, which the students had previously described as ‘vinegar topped with lettuce’, which is roughly accurate, though the rest is nice enough. Agnijo is worried the main course includes beef, but is satisfied with the supposedly vegan alternative, namely a grilled fish.

The Balkan countries take the table of scores a bit more seriously than we do, and so this year’s celebratory table is sipping Bulgarian cognac washed down with Romanian tears, though this wholesome rivalry shouldn’t distract from the hugely impressive seven perfect scores from those countries’ contestants (plus four from the others). The competition at the adjacent table seems to be the relative merits of Serbian, Macedonian and Montenegrin wine and rakija. Meanwhile, the UK students have made plenty of new friends to induct into their favourite card games, and some Albanians, Bosnians and Turks seem a) very keen to practise their excellent English, and b) appropriately baffled by the rules, and lack of rules.

Round and about

The bulk of Friday is set aside for an excursion. Our destination is Valjevo, a town two hours’ drive west of Belgrade, which represents some sort of historical home for the Serbian maths enrichment community. We gather in their gloriously rococo hall to listen to an in-depth presentation concerning many aspects of daily life at Valjevo Grammar School. The nearby research institute in leafy Petnica offers a more science-focused perspective. The students get to tour some labs, though they don’t get to practise for their upcoming A-level or Highers physics by trying any experiments. Nathan, however, finalises his solution to Q4 from the contest, which seems a good use of time, and which you can read earlier in this report. Aron asks me to solve what seems a challenging geometry question in my head. I cannot. A stamp-sized freehand diagram on a napkin doesn’t help either.

Vesna was a regular visitor to Petnica as a teenage olympiad contestant, and she has briefed me on the charms of a nearby cave, apparently a regular choice for planned and unplanned excursions during her selection camps in the 90s. The UK group plans to sneak away from the third phase of the tour to find this cave, but we are foiled because the third phase of the tour is indeed a visit to the cave. This involves a short walk, during which Agnijo is harassed by the world’s least threatening dog. The temperature is pushing 30C, but Aron is worried about sunburn, so is reluctant to remove his polar fleece. He gently roasts, while Alex tells us some horror stories from his experience as a Wimbledon ballboy during the 2016 heatwave. The cave provides cool relief, and is indeed giant, with plenty of sub-caves underneath the looming stalactites.

It turns out we are in the less impressive half of the cave. The students want to climb to the more impressive upper cave. It may be more impressive, but it is also considerably darker, and I admire Giles’ and Nathan’s tenacity to find out exactly how far a distant rocky staircase extends into the gloom temporarily illuminated by a phone torch. That concludes the adventure, and we return to Belgrade coated in varying quantities of cave detritus. The return journey affords great views of the distant mountains towards the Bosnian and Montenegrin borders, though Tom is keen to use the time to make a start on coordinating the multi-author student report. Unable to avoid eavesdropping on the discussion, sounds like it will be a substantial document when completed…

Finishing up

Back in Avala, the closing ceremony takes place during dinner, and is informal. Jury chair Zoran Kadelburg awards the certificates; chief organiser Miljan presents the medals; and Miljan’s wife notices and steps into the essential role of helping the medallists flip their newly-acquired prizes in front of any flags they might be carrying for the waiting photographers. This one-at-a-time low-key arrangement was actually very nice for everyone, and our four medallists enjoyed their moments.

It is a balmy evening, so we drift outside again. Aron is random-walking, hunting for the WiFi sweetspot so he can download the punchline to our colleague Sam’s claimed complex solution to Q1 before Nathan finishes rounding up new players for the next round of card games; while Giles and Alex disappear off towards the most distant unlit car park with a troupe of guides and Bosnians and a volleyball. At the leaders’ table, Vesna and the other Balkan residents give a collective hollow laugh on hearing that I have elected to travel to the Montenegrin Alps by bus. But that ten hour experience starts tomorrow, outside the remit of this report, which will end here, with some pictures of mountains.

Harmonic ranges and Balkan MO 2018 Q1

A discussion of the non-geometry questions {Q2,Q3,Q4} on the Balkan MO 2018, held in Serbia, may be found here.

A blog post about the UK team’s experience is here, and a more formal pdf report is here.

Balkan MO 2018 Problem One

A quadrilateral ABCD is inscribed in a circle \Gamma, where AB>CD, and AB is not parallel to CD. Point M is the intersection of the diagonals AC and BD and the perpendicular from M to AB intersects the segment AB at the point E. If EM bisects the angle CED, prove that AB is a diameter of \Gamma.

I do not think that this was the hardest question on the paper, but I have the most to say about it, so it gets its own post. The section entitled ‘Step One’ contains (including the exercise at the end) a complete solution which only uses familiar material. The remaining sections have to quote some more obscure material, and may be of less interest to inexperienced readers, for whom many other Balkan and IMO geometry problems might be more appropriate.

Although I’ve been working hard to improve my geometry over the past couple of years, my attitude to the subject remains recreational. I prefer problems with a puzzle-like quality rather than this sort of question, whose statement is, after a little thought, not so surprising, even if most proof methods are either complicated (but elementary) or exotic. I feel most approaches to this problem require three steps: it’s easy to read a solution and forget that the first step really is a step!

I’m fairly vigorously opposed to software diagrams, as at least for me they discourage exactly the sort of insights one is generally hoping for. If you are reading this section carefully, almost certainly the most useful approach is to draw your own diagram, moderately accurate. There are only five points, though you might like to peek at Step Zero to inform drawing an accurate enough diagram without needing to apply the condition by eye.

Step Zero: Introduce X, the intersection of AD and BC.

To follow through any synthetic approach, it’s essential to have a good perspective on what the diagram means, and you will almost certainly need to introduce X to get such a perspective. Here are a couple of reasons why you might think to introduce X:

  • If the conclusion is true, then \angle ADB=\angle ACB=\pi/2, and so M lies on two altitudes, and thus is the orthocentre of some triangle. Which triangle? It’s triangle AXB.
  • Alternatively, the corresponding altitude is an angle bisector of the pedal triangle, and so the given diagram might remind you very strongly of this. Which triangle has pedal triangle CED? It’s AXB again.
  • If your diagram was accurate enough (and since part of the statement is a ‘given…’ this is not so easy) you might have noticed that AD, ME and BC were concurrent. Where? At X:= AD n BC, obviously.
  • In a similar vein, if the conclusion is true, then ADME and BEMC are both cyclic, and we are given ABCD cyclic. The radical axes of these three circles are AD, ME, and BC, so it is reasonable to guess that X, the (hypothesised) point of concurrence is relevant. See later.
  • You are given part of a complete quadrilateral (since M is one of the intersection points of quadrilateral ABCD$ – it might well be useful to complete it!
  • Random luck. It’s not unreasonable to consider arbitrary intersections, though this can be a low-reward strategy in general. If you did introduce X for no reason, you then had to guess, observe or realise that X, M and E should be collinear.

Step One: Proving X, M, and E are collinear.

This is harder than Step Two I think, so is postponed.

Step Two: showing the result, given X,M,E collinear

The official solution proposes introducing the reflection of A in E, which is certainly a good way to get lots of equal angles into useful places rather than not-quite-useful places. However, probably one didn’t spot this. Whether or not this was your motivation in the first place, once X is present, it’s natural to look for an argument based on the radical axis configuration. Our conclusion is equivalent to showing that ADME or BEMC are cyclic, and obviously ABCD is given as cyclic.

However, motivated by the radical axis configuration (Which you can look up – but I recommend not getting distracted by what radical axis means at this stage. It’s a theorem concerning when three pairs of points form three cyclic quadrilaterals, and it has a valid converse! I also recommend not drawing any circles when thinking about the diagram.) let E’ be second intersection of circles ADM and BMC. We know that E’ lies on line XM, and so it suffices to show that E’=E. But by chasing angles in the cyclic quadrilaterals involving E’, we find that if E\ne E', then \angle EE'A=\angle BE'E, and so \triangle AEE'\equiv \triangle BEE', which after a bit of thought implies triangle AXB is isosceles, which contradicts the given assumptions.

Step One: Proving X, M, and E are collinear

By introducing enough extra notation and additional structure, one can prove this part by similar triangles. I think a natural approach in a question with significant symmetry is to use the sine rule repeatedly. This has pros and cons:

  • Disadvantage: it’s easy to get into an endless sequence of mindless calculations, which don’t go anywhere and leads more towards frustration than towards insight.
  • Advantage: one can plan out the calculation without actually doing it. Imagine, to give a completely hypothetical example, trying to plan such an approach in a lurching Serbian minibus with only one diagram. You establish which ratios can be calculated in terms of other ratios, and wait until you’re back in a quiet room actually to do it.

You might try to show that \angle ADB=\angle ACD=\pi/2 directly by such a method, but I couldn’t make it work. I could plan out the following though:

  • Start with some labelling. I write \alpha,\beta for \angle XMD, \angle CMX, and a,b for \angle DME,\angle EMC. The goal is to prove that (a,\alpha) and (b,\beta) are complementary by showing that \frac{\sin \alpha}{\sin \beta}=\frac{\sin a}{\sin b}. Will also refer to \hat{A} for \angle BAD when necessary.
  • The first ratio of sines is the easier one. Using the equal length MX in triangle DXM, triangle CMX, and then the sine rule in triangle DXC, obtain \frac{\sin\alpha}{\sin\beta}=\frac{DX}{CX} = \frac{\sin \hat{A}}{\sin \hat{B}}.
  • We can obtain \frac{\sin a}{\sin b}=\frac{DE/DM}{CE/CM}, but this could get complicated. However, by exploiting the equal angles \angle DEA=\angle BEC, we can derive \frac{DE}{CE}=\frac{AD}{BC}\frac{\sin \hat{A}}{\sin\hat{B}}. But of course, ABCD$is cyclic, and so there are relevant similar triangles, from which \frac{AD}{BC}=\frac{DM}{CM}. So in fact we have shown \frac{\sin a}{\sin b}=\frac{\sin \hat{A}}{\sin \hat{B}}, as we wanted since now we know:

\frac{\sin \alpha}{\sin \beta}=\frac{\sin a}{\sin b}. (1)

  • We need to be careful as this doesn’t immediately imply \alpha=\pi-a and \beta=\pi-b. (For example, we need to exclude \alpha=a! It’s useful to exploit the fact that both a and b are obtuse here. For this type of thing, it’s more useful to focus on showing uniqueness (we definitely know one solution!) rather than finding all solutions. We are essentially asked to show uniqueness of a solution to an equation like

\frac{\sin(\theta-x)}{\sin x}=z, (2)

  • where \theta<\pi. After suitable rearranging, (2) determines \tan x, and so certainly has at most one solution in any interval of width less than \pi. This is a standard issue when using this type of argument and it’s important to know how roughly how to resolve such issues, as you wouldn’t want to waste significant competition time on such technicalities.

As an exercise, you can try to prove Step Two using this method. A hint: suppose M is not the orthocentre of triangle AXB. Introduce points C’,D’ such that \angle AD'B=\angle AC'B=\pi/2. Now AE bisects \angle DEC but also \angle D'EC'. Can you use this to find two congruent triangles which can’t possibly actually be congruent?

An alternative synthetic approach

UK student Alex started with the following observation. Simple angle-chasing in cyclic quadrilateral ABCD reveals that

\pi/2-\angle AME = \angle EAM=\angle MDC,\quad \pi/2 - \angle EMB=\angle MBE=\angle DCM. (3)

But we are given that M lies on the angle bisector of $\angle CED$. So we make the following claim.

Claim: the only point M which lies on the angle bisector and satisfies (3) is the incentre of triangle CED.

Remark: This claim is false. However, it is true that such a point can only be the incentre or E-excentre of triangle CED. One could salvage the original by restricting M to lie inside the triangle.

Remark: As was heavily discussed, this claim is certainly not well-known. It is very believable, but it is also not obvious either. An approach by ratios of sines, for example, as in the solution given above, seems rather tricky. Aron’s argument below is lovely, but again brief is not equal to easy’!

Proof of claim (Aron): Write \theta:= \angle MDC and \varphi:=\angle DCM. Consider the altitude MX in triangle MDC. This is isogonal in this triangle to line ME, because the angles \pi/2-\theta and \pi/2-\varphi are interchanged at M. This means that the circumcentre of triangle MDC lies on ME. (Perhaps you are more familiar with the stronger statement that the orthocentre and circumcentre – eg of triangle MDC – are isogonal conjugates.) But the circumcircle of triangle MDC also lies on the perpendicular bisector of CD, and this meets the angle bisector on the circumcircle of triangle CED. Indeed, this intersection point is the arc midpoint of CD, and this really is well-known to be the circumcentre of \odot ICI_ED, the circle which includes the incentre and the E-excentre, and so this characterises the two possibilities for M, as required.

Harmonic ranges

In the end, the most straightforward approach to this question was to use harmonic ranges. Personally, I would use this to complete what I referred to as Step One, namely showing X,M,E collinear. I feel the radical axis argument given above is a more natural way to handle the second step, though one can also deploy projective theory for this too in relatively few steps.

This is not the place for an in-depth introduction to harmonic ranges. However, I think less experienced students are often confused about when they should consider looking for them, so I’ll try to focus on this.

What is it? Study four points A,B,C,D on a line \ell, grouped into two pairs (A,B),(C,D)$ Then define the cross-ratio to be

(A,B ; C,D ) := \frac{\overrightarrow{CA}}{\overrightarrow{CB}}\,\div \,\frac{\overrightarrow{DA}}{\overrightarrow{DB}}. (4)

We say that (A,B;C,D) form a harmonic range (or harmonic bundle, harmonic system etc etc.) if their cross-ratio is -1. This certainly implies that one of (C,D) lies between A and B, and the other lies outside. Note that this is a property of two pairs of points, not of four points! (A,B;C,D) harmonic does not imply (A,C; B,D) harmonic and so on. Crucially, there is an analogous definition for two pairs of points lying on a given circle.

What can you do with harmonic ranges? There are two reasons why they are useful in solving geometry problems:

  • They often appear in standard configurations and given configurations!
  • Given one harmonic range, there are natural ways to generate other harmonic ranges.

We’ll discuss both of these in a second, but a rough outline of a typical proof using harmonic ranges is as follows. First, identify a harmonic range in the configuration, perhaps using a standard sub-configuration; then, project this first harmonic range around to find some new, perhaps less obvious, harmonic ranges; finally, use some converse result to recover a property about the diagram from your final harmonic range.

We need to discuss the two useful reasons given above in more detail:

  • Take a triangle ABC, and consider the intersection points D,E of the internal and external A-angle bisectors with the opposite side BC. Can you prove (for example using a theorem about lengths in the angle bisector configuration…) that (B,C; D,E) is harmonic?

A related example occurs when you have both Ceva’s configuration and Menelaus’s transversal present in a given triangle, as you then have a harmonic range too. (See the suggested notes.)

One of the points may be the point at infinity on \ell. Without getting into philosophy, can you see how to choose C so that (A,B; C,\infty) is harmonic? This is a very very useful example.

There are plenty of good examples for cyclic ranges too, which you can explore yourself.

  • Harmonic ranges live in the world known as projective geometry. What this means in general is not relevant here, but it’s a good mnemonic for remembering that one can project one harmonic range to acquire another. The most simple example is this.

Given A,B,C,D on a line \ell, let P be some point not on \ell. The set of lines (PA,PB,PC,PD) is often referred to as a pencil. Now, consider intersecting this pencil with a different line \ell' (again not through P) to obtain a new set of points (A’,B’,C’,D’). The key fact is that if (A,B; C,D) is harmonic, then (A’,B’; C’,D’) is also harmonic!

Not only does this give a new harmonic range, it establishes that the harmonic property really depends on the pencil of lines, rather than the choice of \ell. Letting \ell vary, we get an infinite collection of harmonic ranges. So if your diagram has a suggestive pencil of four lines, this is a promising sign that harmonic ranges may have value.

One can also project between lines and circles and from circles to circles, and typically you will need to do this.

How do you prove the results? If you proved the first example above using the angle bisector theorems, you might ask `how do you prove the angle bisector theorem’? Well, there are elegant synthetic methods, but the sine rule is a fail-safe mode of attack too. Essentially, almost all results about harmonic ranges can be proved using the sine rule, perhaps with a bit of help from other standard length-comparison results, in particular Menelaus, Ceva, and trigonometric Ceva.

As we’ve seen in the first attempt at Step One, sine rule calculations can be arduous. Projecting harmonic ranges can be a shortcut through such calculations, provided you know enough examples.

How do I know when to use them? This is really just a reiteration:

  • If you are given a configuration and you recognise part of the diagram as a harmonic range, it might well be worth pursuing this. If you can’t project it into any useful other harmonic range (even after, for example, introducing one extra intersection point), this might lead nowhere, but you’ll probably find something.
  • If you see that part of the diagram is well-suited for projecting harmonic ranges into other harmonic ranges, this is relevant. For example, if there are several lines through one point, particularly if that point also lies on a relevant circle.
  • Similarly, if you require some sort of symmetric result like ‘points \mathcal{A} have some tangency condition iff points \mathcal{B} have the same tangency condition’, then consider whether the condition has a harmonic range interpretation, and whether \mathcal{A} can be projected onto \mathcal{B}.
  • If it feels like the problem could be solved by a giant sine rule calculation comparing various ratios, it might be amenable to harmonic range analysis, so long as you find a first example!

Where can I find actual details? Because this is a report on a contest, rather than a set of lecture notes, the level of detail given here is intentionally very low. Though I hope it gives a useful overview of why such approaches might be useful, perhaps especially for those students who have a passing familiarity with harmonic ranges, but are not yet fluent at successfully applying the methods in actual problems.

The detail is important though, and I recommend these resources, among many articles on the internet:

  • Alexander Remorov’s sheet on Projective Geometry, which also includes a discussion of polars. My own knowledge of the subject is particularly indebted to this source. I like Question 4.
  • Sections 9.2–9.4 of Evan Chen’s recent book Euclidean Geometry in Mathematical Olympiads includes an ideally compact repository of useful statements. Problems, some of which veer into more challenging territory, are at the end of the section.

Balkan MO 2018 – Questions 2,3,4

The Balkan Mathematical Olympiad is a competition for secondary school students organised annually by eleven countries in Eastern Europe on a rotating basis. The 2018 edition was held near Belgrade, Serbia over 7-12 May 2018. The UK was grateful to be invited as a guest nation.

A full account of the competition can be found in this report and this blog report. This blog post concerns the three non-geometry questions on the paper. For typical able British schoolchildren, the order of the questions might not be ideal, and so this post talks about the problems in a non-standard order. A post about the geometry Q1, and a discussion of some of the background, including an introduction to harmonic ranges may be found here.

Problem Three

Alice and Bob play the following game. They start with two non-empty piles of coins. Taking turns, with Alice playing first, each player chooses a pile with an even number of coins and moves half of the coins of this pile to the other pile. The game ends if a player cannot move, in which case the other player wins.

Determine all pairs (a,b) of positive integers such that if initially the two piles have a and b coins, respectively, then Bob has a winning strategy.

Clearly, the game ends when both piles are odd. If one pile a is odd, and the other b is even, then only one move is possible, namely ending up a+b/2 and b/2. It’s not possible that both of these are odd, so further analysis would be required. However, we might notice from this that if a is even, and b is 2 modulo 4, then there are two possible moves, but at least one of them ends up with both piles now being odd.

So when the official solution starts with the sentence ‘let v_2(a) be the exponent of the largest power of two dividing (this is often called a valuation, and is a useful property to consider in many contexts.) a‘, this is not magic, but a natural response to a preliminary investigation along the lines of the previous paragraph.

One should then consider some cases. It is clear that Bob wins if (a,b) are both odd, that is v_2(a)=v_2(b)=0, and in our preliminary exploration we established that Alice wins if a\equiv b\equiv 2 modulo 4, that is v_2(a)=v_2(b)=1. It’s not too hard to establish from here that if v_2(a)=v_2(b), then Bob wins iff this common valuation is even, and Alice wins when it’s odd. It’s also worth noting that this holds irrespective of the players’ choices of moves.

To finish the problem, we now have to classify the remaining cases, and prove what happens in these cases. From the final preliminary observation, we know that Alice wins if v_2(a)=1 and v_2(b)\ge 1, but it seems like the game might go on for ever if both players aim to avoid losing when starting from v_2(a)=0 and v_2(b)\ge 1. One can try some more small examples, or move straight to a conjecture, but the parity (That is, whether a number is odd or even) of \min(v_2(a),v_2(b)) determines the outcome. In neither case does Bob win, but Alice wins when this minimal valuation is odd, and the game continues forever if it’s even, and if you haven’t already, you should try proving this by considering how the valuations could change on any move.

As a slight alternative, especially once you know the answer and have observed that the outcome is invariant under multiplying both a,b by four (and so v_2(a)\mapsto v_2(a)+2), one could attempt the following argument. Introduce the notation (a_t,b_t) for the pile sizes at time t\ge 0, so (a,b)=(a_0,b_0). We know the outcomes in all cases where \min(v_2(a),v_2(b))\le 2. So if we start the original game G from a pair (a,b) satisfying \min(v_2(a),v_2(b))\ge 2, we could consider an alternative game G’ whose rule for winning instead says that we wait for the first time t such that Alice is to move and \min(v_2(a_t),v_2(b_t))\le 2. Then we declare the winner (or non-winner) to be the outcome of the original game G started from (a_t,b_t). While the outcome profile is obviously the same as the original game G, we can claim that playing G from (a,b) is the same as playing G’ from (4a,4b), and thus derive the entire outcome profile by induction.

The details required to establish this claim are easy but numerous, and certainly need to be present in a full solution, which explains Alex’s unfortunate mark for this problem despite having this sophisticated and workable idea. Finishing the details would be an excellent exercise for anyone aiming to tighten up their combinatorial clarity at this level.

Problem Two

Let q be a positive rational number. Two ants are initially at the same point X in the plane. In the n-th minute (n=1,2, … ) each of them chooses whether to walk due north, east, south, or west, and then walks q^n metres in this direction. After a whole number of minutes, they are at the same point in the plane (not necessarily X), but have not taken exactly the same route within that time. Determine all possible values of q.

The answer is that only q=1 is possible, and the majority of approaches will eliminate all but a finite number of potential values first, then study the cases q=2 and q=1/2 separately. Even though it might seem obvious, remember that you have to provide an example for q=1 too!

This is really a question about polynomials, where the variable is q. So for example, if ant A follows the path NNESWN, then its coordinates after the sixth minute are

(x^6_A,y^6_A)=\left(q^3-q^5,\, q+q^2-q^4+q^6\right).

So if we want to prove it’s impossible for (x^n_A,y^n_A)=(x^n_B,y^n_B) for some different length-n paths, we could first focus on just one coordinate, say the x-coordinate. But note that x_A^n-x_B^n is a polynomial in q with degree at most n, where all the coefficients are {-2,-1,0,1,2}. So if the ants are in the same place at time n, then q is a root of this polynomial.

Insisting on converting q into \frac{a}{b} at an early stage is a sort of intellectual comfort blanket that’s probably going to distract from the main insight. But at this stage, we do need to introduce this, and argue that if q=\frac{a}{b} in lowest terms, then q cannot be a root of such a polynomial if either a or b is at least 3. Proving this yourself is definitely a worthwhile exercise. Remember to use that a and b are coprime! (With an additional idea, you can reduce instead to a polynomial with coefficients in {-1,0,+1}, from which you can finish even faster.)

To reduce the number of cases left, we can show that there are examples for q iff there are examples for 1/q, arguing either via the polynomial description (much easier with q rather than \frac{a}{b} again here), or more combinatorially in terms of reversed ant paths.

To finish the problem we have to eliminate one of the possibilities q=1/2 and q=2 (as one follows from the other by the previous paragraph). For q=2, we should study the first time at which the ants diverge, but life will be easier if we argue that we may assume that this happens on the first step. Now, we study the first couple of moves.

  • If one ant moves horizontally and the other moves vertically on the first move, then what can you say about the parity of each ant’s coordinates after the first step, and indeed after all future steps? This will show that they cannot ever meet.
  • Otherwise, assume that both ants move horizontally, one East, one West. Since we can’t use parity, but powers of two are deeply involved, it makes sense to consider using congruence modulo 4. Indeed, after this first step, the ants’ x-coordinates are not congruent modulo 4 (since one is 1 and the other is -1).
    • If they both move vertically on the second step, or both move horizontally on the second step, this remains the case. (One should check both options for the horizontal case.) Thereafter, all moves have length divisible by 4, and so this property holds forever, and so the ants do not meet.
    • If one moves horizontally, and one moves vertically on the second step, what can you say about the ants’ y-coordinates modulo something relevant?

If you want to study q=1/2 instead, you might observe by trying some examples that if the ants head off in different directions, there is a real sense that they become too far apart to get back together using the future allowed moves. This motivates considering some sort of distance argument. The interplay between the coordinates is not really suited to standard Euclidean distance, since the ants can’t walk in a diagonal direction (which is what will mostly determine the Euclidean distance). Instead, it’s worth studying d_n(A,B):=|x^n_A - x^n_B| + |y^n_A-y^n_B| (which is sometimes called \ell_1-distance, or Manhattan distance or taxicab distance.) What is d_1(A,B), and can you control d_n(A,B)-d_{n-1}(A,B) strongly enough to show that d_n(A,B) is always strictly positive? If you can, perhaps you can draw an analogy with the argument for q=2 as a final insight into the workings of this interesting question?

Problem Four

Find all primes p and q such that 3p^{q-1}+1 divides 11^p+17^p.

None of the UK students solved this problem during the competition, but several managed it during some free time the following morning. Nathan’s solution, lightly paraphrased, will follow shortly.

In a question like this, you don’t know how many of the details will be crucial. Is the choice of {3,11,17} going to be important? How will we use the fact that q is prime? You probably can’t answer these meta-questions immediately. It also looks like standard motifs of subtracting multiples of 3p^{q-1}+1 from 11^p+17^p is not going to make life easier. Nathan’s approach is to study the possible factors of 11^p+17^p, focusing on prime power factors. Once he has a rich enough understanding of potential such factors, he can then study whether they combine to form 3p^{q-1}+1, which turns out to be very restrictive, leaving only a handful of cases to eliminate by hand.

Nathan writes: We can quickly eliminate the possibility that p=2, and so now assume we have a solution where p is odd.

Claim I: None of 8, 49 or 11 divide 3p^{q-1}+1.

Proof: It’s enough to show that they do not divide 11^p+7^p. The non-divisibility of 11 is clear. For 8, note that 11^p\equiv 1,3 and 17^p\equiv 1 modulo 8, and so 11^p+17^p\equiv 2,4 \not\equiv 0.

To handle 49, we rewrite 11^p+17^p as 11^p-(-17)^p and we have the valuation v_7(11 - (-17))=v_7(28)=1. So when we lift the exponent (see later), we find

v_7\left(11^p-(-17)^p\right) = 1+v_7(p).

So if 49\mid 11^p+17^p, then the LHS is at least two, and so v_7(p)\ge 1. But then p=7 is the only option, for which certainly 49\nmid 3p^{q-1}+1. The claim is now proved.

So we may now write

3p^{q-1}+1 = 2^a7^b \prod r_i^{e_i}, (1)

where r_i are primes not equal to {2,7,11}, and a\in\{1,2\},\, b\in\{0,1\}.

Claim II: each r_i\equiv 1 modulo p.

Proof: As before r_i\mid 11^p-(-17)^p, and since r_i\ne 11, 11 has a multiplicative inverse modulo r_i, and so indeed there exists t such that 11t \equiv -17 modulo r_i. Using this in the divisibility relation:

r_i\mid 11^p-(-17)^p \equiv 11^p - (11t)t^p \equiv 11^p(1-t^p) \quad\iff\quad r_i\mid 1-t^p.

The order of t modulo r_i then divides p, so is either 1 or p. If this order is 1, then t\equiv 1, but then, modulo r_i, 11\equiv -17, so r_i\mid 28, which we have excluded already. So the order is p, and thus p\mid r_i-1, as we claimed.

Going back to (1), we have

1\equiv 3p^{q-1}+1 = 2^a7^b\prod r_i^{e_i} \equiv 2^a 7^b\quad \mod p,

and so p\mid 2^a7^b-1. But remember that a\in\{1,2\} and b\in\{0,1\}, so there are only a handful of cases to check. Each of the other cases requires a line or two to eliminate, so do try this yourself! In the end, though, we see that (a,b)=(2,0) or (2,1), both leading to p=3 are the only possibilities. Returning to the original question, we just have to check possible solutions to 3^q+1 \mid 11^3+17^3=2^2\cdot 7\cdot 223, which we can do manually (for example by checking all prime q\le 7), to find that the only solution is (p,q)=(3,3).

Dominic: As part of this solution, Nathan uses the lifting the exponent lemma to control v_7(11^p-(-17)^p). This example is simple enough that it’s probably easiest to go directly. Since p is odd, we can factorise

11^p+17^p= 28\cdot \left( 11^{p-1}- 11^{p-2}\cdot 17 + 11^{p-3}\cdot 17^2-\ldots + 17^{p-1}\right).

Can you come up with an argument for why 7 cannot divide the second factor? Some of the notation Nathan used elsewhere in his solution may be useful! If you can, then you’ve shown that v_7(11^p+17^p)=1.

The general statement of the lemma relates v_p(x^n-y^n) to v_p(n) and v_p(x-y), which explains why Nathan converts +17^p to -(-17)^p, though it makes little difference to the proof. You can find statements of this lemma, which has become relatively well-known recently in this community (and which is sometimes attributed to Mihai Manea), in many places on the internet and in modern books. The proof is very similar in the general case to the special case discussed previously. It’s worth remembering that the case p=2 always requires extra care (and indeed a different statement). This distinction comes from the fact that the simultaneous congruence equations x+y\equiv 0 and x-y\equiv 0 modulo $n$ have two pairs of solutions when 2\mid n.

It’s worth noting also that in a solution like Nathan’s where different ranges of options are excluded one after the other, this clear organisation into claims is of huge benefit to the reader, irrespective of how much text is or isn’t included as a prelude.

EGMO 2018

Last week the UK held its annual training and selection camp in Cambridge. This week, four of the students have been attending the European Girls’ Mathematical Olympiad. 2018 is the seventh edition of this prestigious competition, and is being held in Florence.

You can find very many details about the competition, and observe the UK’s excellent performance (with particular congratulations to Emily, who obtained a perfect score) at the competition website. A short article about the team in the TES can be found here.

In this post, I’m going to muse on some of the problems. You can find the two papers here and here.

Problem Two

Part a) would have been more immediate if the set A had been defined as

A:= \left\{\frac{k+1}{k} \,:\, k=1,2,3,\ldots\right\},

as this is instantly suggestive of a telescoping product such as

7 = \frac{7}{6}\cdot \frac{6}{5}\cdot\ldots \cdot \frac{2}{1}.

I found part b) to be one of the most difficult sections of the paper. It builds on the idea that given an expression for x as a product of elements of A, and an expression for y as a product of elements of A, we can combine these (ie take the product of the products!) to get an expression for xy as a product of elements of A. This yields f(xy)\le f(x)+f(y), and so the task is to show that sometimes this isn’t the most efficient way to proceed.

I tried a couple of things, like trying to bound f(p) below when p is a prime. This wasn’t ludicrous, as one would certainly need to use a term \frac{kp}{kp-1} somewhere in the product so that it is divisible by p. However, this didn’t go anywhere, and nor did investigating f(n!). Perhaps others had more success down these avenues.

But as a general rule, if an abstractly-defined function is typically hard to calculate, then classes where you can calculate it are likely to be extra valuable. Here, powers of two make life particularly easy. We have 2\in A, and so 2^n=2\times 2\times\ldots\times 2 is a valid product. And we can’t possibly achieve 2^n as a product of fewer terms than this, because 2 is the largest element of A. So f(2^n)=n. Note that this is already way better than the bound we would have achieved from our argument in part a), which yields f(m)\le m-1.

My next observation was that a similar argument and a natural construction gives f(2^n+1)=n+1. But this can be extended so that when 2^n+1\le m\le 2^{n+1}, we have f(m)\ge n+1 and in fact there is equality exactly for

m= 2^n+1, 2^n+2, 2^n+4,\ldots, 2^n+2^{n-1},2^{n+1}. (*)

In particular, note that all of these are even except 2^n+1. It may well be the case that we don’t need this extension, but before you’ve solved the problem you don’t know how much you’ll have to extend each idea!

I had a feeling that this meant f(2^n+1) was a strong candidate to satisfy the requirements, and that almost any factorisation would work. I suspect many students at this point did some refinement of choice of n, but I want to stay abstract, and use the extended observation (*). Since 2^n+1 is certainly not always prime, let’s focus on the infinitely many values n where it has a factorisation as 2^n+1 = ab, and consider whether a or b can achieve equality at (*). We’d better introduce the notation

2^\alpha<a<2^{\alpha+1},\quad 2^\beta<b<2^{\beta+1}.

So ab> 2^{ab}+2^a+2^b+1, and so \alpha+\beta>n. But similarly, ab< 2^{\alpha+1}2^{\beta+1}, so \alpha+\beta<n+2. We obtain

\alpha+\beta+1=n,

which is kind of what I’d been hoping for when I started this analysis. Now, we have

f(a)\ge \alpha+1,\quad f(b)\ge \beta+1,

\Rightarrow\quad f(a)+f(b)\ge \alpha+\beta+2 = n+1, (**)

with equality precisely if a,b both satisfy the equality conditions at (*). But a,b are odd, and so we have equality at (**) precisely if a=2^\alpha+1,b=2^\beta+1. So we have a resolution to the problem whenever 2^n+1 can be non-trivially factorised in any way other than 2^n+1=(2^\alpha+1)(2^\beta+1), so we have a rich (and certainly infinite) class of suitable (x,y).

Problem Three

An obvious remark. The jury will never choose contestant i if she has fewer than contestants in front of her unless they are forced to. They are only forced to if everyone has this property. So we ignore the second dashed bullet point, as it just tells us when the process ends. And with a little further thought, the process ends exactly when the contestants are in correct order.

I suspect part a) of this may end up featuring on future examples of our interactive write-up clinic, where students are challenged to produce technically-correct arguments for obvious but awkward mini-problems. The location of contestant C_n is probably a good starting point.

For part b), you have to find an optimal construction, and prove that it’s optimal. At national and junior olympiad level, students often forget that they have to supply both of these components. At international level, the challenge is to work out which one gives the entry into the problem. I would say that about two-thirds of the time, either the optimal construction is very obvious, or is best attacked after you’ve had some insight into the bound. For this question (and again it’s just my opinion), I felt it was all about the construction. I made absolutely no progress by aiming for bounds. Whereas the construction offers plenty of insight into how to prove the bounds, and so once I had it, I found it quick.

The usual rules apply. An optimal construction is going to have to be neat to describe. It’s very unlikely to have millions of cases. Intuitively, it seems reasonable that starting the contestants in reverse order gives the jury the greatest possible ‘elbow room’ to squeeze moves into the procedure. Perhaps you tried to prove this directly, by coupling a procedure starting from arbitrary order with a corresponding procedure starting from reverse order? Well, I found that very hard, and perhaps you did too.

However, that doesn’t mean it’s the wrong construction! The key question is, what to do about contestant C_n? Well, essentially nothing. This contestant can never be moved. So when do we start allowing other contestants to pass her? It seemed natural to let the other contestants C_1,\ldots,C_{n-1} do as much as possible among themselves first. That is

\mathbf{C_n},C_{n-1},\ldots,C_2,C_1 \quad \Rightarrow\Rightarrow\Rightarrow \quad \mathbf{C_n}, C_1,C_2,\ldots,C_{n-1},

where \Rightarrow\Rightarrow\Rightarrow denotes lots of moves. At this point, what to do next stood out for me, namely that one could use \mathbf{C_n} at the start to put all the others back into reverse order, while moving \mathbf{C_n} to the back. That is

\mathbf{C_n},C_1,C_2,\ldots,C_{n-1}\quad\Rightarrow \quad C_1,\mathbf{C_n},C_2,\ldots,C_{n-1} \quad\Rightarrow\quad C_2,C_1,\mathbf{C_n},C_3,\ldots,C_{n-1}

\Rightarrow\Rightarrow \quad C_{n-1},C_{n-2},\ldots,C_2,C_1,\mathbf{C_n}.

You might have tried other things first, but once you notice this, you just know it has to be right. It’s just too elegant a construction, and it looks like the sort of thing one prove will be optimal, because the overall process

\mathbf{C_n},C_{n-1},\ldots,C_n\quad \Rightarrow\Rightarrow\Rightarrow \quad \mathbf{C_n},C_1,C_2,\ldots,C_{n-1}

\Rightarrow\Rightarrow\quad C_{n-1},\ldots,C_2,C_1,\mathbf{C_n}\quad\Rightarrow\Rightarrow\Rightarrow\quad C_1,C_2,\ldots,C_{n-1},\mathbf{C_n},

incorporates the corresponding process for n-1 (twice, in fact) and so induction is very accessible both for calculating the total number of moves. We conjecture that this is indeed the optimal process, and under this assumption, with f(n) the number of moves, we would have f(n) = f(n-1) + (n-1) + f(n-1), from the three stages of the process, from which, after looking at small values,

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

I started by saying that the construction was the hard part of this problem. Well, that doesn’t mean the bound is easy. But at least with a construction in hand, you can make observations that might inform a bounding argument:

  • observation 1: contestant C_n never jumps;
  • observation 2: in the optimal construction, by induction C_{n-1} doesn’t jump in the outer phases, so in fact jumps only once, ie during the middle phase;
  • observation 3: contestant C_{n-2} doesn’t jump very often, and in fact can only jump after at least one of C_{n-1} and C_n have ended up in front of her. Since we’ve established that C_{n-1},C_n don’t jump very often themselves, this gives a bound on the number of times C_{n-2}.

There is still work to do here, and errors with \pm 1 could easily creep in. But I still hold fast to my original claim that the construction was the hard part here. Or at least, the rough form of the construction. I guess it’s possible that one would have started making observations like the three above without a construction in mind, but I think it’s unlikely. Anyway, I leave for you the final details of the bounding argument, which involves formally transcribing observation 3, proving it, then generalising it to jumps of C_{n-3} and so on.

Problem Four

One of the exercises I have been setting to UK students recently is to produce short solution digests, which manifest any key ideas of the solution abstractly and briefly enough to resonate in the future. I’m a little tired of domino tiling problems, so I’ll do one of these here. This will be slightly longer than if I were not writing for a (small) audience.

Double-counting the total value by rows/columns and by dominos shows there are \frac{2kn}{3} dominos in a balanced configuration. When n=3, we can achieve k=1, and by tiling copies of this down the main diagonal, can extend to 3\,|\,n. For 3\not|\,n, we must have 3\,|\,k ie k\ge 3, but in fact k=3 is achievable, by tiling the main diagonal with copies of small boards for which k=3 can be constructed with a bit of trial-and-error.

The double-counting idea at the start is the nice part of the problem. The construction is a bit annoying, but saving ourselves work by building up large examples from copies of small examples is a useful motif to have in mind.

Problem Six

This question has lots of clues in the statement. It would, for example, be pretty surprising if the answer were ‘no’ to part b) given the setup in part a).

My confession is that I wasted lots of time on part a) not using the option m=0, which was foolish given that it’s clued from part b) that one needs to use the option m=0. My thought had been to consider some integer y, and ask which integers x were banned (if we were aiming for contradiction in part a)). For part a), it gets harder if t is smaller, so I found it helpful to think of t as \epsilon\ll 1. Anyway, if you struggled on part a), maybe worth reviewing whether you were definitely trying to solve part a), and not accidentally using the setup that really addressed part b)!

Some people have shown me solutions to part a) that carry an air of magic, by placing all the key steps (such as (*) to follow) in the language of the original setup. Let’s try to be cleaner. The key is to consider m=0. Since m=0 is included, we know that whenever x<y, we must have

\epsilon y \le x \le (1-\epsilon)y. (*)

Maybe you just have a gut feeling that this can’t be possible if you have enough xs and ys? But either way, choosing to focus on (*) is the key step, because once you know you have to prove the result based on this, it’s not too hard. I prefer addition to multiplication, so one might as well take logs (since does it really look like we’re going to use heavily the integer property now?) to obtain

\alpha\le |z_i - z_j|\le \beta,

for all z_i,z_j in some large finite collection, where 0<\alpha<\beta. You should now have a strong gut feeling that this is impossible. You have an arbitrarily large collection of real numbers which have to be close to each other pairwise, but never too close pairwise. How to finish the argument is a matter of taste.

For part b), assuming we’re aiming for the answer ‘yes’, we probably want to construct it one step at a time, and you want to think of t\approx \frac12 to make life as hard as possible.

Now, suppose you have x_1,x_2,\ldots,x_n so far. What next? Well if we could have

x_{n+1} \equiv \frac{x_i}{2}\,\mod x_i,

for all i=1,\ldots,n, that would be perfect. We can often solve sets of coupled residue equations like this using the Chinese Remainder Theorem. (Recall of course that the solutions themselves are rarely important – the fact that they exist is enough!) A couple of things go wrong with trying this crudely:

  • If x_i is odd, then \frac{x_i}{2} is not an integer…
  • If we correct this by asking for x_{n+1}\equiv \lfloor\frac{x_i}{2}\rfloor\,\mod x_i, then there’s a chance we might still be within the t-window around a multiple of x_i.
  • Unless we are going to make complicated demands on the residues, to use CRT it would be easier if all the x_is were coprime.

One option is to give up. But actually all these objections can be handled with fairly small alterations. Can you see how the second objection can be overcome by an appropriate choice of x_1? Remember that t is fixed right at the start, and cannot be equal to 1/2. Is the third objection actually an objection any more? If it is, can we fix it?

Anyway, I guess P6 was my favourite non-geometry question on the paper, though, that’s far from relevant. P5 was pretty neat too, but who knows whether a follow-up geometry post will materialise soon.

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. 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, but for now, a long and separate post is the answer.

This will be available once I’ve successfully de-flooded my apartment.

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 c\not\equiv 0 whenever possible. At all times she has two possible options for where to go next, lets say b_k+a_k, b_k-a_k in the language of the original statement. We lose nothing by assuming -N/2 < a_k\le N/2, and certainly it would be ridiculous for Joe / Hatter ever to choose a_k=0. The only time Alice’s strategy doesn’t work is when both of these are congruent to c, which implies N\,|\, 2a_k, and thus we must have N= 2a_k. 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 b_k. But obviously here, if b_k\equiv 1 modulo p and p\,|\,a_k, then certainly b_{k+1}\equiv 1 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 a_k=N/2, 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 a_ks, 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 a_N=1. Just as in the N=4 case, it doesn’t matter which odd site we start from, since if we again double all the a_ks, 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.

Continue reading

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 a_1,a_2,\ldots,a_{300} be the ordering of the cards. We require that \frac{a_1+\ldots+a_n}{n} is an integer for every 1\le n\le 300. Maybe the values of these integers will be important, so hold that thought, but for now, replace with the divisibility statement that n | a_1+\ldots+a_n.

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 (a_1,\ldots,a_{n-1}) such that you can’t pick a suitable a_n?”

It means that there is no integer k in \{1,\ldots,300\}\backslash\{a_1,\ldots,a_{n-1}\} such that n\,\big|\,(a_1+\ldots+a_{n-1})+k, which for now we write as

k\equiv -(a_1+\ldots+a_{n-1})\,\mod n.

Consider the congruence class of -(a_1+\ldots+a_{n-1}) modulo n. There are either \lfloor \frac{300}{n}\rfloor or \lceil \frac{300}{n}\rceil 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 \{a_1,\ldots,a_{n-1}\}. 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 a_n, we have

\lfloor \frac{300}{n} \rfloor\text{ or }\lceil \frac{300}{n}\rceil \le n-1, (*)

which is summarised more succinctly as

\lfloor \frac{300}{n} \rfloor \le n-1. (**)

[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 \pm 1 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 n\le 17 and true when n\ge 18. Indeed, both versions of (*) are true when n\ge 18.

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 n=18), 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 n\ge 19 because there won’t be equality anywhere.

We have to hope there is a construction for n=18. 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 \alpha\in\{1,2,\ldots,18\} describe the congruence class modulo 18 which is exhausted by \{a_1,\ldots,a_{17}\}. I’m going to hope that \alpha=18 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 \alpha\equiv-(a_1+\ldots+a_{n-1}). 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 a_j, is not a multiple of 18. But then

0 \equiv 0+\ldots+0+a_j+0+\ldots+0,

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 \alpha\in \{13,14,\ldots,18\}.

So we have to tackle a different class. If \alpha\le 12 then our sequence must be

\alpha,18+\alpha,2\times 18 +\alpha, \ldots, 16\times 18 + \alpha,

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

(a_1,\ldots,a_{17}) = (18\lambda_1+ \alpha,\ldots,18\lambda_{17}+\alpha),

where (\lambda_1,\ldots,\lambda_{17}) is a permutation of {0,…,16}. And so we require

k \,\big|\, 18(\lambda_1+\ldots+\lambda_k) + k\alpha, (%)

for 1\le k\le 17. But clearly we can lop off that k\alpha, and could ignore the 18. Can we find a permutation \lambda such that

k \,\big|\, \lambda_1+\ldots+\lambda_k.

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 \frac{\lambda_1+\ldots+\lambda_k}{k} 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 a_is 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

\lambda_1+\ldots+\lambda_{17}=136= 16\times 8 + 8\quad\text{and}\quad 16\,\big|\,\lambda_1+\ldots+\lambda_{16},

which means \lambda_1+\ldots+\lambda_{16} must be 128 = 15×8 + 8, ie \lambda_{17}=8. But then we also have 15\,\big|\, \lambda_1+\ldots+\lambda_{15}, 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

k\,\big|\,2(\lambda_1+\ldots+\lambda_k).

And now if you experiment, you will notice that taking \lambda_1=0,\lambda_2=1,\lambda_3=2,\ldots 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

(a_1,\ldots,a_{17}) = (1, 18+1,2\times 18 +1,\ldots, 16\times 18 +1).

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 \alpha 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

p(1)+p(2)+\ldots+p(366) - \left(h(1)+h(2)+\ldots+h(365)\right)

= \left(p(1)-h(1)\right) + \ldots+\left(p(365)-h(365)\right) + p(366),

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

p(1)+p(2)+\ldots+p(366) - \left(h(1)+h(2)+\ldots+h(365)\right)

= -371 + 358 + 0 = -13.

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 n\ge 25, 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 n\ge 10 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

450\le 4n + 6(100-n)

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

450 \ge 5n + 0\times (100-n), (*)

which gives n\le 90. 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 25\le n\le 90.

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

BMO1 2017Q4

I wasn’t paying enough attention initially, and I calculated a_2=0\text{ or }2. 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 a_2=0 \text{ or }3, and of course a_2=0 is not allowed, since it must be positive. So a_2=3, and a similar calculation suggests a_3=1\text{ or }6. It’s clear that the set of values for a_{k+1} depends only on a_k, so if you take a_3=1, then you’re back to the situation you started with at the beginning. If you choose to continue the exploration with a_3=6, you will find a_4=2\text{ or }10, 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 a_n=T_k=\frac{k(k+1)}{2}, the k-th triangle number, then a_{n+1}=T_{k-1}\text{ or }T_{k+1}.

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 a_{n+1}=T_{k+1}.

The second stage really concerns the question “but what if a_n\ne T_k?” While there are deductions one could make, the key is that if a_1 is a triangle number, the claim we’ve just made shows that a_n is always a triangle number, so this question is irrelevant. Indeed the claim further shows that a_{2017}\le T_{2017}, and also that a_{2017}=T_k 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 \{T_1,T_3,\ldots,T_{2017}\}, 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 a^p\equiv a modulo p to make sense even when a\ge p. 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 a_n=T_n for $1\le n\le k$, and thereafter a_n=T_k 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 T_0!