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 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.

EGMO 2017 – Paper One – Geometric subconfigurations

I’ve recently been in Cambridge, running the UK’s annual training and selection camp for the International Mathematical Olympiad. My memories of living and studying in Cambridge are very pleasant, and it’s always nice to be back.

Within olympiad mathematics, the UK has traditionally experienced a weakness at geometry. By contrast to comparable nations, for example those from Eastern Europe, our high school curriculum does not feature much Euclidean geometry, except for the most basic of circle theorems and angle equalities, which normally end up as calculation exercises, rather than anything more substantial. So to arrive at the level required to be in with a chance of solving even the easier such questions at international competitions, our students have to do quite a lot of work for themselves.

I’ve spent a bit of time in the past couple of years thinking about this, and how best to help our students achieve this. The advice “go away and do as many problems as you can, building up to IMO G1, then a bit further” is probably good advice, but we have lots of camps and correspondence training, and I want to offer a bit more.

At a personal level, I’m coming from a pragmatic point of view. I don’t think Euclidean geometry is particularly interesting, even though it occasionally has elegant arguments. My main concern is taming it, and finding strategies for British students (or anyone else) to tame it too [1].

Anyway, I’m going to explain my strategy and thesis as outlined at the camp, then talk about Question 1 from EGMO 2017, a competition held in Zurich this year, the first paper of which was sat earlier today (at time of writing). The UK sent a strong team of four girls, and I’m looking forward to hearing all about their solutions and their adventures, but later. I had intended to talk about the other two questions too, but I can’t think of that much to say, so have put this at the end.

My proposed strategy

Before explaining my proposed strategy, let me discuss a couple of standard approaches that sometimes, but rarely, work at this level:

  • Angle chase (or length chase) forwards directly from the configuration. Consider lots of intersection points of lines. Consider angles and lengths as variables, and try to find relations.
  • Exactly as above, but working back from the conclusion.
  • Doing both, and attempting to meet in the middle.

The reason why this doesn’t work is that by definition competitions are competitive, and all participants could probably do this. For similar reasons competition combinatorics problems tend not to reduce instantly to an exhaustive search.

It’s also not very interesting. I’m certainly unlikely to set a problem if it’s known to yield to such an approach. When students do try this approach, common symptoms and side-effects involve a lot of chasing round conditions that are trivially equivalent to conditions given in the statement. For example, if you’re given a cyclic quadrilateral, and you mark on opposing complementary angles, then chase heavily, you’ll probably waste a lot of time deducing other circle theorems which you already knew.

So actually less is more. You should trust that if you end up proving something equivalent to the required conclusion, you’ll notice. And if you are given a cyclic quadrilateral, you should think about what’s the best way to use it, rather than what are all the ways to use it.

On our selection test, we used a problem which essentially had two stages. In the first stage, you proved that a particular quadrilateral within the configuration was cyclic; and in the second stage, you used this to show the result. Each of these stages by themselves would have been an easy problem, suitable for a junior competition. What made this an international-level problem was that you weren’t told that these were the two stages. This is where a good diagram is useful. You might well guess from an accurate figure that TKAD was cyclic, even if you hadn’t constructed it super-accurately with ruler and compasses.

So my actual strategy is to think about the configuration and the conclusion separately, and try and conjecture intermediate results which might be true. Possibly such an intermediate result might involve an extra point or line. This is a standard way to compose problems. Take a detailed configuration, with some interesting properties within it, then delete as much as possible while keeping the properties. Knowing some standard configurations will be useful for this. Indeed, recognising parts of the original diagram which resemble known configurations (possibly plus or minus a point or line) is a very important first step in many settings.

Cyclic quadrilaterals and isosceles triangles are probably the simplest examples of such configurations. Think about how you often use properties of cyclic quadrilaterals without drawing in either the circle or its centre. The moral is that you don’t need every single thing that’s true about the configuration to be present on the diagram to use it usefully. If you know lots of configurations, you can do this sort of thing in other settings too. Some configurations I can think up off the top of my head include: [2]

  • Parallelograms. Can be defined by corresponding angles, or by equal opposite lengths, or by midpoint properties of the centre. Generally if you have one of these definitions, you should strongly consider applying one of the other definitions!
  • The angle bisector meets the opposite perpendicular bisector on the circumcircle.
  • Simson’s line: the feet of the three perpendiculars from a point to the sides (extended if necessary) of a triangle are collinear precisely when the point is on the circumcircle.
  • The incircle touch point and the excircle touch point are reflections of each other in the corresponding midpoint. Indeed, all the lengths in this diagram can be described easily.
  • The spiral similarity diagram.
  • Pairs of isogonal conjugates, especially altitudes and radii; and medians and symmedians.

Note, all of these can be investigated by straightforward angle/length-chasing. We will see how one configuration turned out to be very useful in EGMO. In particular, the configuration is simple, and its use in the problem is simple, but it’s the idea to focus on the configuration as often as possible that is key. It’s possible but unlikely you’d go for the right approach just by angle-analysis alone.

EGMO 2017 Question 1

Let ABCD be a convex quadilateral with <DAB=<BCD=90, and <ABC > <CDA. Let Q and R be points on segments BC and CD, respectively, such that line QR intersects lines AB and AB at points P and S, respectively. It is given that PQ=RS. Let the midpoint of BD be M, and the midpoint of QR be N. Prove that the points M, N, A and C lie on a circle.

First point: as discussed earlier, we understand cyclic quadrilaterals well, so hopefully it will be obvious once we know enough to show these four points are concyclic. There’s no point guessing at this stage whether we’ll do it by eg opposite angles, or by power of a point, or by explicitly finding the centre.

But let’s engage with the configuration. Here are some straightforward deductions.

  • ABCD is cyclic.
  • M is the centre.

We could at this stage draw in dozens of equal lengths and matching angles, but let’s not do that. We don’t know yet which ones we’ll need, so we again have to trust that we’ll use the right ones when the time comes.

What about N? If we were aiming to prove <AMC = <ANC, this might seem tricky, because we don’t know very much about this second angle. Since R and Q are defined (with one degree of freedom) by the equal length condition, it’s hard to pin down N in terms of C. However, we do know that N is the midpoint opposite C in triangle QCR, which has a right angle at C. Is this useful? Well, maybe it is, but certainly it’s reminiscent of the other side of the diagram. We have four points making up a right-angled triangle, and the midpoint of the hypotenuse here, but also at (A,B,D,M). Indeed, also at (C,B,D,M). And now also at (C,Q,R,N). This must be a useful subconfiguration right?

If you draw this subdiagram separately, you have three equal lengths (from the midpoint to every other point), and thus two pairs of equal angles. This is therefore a very rich subconfiguration. Again, let’s not mark on everything just yet – we trust we’ll work out how best to use it later.

Should we start angle-chasing? I think we shouldn’t. Even though we have now identified lots of potential extra pairs of equal angles, we haven’t yet dealt with the condition PQ=RS at all.

Hopefully as part of our trivial equivalences phase, we said that PQ=RS is trivially equivalent to PR=QS. Perhaps we also wrote down RN=NQ, and so it’s also trivially equivalent to PN=NS. Let’s spell this out: N is the midpoint of PS. Note that this isn’t how N was defined. Maybe this is more useful than the actual definition? (Or maybe it isn’t. This is the whole point of doing the trivial equivalences early.)

Well, we’ve already useful the original definition of N in the subconfiguration (C,Q,R,N), but we can actually also use the subconfiguration (A,P,S,N) too. This is very wordy and makes it sound complicated. I’ve coloured my diagram to try and make this less scary. In summary, the hypotenuse midpoint configuration appears four times, and this one is the least obvious. If you found it, great; if not, I hope this gave quite a lot of motivation. Ultimately, even with all the motivation, you still had to spot it.

Why is this useful? Because a few paragraphs earlier, I said “we don’t know very much about this second angle <ANC”. But actually, thanks to this observation about the subconfiguration, we can decompose <ANC into two angle, namely <ANP+<QNC which are the apex angle in two isosceles triangles. Now we can truly abandon ourselves to angle-chasing, and the conclusion follows after a bit of work.

I’m aware I’ve said it twice in the prelude, and once in this solution, but why not labour my point? The key here was that spotting that a subconfiguration appeared twice led you to spot that it appeared a further two times, one of which wasn’t useful, and one of which was very useful. The subconfiguration itself was not complicated. To emphasise its simplicity, I can even draw it in the snow:

Angle-chasing within the configuration is easy, even with hiking poles instead of a pen, but noticing it could be applied to point N was invaluable.

Other questions

Question 2 – My instinct suggested the answer was three. I find it hard to explain why. I was fairly sure they wouldn’t have asked if it was two. Then I couldn’t see any reason why k would be greater than 3, but still finite. I mean, is it likely that k=14 is possible, but k=13 is not.

In any case, coming up with a construction for k=3 is a nice exercise, and presumably carried a couple of marks in the competition. My argument to show k=2 was not possible, and most arguments I discussed with others were not overwhelmingly difficult, but didn’t really have any key steps or insight, so aren’t very friendly in a blog context, and I’ll probably say nothing more.

Question 3 – Again, I find it hard to say anything very useful, because the first real thing I tried worked, and it’s hard to motivate why. I was confused how the alternating turn-left / turn-right condition might play a role, so I ignored it initially. I was also initially unconvinced that it was possible to return to any edge in any direction (ie it must escape off to infinity down some ray), but I was aware that both of these were too strong a loosening of the problem to be useful, in all likelihood.

Showing that you can go down an edge in one direction but not another feels like you’re looking for some binary invariant, or perhaps a two-colouring of the directed edges. I couldn’t see any way to colour the directed edges, so I tried two-colouring the faces, and there’s only one way to do this. Indeed, on the rare occasions (ahem) I procrastinate, drawing some lines then filling in the regions they form in this form is my preferred doodle. Here’s what it looks like:

and it’s clear that if the path starts with a shaded region on its right, it must always have a shaded region on its right. As I say, this just works, and I find it hard to motivate further.

A side remark is that it turns out that my first loosening is actually valid. The statement remains true with arbitrary changes of direction, rather than alternating changes. The second loosening is not true. There are examples where the trajectory is periodic. I don’t think they’re hugely interesting though, so won’t digress.

Footnotes

[1] – “To you, I am nothing more than a fox like a hundred thousand other foxes. But if you tame me, then we shall need each other. To me, you will be unique in all the world. To you, I shall be unique in all the world,” said the Fox to the Little Prince. My feelings on taming Euclidean geometry are not this strong yet.

[2] – Caveat. I’m not proposing learning a big list of standard configurations. If you do a handful of questions, you’ll meet all the things mentioned in this list several times, and a few other things too. At this point, your geometric intuition for what resembles what is much more useful than exhaustive lists. And if you’re anxious about this from a pedagogical point of view, it doesn’t seem to me to be a terribly different heuristic from lots of non-geometry problems, including in my own research. “What does this new problem remind me of?” is not unique to this area at all!

EGMO 2015

It’s been a while since I last wrote anything substantial. There have been some posts in the pipeline, but mainly I’ve been working hard on technical things that don’t translate very well into blog posts, and when I haven’t been working on those, have felt like doing non-maths.

Anyway, among other things which happened recently were the UK’s IMO selection camp in Cambridge during the last week of March, and the fourth European Girls’ Mathematical Olympiad in Belarus this past weekend. At the former, I was quite busy organising various things, and so gave a session based on some of my favourite problems about points and lines that I’ve used in the past. My hope was that with each problem in turn the students would actively invest time in thinking about whether the ideas each other were having seemed likely to be profitable. The aim was that being critical about your approach is a necessary skill once you start having lots of ideas for approaches.

This is hard to practise at school just by reading around, whether regarding competition material or generally. In the competition world, official solutions often contain unmotivated magic. This is reasonable, since they are supposed to be a minimal elementary demonstration of the problem’s validity. Motivation is a luxury which space and time sometimes doesn’t permit. And the solutions you find on, for example, Mathlinks often give the impression that the solvers know how to do 25,000 specific types of problem, and the sole task is to identify which type the latest one belongs to. Relating problems to ones you’ve seen before is important, but can hide, or at least dilute the actual ideas in some cases. Knowing that a specific inequality is a special case of a big machine allows you to claim a ‘solution’ but doesn’t help you identify the relevant ideas.

Later in the camp, a conversation arose concerning to what extent the younger staff found these elementary methods and problems easier now that they had experienced various levels of higher education in mathematics than when they were at school. It’s a complicated question, and I don’t think there’s a simple answer. I think the students might suspect that doing a university degree teaches you ‘advanced techniques’ which immediately simplify some of these problems. In rare examples this can be the case, but the majority of the time, I personally feel the only advantage I have is perhaps better instincts for whether something is or isn’t going to work.

Probably a good test would be Euclidean geometry. Adult olympiad staff typically come in two flavours: those who used to be good at geometry and feel out of practice; and those who weren’t good at geometry and certainly had no inclination to remedy this after they left school. I’m probably closer to the first category and I definitely feel out of practice, but also have minimal inclination to remedy this. Nonetheless, on the rare occasions I try these questions (and it’s not going to be for 4.5 hours at this stage…) my progress rate is probably comparable to when I was in sixth form. I’ve no idea how to turn this into a more concrete assessment, but there must be something about doing abstract maths all the time that prevents you forgetting how to do this, so presumably it should be at least as helpful in the types of problem with non-zero overlap with things I actually do. I won’t discuss geometry in the rest of this post, but I did also enjoy the geometry questions – it’s simply that I feel anything I have to say about them would be less useful than saying nothing.

In any case, I enjoyed trying the problems from Belarus in between bouts of typing, and thought I would write some brief comments about how I decided whether my ideas were good or not. To achieve this, I’ve looked at my rough, and will tell you the ideas which didn’t work, as well as some of the ones which did. I’ve paraphrased the statements slightly to avoid having too many LaTeX tags.

WARNING: what follows will spoil questions {2,4,5} if you haven’t already looked at them, but would like to.

Question 2 – A domino is a 2 × 1 or 1 × 2 tile. Determine in how many ways exactly n^2 dominoes can be placed without overlapping on a 2n × 2n chessboard so that every 2 × 2 square contains at least two uncovered unit squares which lie in the same row or column.

The wording of the question prompted me to consider splitting the board naturally into n^2 2 x 2 squares. I then thought about this ‘at least’ in the question, and concluded that for these 2 x 2 squares, it should be ‘exactly’.

I tried doing an unusual colouring, when I coloured half the black squares green, and half blue and tried to show that either only greens or only blues were covered, but this was clearly not true, or fixable. I then tried to do something similar for the other set of 2 x 2 squares (those whose vertices have (odd, odd) coordinates). Roughly speaking, if too few of the outer cells on the original board are covered, you can’t achieve the bounds on these odd inner squares. But this didn’t really give any useful information.

However, it did get me thinking about how what happens in the far top-left affects the rest of the board, and from there most of the ideas came quickly. I described a 2 x 2 square as N, E, S, W depending on which ‘half’ of the square was covered. Then if a square is N, all the squares directly above it must be also be N (*).

I then made two mistakes, and if we’re looking for reasons where experience is helpful, it was probably here, as I spotted them fairly quickly, rather than wasting ages and ages.

First, I decided that either all squares were {N,E} or all were {S,W} which seemed plausible when I had been focusing on the top-left. This gave an answer of 2 \binom{2n}{n}, but after a bit more thought is clearly not symmetric enough.

Second, I thought condition (*) might be the only constraint, along with similar ones for E, S, W naturally too. I tried to count these using a similar method of enumerating lines between these regions, and I realised I didn’t know how to do these sensibly, for example if it looked like this:

EGMO15 Q2 diagram (3)

This led to another bit of meta-maths that I probably wouldn’t have considered if I was 16. Namely, that the idea of counting these monotone lines across the 2n x 2n grid was too nice not to be useful. Also, if I couldn’t see a way to adapt it for this more complicated setup, my setup was probably wrong. This thought was useful, and then by thinking about the interface between {N,E} and {S,W}, then the other way round, it made sense that the configuration could be parameterised by two monotone lines between different pairs of corners, giving an answer of \binom{2n}{n}^2.

So, if it’s possible to give a reason why I could do this, it’s probably because I had an arsenal of ways to check an answer for plausibility, which saved wasting time on something wrong, and also because I trusted that the answer would be nice, which saved wasting time on something which was also wrong, and would probably have been very complicated to resolve.

Question 4 – Determine whether there exists an infinite sequence a_1,a_2,\ldots of positive integers satisfying a_{n+2}=a_{n+1}+\sqrt{a_{n+1}+a_n}.

So, my first reaction was ‘no way’. Why? Because everything’s determined by the first two terms, and I couldn’t think of any reason why a cool choice of the first two terms would force all of the sums a_{n+1}+a_n to be perfect squares. It seemed just about possible that we could arbitrarily large finite sequences with this property. (Though this also turns out to be impossible.)

I imagine many contestants might have felt similarly and spent a while playing round with quadratic residues to get a sense for exactly how hard it is to make this work for the initial terms. But I was suspicious of the form of the recurrence. We know that if it had been defined linearly, then the terms would grow exponentially, but it’s natural to ask roughly how fast they grow in this example, even relaxing the restriction that the terms be integers.

The first observation was that they are indeed (strictly) growing! But how fast? Are there actually enough squares that every a_{n+1}+a_n can be a different one? Note that the squares themselves satisfy a similar recurrence relation (N+1)^2 = N^2 + 2\sqrt{N^2} + 1 > N^2 + \sqrt{ N^2 + N^2}. So this seemed like a very good idea, and my instinct was that this should work, and I felt glad that I hadn’t pursued the quadratic residues approach.

From here we were basically home. I asked whether the sequence grows faster than the sequence (\frac{n^2}{2}), and the answer was no as

a_{n+2}\le a_{n+1}+ \sqrt{2 a_{n+1}} \le (\sqrt{a_{n=1}} + \frac{1}{\sqrt 2})^2,

so if (after translating indices) a_n = \frac{x^2}{2}, we have a_{n+1}\le \frac{(x+1)^2}{2}. This is clearly a problem or at best a very tight constraint if all the \{a_n+a_{n+1}\} have to be perfect squares, so even though we aren’t completely finished, I am confident I can be in one or two lines, with a bit of care. Fiddling with small values of n looked like it would work, or showing that looking at a large enough initial subsequence that the effect of the first two terms dissipated, we must by the pigeonhole principle have a_{n+2}+a_{n+1}=(k+1)^2,\, a_{n+1}+a_n=k^2, which is enough by a parity argument, using the original statement.

This final bit looks and feels a bit messy, but by this stage it really is just finding any argument to justify why a sequence which grows at most as fast as n^2 can’t actually be n^2 eventually.

Probably the reason I did this quickly was because I trusted my instinct for ‘no’, and also because there seemed a quick way to qualify *roughly* how this sequence grew. Sensibly approximating things, and deciding whether it’s appropriate to approximate them is definitely something I feel I’ve got better at during my PhD, so I guess this was helpful, then just try and throw back the important condition that the elements were integers at the very end.

Question 5 – Anastasia partitions the integers [1,2m] into pairs. Boris tries to choose one integer from each pair so that the sum is n. Given n and m, prove Anastasia can select pairs so that Boris can’t succeed.

So I wasted some thought time by imagining that n was fixed and trying to come up with ideas for the choice of pairs which might avoid n. It struck me that there was no reason why a a typical (uniformly chosen) pairing should avoid any particular n unless this value was particularly big or small.

How big or how small? Well Boris can always choose the bigger element of a pair, so the way to make the minimum maximum is to pair as (1,2), (3,4), … , (2m-1,2m). Conveniently, this also achieves the maximum minimum. These can be calculated as m^2,m(m+1) respectively. Suddenly this seems great, because we’ve actually solved the problem for a huge range of n, ie everything not within between these extrema.

The key step here was to start considering special pairings, chosen to give a reduced set of possible sums. Once we’ve had this idea, it makes sense to consider other different special pairings. The reason we got a small set of possible sums is that there’s lots of overlap. We can achieve lots of overlap by looking at the difference between elements in a pair, and making as many of these the same as possible. For, consider pairs (a,a+d), (b,b+d). Then it’s the same to take a and b+d as to take a+d and b, so we get the same sums in lots of different ways.

The other way to have as many differences the same as possible is to go for (1,m+1), (2,m+2), … , (m,2m). Conveniently, we can parameterise the sums now because at each choice, we decide whether to add an extra m or not, so the sum must be 1+2+…+m, plus some multiple of m. So we can defeat Boris, except when n is \binom{m}{2}+km.

This is a good point to stop because what followed was basically book-keeping. We only have to consider a couple of specific cases when m is odd, and one when m is even, that happen not to fall into either of the categories we can now deal with. It wasn’t too hard to corrupt the examples we already have to deal with these.

The key here was responding to initial failure by trying to find any control at all over n. Perhaps given enough time I would have started trying special pairings? Equally, I might have tried small examples, which would not really have been hugely helpful for this question. In any case, trying to eliminate very small or very large n luckily worked well, as a) I didn’t need to use the word ‘very’ twice in the end; and b) the idea of looking at choices of pairings to minimise the number of sums quickly gave other useful deductions.

I also really enjoyed Question 3, though was suspicious that I’d used a bound a great deal weaker than one in the question. Along the way, I was trying something confusing and not especially useful that led me into some interesting theory about Latin squares, which I might write something about later in the week.