Balkan MO 2017 – Qs 1, 3 and 4

The UK is normally invited to participate as a guest team at the Balkan Mathematical Olympiad, an annual competition between eleven countries from South-Eastern Europe. I got to take part in Rhodes almost exactly ten years ago, and this year the competition was held in Ohrid, in Macedonia. There’s one paper, comprising four questions, normally one from each of the agreed olympiad topic areas, with 4.5 hours for students to address them. The contest was sat this morning, and I’m going to say quite a bit about the geometric Q2, and a little bit about Qs 1 and 3 also. In all cases, this discussion will include most of a solution, with some commentary, so don’t read these if you are planning to try the problems yourself.

I’m not saying anything about Q4, because I haven’t solved it. (Edit: I have solved it now, so will postpone Q2 until later today.)

Question One

Find all ordered pairs of positive integers (x,y) such that

x^3+y^3=x^2+42xy+y^2.

The first thought is that if either of x or y is ‘large’, then the LHS is bigger than the RHS, and so equality can’t hold. That is, there are only finitely many solutions. The smallest possible value of y is, naturally, 1, and substituting y=1 is convenient as then y^2=y^3, and it’s straightforward to derive x=7 as a solution.

Regarding the non-existence of large solutions, you can make this precise by factorising the LHS as

(x+y)(x^2-xy+y^2) = x^2+42xy+y^2.

There are 44 terms of degree two on the RHS, and one term of degree in the second bracket on the LHS. With a bit of AM-GM, you can see then that if x+y>44, you get a contradiction, as the LHS will be greater than the RHS. But that’s still a lot of possibilities to check.

It struck me that I could find ways to reduce the burden by reducing modulo various primes. 2, 3 and 7 all divide 42, and furthermore cubes are nice modulo 7 and squares are nice modulo 3, so maybe that would bring the number of possibilities down. But my instinct was that this wasn’t the right way to use the fact that we were solving over positive integers.

The second bracket in the factorisation looks enough like the RHS, that it’s worth exploring. If we move x^2-xy+y^2 from the right to the left, we get

(x+y-1)(x^2-xy+y^2) = 43xy. (1.1)

Now it suddenly does look useful that we are solving over positive integers, because 43 is a prime, so has to appear as a factor somewhere on the LHS. But it’s generally quite restrictive that x^2-xy+y^2 | 43xy. This definitely looks like something that won’t hold often. If x and y are coprime, then certainly x^2-xy+y^2 and y are coprime also. But actually if x and y have a non-trivial common factor d, we can divide both sides by d^2, and it still holds. Let’s write

x=dm,\quad y=dn,\quad\text{where }d=\mathrm{gcd}(x,y).

Then m^2 -mn+n^2 really does divide 43, since it is coprime to both m and n. This is now very restrictive indeed, since it requires that m^2-mn+n^2 be equal to 1 or 43. A square-sandwiching argument gives m^2-mn+n^2=1 iff m=n=1. 43 requires a little bit more work, with (at least as I did it) a few cases to check by hand, but again only has one solution, namely m=7, n=1 and vice versa.

We now need to add the common divisor d back into the mix. In the first case, (1.1) reduces to (2d-1)=43, which gives (x,y)=(22,22). In the second case, after cancelling a couple of factors, (1.1) reduces to (8d-1)=7, from which (x,y)=(7,1),(1,7) emerges, and these must be all the solutions.

The moral here seemed to be that divisibility was a stronger tool than case-reduction. But that was just this question. There are other examples where case-reduction is probably more useful than chasing divisibility.

Question Three

Find all functions f:\mathbb{N}\rightarrow\mathbb{N} such that

n+f(m) \,\big|\, f(n)+nf(m)

for all m,n\in\mathbb{N}.

What would be useful here? There are two variables, and a function. It would be useful if we could reduce the number of variables, or the number of occurences of f. We can reduce the number of variables by taking m=n, to get

n+f(n) \,\big|\, f(n) [1+n]. (3.1)

From this, we might observe that f(n)\equiv 1 is a solution. Of course we could analyse this much more, but this doesn’t look like a 10/10 insight, so I tried other things first.

In general, the statement that a\,|\,b also tells us that a\,|\, b-ka. That is, we can subtract arbitrary multiples of the divisor, and the result is still true. A recurring trope is that the original b is elegant, but an adjusted b-ka is useful. I don’t think we can do the latter, but by subtracting n^2 +nf(m) from the problem statement, we get

n+f(m) \,\big|\, n^2-f(n). (3.2)

There’s now no m on the RHS, but this relation has to hold for all m. One option is that f(n)=n^2 everywhere, then what we’ve deduced always holds since the RHS is zero. But if there’s a value of n for which f(n)\ne n^2, then (3.2) is a very useful statement. From now on, we assume this. Because then as we fix n and vary m, we need n+f(m) to remain a divisor of the RHS, which is fixed, and so has finitely many divisors. So f(m) takes only finitely many values, and in particular is bounded.

This ties to the observation that f\equiv 1 is a solution, which we made around (3.1), so let’s revisit that: (Note, there might be more elegant ways to finish from here, but this is what I did. Also note, n is no longer fixed as in previous paragraph.)

n+f(n) \,\big|\, f(n) [1+n]. (3.1)

Just to avoid confusion between the function itself, and one of the finite collection of values it might take, let’s say b is a value taken by f. So there are values of n for which

n+b \,\big|\, b(1+n).

By thinking about linear equations, you might be able to convince yourself that there are only finitely many solutions (in n) to this relation. There are certainly only finitely many solutions where LHS=RHS (well, at most one solution), and only finitely many where 2xLHS=RHS etc etc. But why do something complicated, when we can actually repeat the trick from the beginning, and subtract b(n+b), to obtain

n+b \,\big|\, b^2-b.

For similar reasons to before, this is a great deduction, because it means if b\ne 1, then the RHS is positive, which means only finitely many n can satisfy this relation. Remember we’re trying to show that no n can satisfy this relation if b\ne 1, so this is definitely massive progress!

If any of what’s already happened looked like magic, I hope we can buy into the idea that subtracting multiples of the divisor from the RHS is the only tool we used, and that making the RHS fixed gives a lot of information about the LHS as the free variable varies. The final step is not magic either. We know that f is eventually 1. If you prefer “for large enough n, f(n)=1,” since all other values appear only finitely often. I could write this with quantifiers, but I don’t want to, because that makes it seem more complicated than it is. We genuinely don’t care when the last non-1 value appears.

Anyway, since we’ve deduced this, we absolutely have to substitute this into something we already have. Why not the original problem statement? Fix m, then for all large enough n

n+f(m) \,\big|\, 1+nf(m). (3.3)

To emphasise, (3.3) has to hold for all large enough n. Is it possible that f(m)=2? Again, it’s easy to convince yourself not. But, yet again, why not use the approach we’ve used so profitably before to clear the RHS? In fact, we already did this, and called it (3.2), and we can make that work [3.4], but in this setting, because f(m) is fixed and we’re working with variable large n, it’s better to eliminate n, to get

n+f(m)\,\big|\, f(m)^2-1,

again for all large enough n. By the same size argument as before, this is totally impossible unless f(m)=1. Which means that in fact f(m)=1 for all m. Remember ages ago we assumed that f(n) was not n^2 everywhere, so this gives our two solutions: f(n)=1,\, f(n)=n^2.

Moral: choosing carefully which expression to work with can make life much more interesting later. Eliminating as many variables or difficult things from one side is a good choice. Playing with small values can help you understand the problem, but here you need to think about soft properties of the expression, in particular what happens when you take one variable large while holding another fixed.

[3.4] – if you do use the original approach, you get n^2-1 on the RHS. There’s then the temptation to kill the divisibility by taking n to be the integer in the middle of a large twin prime pair. Unfortunately, the existence of such an n is still just a conjecture

Question Four

(Statement copied from Art of Problem Solving. I’m unsure whether this is the exact wording given to the students in the contest.)

On a circular table sit n>2 students. First, each student has just one candy. At each step, each student chooses one of the following actions:

(A) Gives a candy to the student sitting on his left or to the student sitting on his right.

(B) Separates all its candies in two, possibly empty, sets and gives one set to the student sitting on his left and the other to the student sitting on his right.

At each step, students perform the actions they have chosen at the same time. A distribution of candy is called legitimate if it can occur after a finite number of steps.
Find the number of legitimate distributions.

My moral for this question is this: I’m glad I thought about this on the bus first. What I found hardest here was getting the right answer. My initial thoughts:

  • Do I know how to calculate the total number of possibilities, irrespective of the algorithm? Fortunately yes I do. Marbles-in-urns = barriers between marbles on a line (maybe add one extra marble per urn first). [4.1]
  • What happens if you just use technique a)? Well first you can get into trouble because what happens if you have zero sweets? But fine, let’s temporarily say you can have a negative number of sweets. If n is even, then there’s a clear parity situation developing, as if you colour the children red and blue alternately, at every stage you have n/2 sweets moving from red children to blue and vice versa, so actually the total number of sweets among the red children is constant through the process.
  • What happens if you just use technique b)? This felt much more promising.
  • Can you get all the sweets to one child? I considered looking at the child directly opposite (or almost-directly opposite) and ‘sweeping’ all the sweets away from them. It felt like this would work, except if for some parity reason we couldn’t prevent the final child having one (or more, but probably exactly one) sweets at the crucial moment when all the other sweets got passed to him.

Then I got home, and with some paper, I felt I could do all possibilities with n=5, and all but a few when n=6. My conjecture was that all are possible with n odd, and all are possible with n even, except those when none of the red kids or none of the kids get a sweet. I tried n=8, and there were a few more that I couldn’t construct, but this felt like my failure to be a computer rather than a big problem. Again there’s a trade-off between confirming your answer, and trying to prove it.

Claim: If n is even, you can’t achieve the configurations where either the red children or the blue children have no sweets.

Proof: Suppose you can. That means there’s a first time that all the sweets were on one colour. Call this time T. Without loss of generality, all the sweets are on red at T. Where could the sweets have been at time T-1? I claim they must all have been on blue, which contradicts minimality. Why? Because if at least one red child had at least one sweet, they must have passed at least one sweet to a blue neighbour.

Now it remains to give a construction for all other cases. In the end, my proof has two stages:

Step One: Given a configuration, in two steps, you can move a candy two places to the right, leaving everything else unchanged.

This is enough to settle the n odd case. For the even case, we need an extra step, which really corresponds to an initial phase of the construction.

Step Two: We can make some version of the ‘sweeping’ move precise, to end up in some configuration where the red number of children have any number of sweets except 0 or n.

Step one is not so hard. Realising that step one would be a useful tool to have was probably the one moment where I shifted from feeling like I hadn’t got into the problem to feeling that I’d mostly finished it. As ever in constructions, working out how to do a small local adjustment, which you plan to do lots of times to get a global effect, is great. (Think of how you solve a Rubik’s cube for example.)

Step two is notationally fiddly, and I would think very carefully before writing it up. In the end I didn’t use the sweeping move. Instead, with the observation that you can take an adjacent pair and continually swap their sweets it’s possible to set up an induction.

Actual morals: Observing the possibility to make a small change in a couple of moves (Step one above) was crucial. My original moral does still hold slightly. Writing lots of things down didn’t make life easier, and in the end the ideas on the bus were pretty much everything I needed.

[4.1] – one session to a group of 15 year olds is enough to teach you that the canon is always ‘marbles in urns’ never ‘balls’ nor ‘bags’, let alone both.

Advertisements

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!

Antichains in the grid

In the previous post on this topic, we discussed Dilworth’s theorem on chains and antichains in a general partially ordered set. In particular, whatever the size of the largest antichain in a poset, it is possible to partition the poset into exactly that many chains. So for various specific posets, or the directed acyclic graphs associated to them, we are interested in the size of this largest antichain.

The following example turned out to be more interesting than I’d expected. At a conventional modern maths olympiad, there are typically three questions on each paper, and for reasons lost in the mists of time, each student receives an integer score between 0 and 7 per question. A natural question to ask is “how many students need to sit a paper before it’s guaranteed that one will scores at least as highly as another on every question?” (I’m posing this as a straight combinatorial problem – the correlation between scores on different questions will be non-zero and presumably positive, but that is not relevant here.)

The set of outcomes is clearly \{0,1,\ldots,7\}^3, with the usual weak domination partial order inherited from \mathbb{R}^3. Then an antichain corresponds to a set of triples of scores such that no triple dominates another triple. So the answer to the question posed is: “the size of the largest antichain in this poset, plus one.”

In general, we might ask about \{1,2,\ldots,n\}^d, again with the weak domination ordering. This directed graph, which generalises the hypercube as well as our example, is called the grid.

Heuristics for the largest antichain

Retaining the language of test scores on multiple questions is helpful. In the previous post, we constructed a partition of the poset into antichains, indexed by the elements of some maximal chain, by starting with the sources, then looking at everything descended only from sources, and so on. (Recall that the statement that this is possible was referred to as the dual of Dilworth’s theorem.) In the grid, there’s a lot of symmetry (in particular under the mapping x\mapsto n+1-x in every coordinate), and so you end up with the same family of antichains whether you work upwards from the sources or downwards from the sinks. (Or vice versa depending on how you’ve oriented your diagram…) The layers of antichains also have a natural interpretation – each layer corresponds to a given total score. It’s clear a priori why each of these is an antichain. If A scores the same as B overall, but strictly more on the first question, this must be counterbalanced by a strictly lower score on another question.

So a natural guess for the largest antichain is the largest antichain corresponding to some fixed total score. Which total score should this be? It ought to be the middle layer, that is total score \frac{(n+1)d}{2}, or the two values directly on either side if this isn’t an integer. My intuition was probabilistic. The uniform distribution on the grid is achieved by IID uniform distributions in each coordinate, which you can think of as a random walk, especially if you subtract off the mean first. It feels that any symmetric random walk should have mode zero or next-to-zero. Certainly this works asymptotically in a rescaled sense by CLT, and in a slightly stronger sense by local CLT, but we don’t really want asymptotics here.

When I started writing the previous paragraph, I assumed there would be a simple justification for the claim that the middle layer(s) was largest, whether by straight enumeration, or some combinatorial argument, or even generating functions. Perhaps there is, and I didn’t spot it. Induction on d definitely works though, with a slightly stronger hypothesis that the layer sizes are symmetric around the median, and monotone on either side of the median. The details are simple and not especially interesting, so I won’t go into them.

From now on, the hypothesis is that this middle layer of the grid is the largest antichain. Why shouldn’t it, for example, be some mixture of middle-ish layers? (*) Well, heuristically, any score sequence in one layer removes several possibilities from a directly adjacent layer, and it seems unlikely that this effect is going to cancel out if you take some intermediate number of score sequences in the first layer. Also, the layers get smaller as you go away from the middle, so because of the large amount of symmetry (coordinates are exchangeable etc), it feels reasonable that there should be surjections between layers in the outward direction from the middle. The union of all these surjections gives a decomposition into chains.

This result is in fact true, and its proof by Bollobas and Leader, using shadows and compression can be found in the very readable Sections 0 and 1 of [1].

Most of the key ideas to a compression argument are present in the case n=2, for which some notes by Leader can be found here, starting with Proof 1 of Theorem 3, the approach of which is developed over subsequent sections. We treat the case n=2, but focusing on a particularly slick approach that does not generalise as successfully. We also return to the original case d=3 without using anything especially exotic.

Largest antichain in the hypercube – Sperner’s Theorem

The hypercube \{0,1\}^d is the classical example. There is a natural correspondence between the vertices of the hypercube, and subsets of [d]. The ordering on the hypercube corresponds to the ordering given by containment on \mathcal{P}([d]). Almost by definition, the k-th layer corresponds to subsets of size k, and thus includes \binom{d}{k} subsets. The claim is that the size of the largest antichain is \binom{d}{\lfloor d/2 \rfloor}, corresponding to the middle layer if d is even, and one of the two middle layers if d is odd. This result is true, and is called Sperner’s theorem.

I know a few proofs of this from the Combinatorics course I attended in my final year at Cambridge. As explained, I’m mostly going to ignore the arguments using compression and shadows, even though these generalise better.

As in the previous post, one approach is to exhibit a covering family of exactly this number of disjoint chains. Indeed, this can be done layer by layer, working outwards from the middle layer(s). The tool here is Hall’s Marriage Theorem, and we verify the relevant condition by double-counting. Probably the hardest case is demonstrating the existence of a matching between the middle pair of layers when d is odd.

Take d odd, and let d':= \lfloor d/2\rfloor. Now consider any subset S of the d’-th layer \binom{[d]}{d'}. We now let the upper shadow of S be

\partial^+(S):= \{A\in \binom{[d]}{d'+1}\,:\, \exists B\in S, B\subset A\},

the sets in the (d’+1)-th layer which lie above some set in S. To apply Hall’s Marriage theorem, we have to show that |\partial^+(S)|\ge |S| for all choice of S.

We double-count the number of edges in the hypercube from S to \partial^+(S). Firstly, for every element B\in S, there are exactly d’ relevant edges. Secondly, for every element A\in\partial^+(S), there are exactly d’ edges to some element of \binom{[d]}{d'}, and so in particular there are at most d’ edges to elements of S. Thus

d' |S|=|\text{edges }S\leftrightarrow\partial^+(S)| \le d' |\partial^+(S)|,

which is exactly what we require for Hall’s MT. The argument for the matching between other layers is the same, with a bit more notation, but also more flexibility, since it isn’t a perfect matching.

The second proof looks at maximal chains. Recall, in this context, a maximal chain is a sequence \mathcal{C}=B_0\subset B_1\subset\ldots\subset B_d where each B_k:= \binom{[d]}{k}. We now consider some largest-possible antichain \mathcal{A}, and count how many maximal chains include an element A\in\mathcal{A}. If |A|=k, it’s easy to convince yourself that there are \binom{d}{r} such maximal chains. However, given A\ne A'\in\mathcal{A}, the set of maximal chains containing A and the set of maximal chains containing A’ are disjoint, since \mathcal{A} is an antichain. From this, we obtain

\sum_{A\in\mathcal{A}} \binom{d}{|A|} \le d!. (**)

Normally after a change of notation, so that we are counting the size of the intersection of the antichain with each layer, this is called the LYM inequality after Lubell, Yamamoto and Meshalkin. The heuristic is that the sum of the proportions of layers taken up by the antichain is at most one. This is essentially the same as earlier at (*). This argument can also be phrased probabilistically, by choosing a *random* maximal chain, and considering the probability that it intersects the proposed largest antichain, which is, naturally, at most one. Of course, the content is the same as this deterministic combinatorial argument.

Either way, from (**), the statement of Sperner’s theorem follows rapidly, since we know that \binom{d}{|A|}\le \binom{d}{\lfloor d/2\rfloor} for all A.

Largest antichain in the general grid

Instead of attempting a proof or even a digest of the argument in the general case, I’ll give a brief outline of why the previous arguments don’t transfer immediately. It’s pretty much the same reason for both approaches. In the hypercube, there is a lot of symmetry within each layer. Indeed, almost by definition, any vertex in the k-th layer can be obtained from any other vertex in the k-th layer just by permuting the labels (or permuting the coordinates if thinking as a vector).

The hypercube ‘looks the same’ from every vertex, but that is not true of the grid. Consider for clarity the n=8, d=3 case we discussed right at the beginning, and compare the scores (7,0,0) and (2,2,3). The number of maximal chains through (7,0,0) is \binom{14}{7}, while the number of maximal chains through (2,2,3) is \binom{7}{2, 2,3}\binom{14}{4,5,5}, and the latter is a lot larger, which means any attempt to use the second argument is going to be tricky, or at least require an extra layer of detail. Indeed, exactly the same problem arises when we try and use Hall’s condition to construct the optimal chain covering directly. In the double-counting section, it’s a lot more complicated than just multiplying by d’, as was the case in the middle of the hypercube.

Largest antichain in the d=3 grid

We can, however, do the d=3 case. As we will see, the main reason we can do the d=3 case is that the d=2 case is very tractable, and we have lots of choices for the chain coverings, and can choose one which is well-suited to the move to d=3. Indeed, when I set this problem to some students, an explicit listing of a maximal chain covering was the approach some of them went for, and the construction wasn’t too horrible to state.

[Another factor is that it computationally feasible to calculate the size of the middle layer, which is much more annoying in d>3.]

[I’m redefining the grid here as \{0,1,\ldots,n-1\}^d rather than \{1,2,\ldots,n\}^d.]

The case distinction between n even and n odd is going to make both the calculation and the argument annoying, so I’m only going to treat the even case, since n=8 was the original problem posed. I should be honest and confess that I haven’t checked the n odd case, but I assume it’s similar.

So when n is even, there are two middle layers namely \frac{3n}{2}-2, \frac{3n}{2}-1 (corresponding to total score 10 and total score eleven in the original problem). I calculated the number of element in the \frac{3n}{2}-1 layer by splitting based on the value of the first coordinate. I found it helpful to decompose the resulting sum as

\sum_{k=0}^{n-1} = \sum_{k=0}^{\frac{n}{2}-1} + \sum_{k=\frac{n}{2}}^{n-1},

based on whether there is an upper bound, or a lower bound on the value taken by the second coordinate. This is not very interesting, and I obtained the answer \frac{3n^2}{4}, and of course this is an integer, since n is even.

Now to show that any antichain has size at most \frac{3n^2}{4}. Here we use our good control on the chain coverings in the case d=2. We note that there is a chain covering of the (n,d=2) grid where the chains have 2n-1, 2n-3,…, 3, 1 elements (%). We get this by starting with a maximal chain, then taking a maximal chain on what remains etc. It’s pretty much the first thing you’re likely to try.

Consider an antichain with size A in the (n,d=3) grid, and project into the second and third coordinates. The image sets are distinct, because otherwise a non-trivial pre-image would be a chain. So we have A sets in the (n,d=2) grid. How many can be in each chain in the decomposition (%). Well, if there are more than n in any chain in (%), then two must have been mapped from elements of the (n,d=3) grid with the same first coordinate, and so satisfy a containment relation. So in fact there are at most n image points in any of the chains of (%). So we now have a bound of n^2. But of course, some of the chains in (%) have length less than n, so we are throwing away information. Indeed, the number of images points in a given chain is at most

\max(n,\text{length of chain}),

and so the number of image points in total is bounded by

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

where there are n/2 copies of n in the first half of the sum. Evaluating this sum gives \frac{3n^2}{4}, exactly as we wanted.

References

[1] – Bollobas, Leader (1991) – Compressions and Isoperimetric Inequalities. Available open-access here.

IMO 2016 Diary – Part Four

A pdf of this report is also available here.

Thursday 14th July

I have now spent a while thinking about square-free n in Q3 after rescaling, and I still don’t know what the markscheme should award it. I therefore request that Joe and Warren receive the same score as each other, and any other contestant who has treated this case. In my opinion this score should be at most one, mainly as a consolation, but potentially zero. However, we are offered two, and after they assure me this is consistent, I accept.

There is brief but high drama (by the standards of maths competitions) when we meet Angelo the Australian leader, who confirms that he has just accepted one mark for almost the same thing by his student Johnny. A Polish contestant in a similar situation remains pending, so we all return for a further meeting. I’m unconvinced that many of the coordinators have read all the scripts in question, but they settle on two for everyone, which is consistent if generous. The only drama on Q5 is the ferocious storm that sets in while I’m making final notes in the plaza. Again though, coordinator Gabriele has exactly the same opinion on our work as Geoff and I, apart from offering an additional mark for Lawrence’s now slightly damp partial solution.

And so we are finished well before lunch, with a total UK score of 165 looking very promising indeed. I’m particularly pleased with the attention to detail – Jacob’s 6 on Q4 is the only mark ‘dropped’, which is brilliant, especially since it hasn’t come at the expense of the students’ usual styles. We’ll have to wait until later to see just how well we have done.

It would be nice to meet the students to congratulate them in person, but they are with Jill on the somewhat inaccessible Victoria Peak, so instead I take a brief hike along the trail down the centre of HK Island, ending up at the zoo. This turned out to be free and excellent, though I couldn’t find the promised jaguar. There was, however, a fantastic aviary, especially the striking flock of scarlet ibis. A noisy group of schoolchildren are surrounding the primates, and one lemur with an evil glint in his eye swings over and languidly starts an activity which elicits a yelp from the rather harried teacher, who now has some considerable explaining to do.

With 1000 people all returning to UST at roughly 6.30, dinner is not dissimilar to feeding time at the zoo, and afterwards various leaders lock horns during the final jury meeting. Two countries have brought an unresolved coordination dispute to the final meeting, and for the first time since I became deputy leader, one of them is successful. Congratulations to the Koreans, who now have a third student with a highly impressive perfect score. Andy Loo and Geoff chair the meeting stylishly and tightly, and although there are many technical things to discuss, it doesn’t drag for too long. Eventually it’s time to decide the medal boundaries, and the snazzy electronic voting system makes this work very smoothly. I feel the gold and bronze cutoffs at 29 and 16 are objectively correct, and the 50-50 flexibility at silver swings towards generosity at 22. We can now confirm the UK scores as:

UKscoresThis is pretty much the best UK result in the modern era, placing 7th and with a medal tally tying with the famous food-poisoning-and-impossible-geometry IMO 1996 in India. But obviously this is a human story rather than just a 6×6 matrix with some summary statistics, and Harvey in particular is probably looking at the world and thinking it isn’t fair, while Warren’s gold is the ideal end to his four years at the IMO, two of which have ended one mark short. The American team are pretty keen to let everyone know that they’ve placed first for the second year in succession, and their remarkable six golds will hopefully allow scope for some good headlines. There is much to talk about, celebrate and commiserate, and this continues late into the night.

Friday 15th July

Our morning copy of the IMO Newsletter includes an interview with Joe, with the headline ‘Meh’. Frank Morgan has rather more to say, which is good news, since he’s delivering the IMO lecture on Pentagonal Tilings. He discusses the motivation of regular tilings where the ratio Perimeter/Area is minimised, starting from questions about honeycombs raised by the Roman author Varro! We move onto more mathematical avenues, including the interesting result of L’Huilier that given a valid set of angles, the associated polygon with minimal Perimeter/Area has an incircle, and the corresponding result for in-n-spheres in higher dimension. A brief diversion to the beach on the way home is punctuated with attempts to project the hyperbolic plane onto the sand.

The day’s main event is the closing ceremony, held at the striking Hong Kong Convention Centre. As usual, the adults and our students have been vigorously separated for the journey. As I arrive, it seems the UK boys have been directing a massed gathering behind the EU flag on stage, while the non-European teams are divided into two sides in a giant paper aeroplane dogfight. All attempts by the organisers to quash this jocularity are being ignored, and after bringing everyone here two hours early, I have minimal sympathy. Geoff sits on a secluded bench, and agrees to the many selfie requests from various teams with regal if resigned tolerance.

The ceremony is started by a fantastically charismatic school brass band, and proceeds with some brief speeches, and more astonishing drumming. Then it’s time to award the medals. Lawrence and Jacob get to go up together among the clump of 24-scorers, while Kevin from Australia does an excellent job of untangling his flag and medal while keeping hold of the ubiquitous cuddly koala. Neel has been threatened with death if he appears on stage again with an untucked shirt, but no direction is required for his and Warren’s smiles as they receive the gold medallists’ applause.

P1010513 (3)Afterwards, there is a closing banquet. We get to join British coordinators James and Joseph for a climate-defying carrot soup, followed by a rare diversion onto Western carbohydrates accompanying what is, for many of us, a first taste of caviar. Both Geoff and the American team are forced to make speeches at no notice. It is all generally rather formal, and fewer photographs are taken than usual. An attempt to capture Joe and Harvey looking miserable results in one the biggest grins of the evening. The UK and Australian teams have a thousand stickers and micro-koalas to give out as gifts, and some of the attempts at this descend into silliness. All clothing and body parts are fair game, and Jacob makes sure that Geoff is fully included. The UK and Australian leaders, variously coated, retreat from the carnage to the relative safety of our top-floor balcony as the IMO drifts to an end, until midnight, when it seems sensible to find out what the students are up to.

Saturday 16th July

This is what the students are up to. When we arrived at UST last week, everyone was given food vouchers to redeem at the campus’s various restaurants. Very very many of these are left over, and, despite the haute cuisine on offer earlier, people are hungry. They have therefore bought McDonalds. And I mean this literally. Animated by Jacob and American Michael, they have bought the entire stock of the nearest branch. If you want to know what 240 chicken nuggets looks like, come to common room IX.1, because now is your chance. Fortunately our team have made many friends and so after the Herculean task (I make no comment on which Herculean labour I feel this most resembles) of getting it to their common room, pretty much the entire IMO descends to help. Someone sets up a stopmotion of the slow erosion of the mountain of fries, while the usual card games start, and a group around a whiteboard tries to come up with the least natural valid construction for n=9 on Q2. Around 3.30am everything is gone, even the 30 Hello Kitties that came with the Happy Meals, and we’re pre-emptively well on the way to beating jetlag.

I wake up in time to wave Geoff off, but he’s been bumped to an earlier bus, so the only thing I see is Lawrence and colleagues returning from a suicidal 1500m round the seaside athletics track. Our own departure is mid-morning, and on the coach the contestants are discussing some problems they’ve composed during the trip. They’ll soon be able to submit these, and by the sounds of it, anyone taking BMO and beyond in 2018 has plenty to look forward to. Jacob has already mislaid his room key and phone, and at the airport he’s completed the hat-trick by losing one of the two essential passport insert pages. Fortunately, it turns out that he’s lost the less essential one, so we can clear security and turn thoughts towards lunch.

Jill has given me free licence to choose our dim sum, so the trip ends with pork knuckle and chicken feet. Our aim is to stay awake for the whole flight, and Neel helps by offering round copies of a Romanian contest from 2010, while I start proof-reading. By the time they finish their paper, many rogue commas have been mercilessly expunged. It should be daylight outside, but the windows are all shut, and by the ninth hour time starts to hang drowsily in a way that combinatorial geometry cannot fix, and so the mutual-waking-up pact kicks in, aided by Cathay Pacific’s unlimited Toblerone. Winding through Heathrow immigration, Joe unveils his latest airport trick of sleeping against vertical surfaces. We diverge into the non-humid night.

Reflection

IMG_0468 original (2)There’s a great deal more to life and mathematics than problem-solving competitions, but our contestants and many other people have worked hard to prepare for IMO 2016 over the past months (and years). So I hope I’m allowed to say that I’m really pleased for and proud of our UK team for doing so well! The last three days of an IMO are very busy and I haven’t had as much time as I’d have liked to talk in detail about the problems. But I personally really liked them, and thought the team showed great taste in choosing this as the British annus mirabilis in which to produce lots of beautiful solutions.

But overall, this is really just the icing on the cake of a training progamme that’s introduced lots of smart young people to each other, and to the pleasures of problem-solving, as well as plenty of interesting general mathematics. I have my own questions to address, and (unless I’m dramatically missing something) these can’t be completed in 4.5 hours, but as ever I’ve found the atmosphere of problem discussion totally infectious, so I hope we are doing something right.

Lawrence and Warren are now off to university. I’m sure they’ll thrive in every way at this next stage, and hopefully might enjoy the chance to contribute their energy and expertise to future generations of olympiad students. The other four remain eligible for IMO 2017 in Brazil, and while they will doubtless have high personal ambitions, I’m sure they’ll also relish the position as ideal role models for their younger colleagues over the year ahead. My own life will be rather different for the next two years, but our camp for new students is held in my no-longer-home-town Oxford in a few weeks’ time, and I’m certainly feeling excited about finding some new problems and doing as much as possible of the cycle all over again!

IMO 2016 Diary – Part Three

Sunday 10th July

I’m awake at 6am and there’s nothing to do, so take a short run along the edge of the bay. I meet an old lady singing along to a walkman (yes, really) while doing taichi. She encourages me to join and it seems rude to refuse. Suffice it to say I’m as grateful no video evidence exists as she should be that no audio recording was made. Six-hundred mathematicians queueing for powdered eggs seems like an unwelcome start to the day, so we are self-catering. The guides have been commanded to show every student how to find their place in the exam hall, and I approve of Allison’s contempt for the triviality of this task.

The main event of the day is the opening ceremony, held at the Queen Elizabeth stadium in the centre of Hong Kong Island. To no-one’s surprise, this involves a lot of time waiting around in the stifling UST plaza, which the students use to take a large number of photographs. The UK and Australian boys are smartly turned out as usual, but the polyester blazers are rather ill-suited to this tropical conditions, so we invoke Red Sea rig until air conditioning becomes available. The Iceland team are particularly keen to seek out the English members for reasons connected to a football match of which Neel proudly claims total ignorance. I picked up an EU flag for next-to-nothing last Friday, and now Jacob and Warren prove very popular as they circulate inviting our (for now) European colleagues to join us behind the stars.

The deputies are segregated in an upper tier and obliged to watch a rehearsal of the parade. Some of the organisers have a confused interpretation of the IMO roles. I still have some of the uniform with me, but an official says it is literally impossible for me to give it to the team. She is small and Joe Benton can catch flying ties as well as colds, so it turns out to be literally entirely possible, but for my trouble I get called ‘a very bad boy’.

Many hours after we left our rooms, the ceremony starts, and is actually very good, with a handful of well-chosen speeches, a mercifully quickfire parade of teams, and musical interludes from a full symphony orchestra, with various traditional and non-traditional percussion. The new IMO song Every day in love we are one involves a B section accompanied by a melange of watercooler bottles, but despite its catchy conclusion about maths, friendship and beyond, I suspect it may not trouble the top of the charts.

Monday 11th July

It’s the morning of the first IMO paper, and you can feel both the excitement and the humidity in the air. Some of our boys are looking a bit under the weather, but we know from past experience that the adrenaline from settling down in a room of 600 young contestants who’ve been preparing for exactly this can carry them through anything. I skip an excursion in order to receive a copy of the contest paper. Security is tight, and the deputies who have chosen this option are locked in a lecture theatre for two hours, and our bathroom visits monitored with commendable attention to detail. I guess that the combinatorial second problem is most likely to provoke immediate discussion, so I spend my time working through the details of the argument, just in time to meet our contestants when their 4.5 hours are up.

Q3 has been found hard by everyone, and Q2 has been found hard by other countries. Harvey’s kicking himself for drawing the wrong diagram for the geometry, an error that is unlikely to improve Geoff’s mood when he receives the scripts later today. Apart from that, we have a solid clutch of five solutions to each of the first two problems, and various nuggets of progress on the final problem, which is an excellent start. Several of the team are itching to keep trying to finish Q3, but the campus is likely to be annoying hotbed of spurious gossip all day, so Allison and I take them out. The very convenient MTR takes us under the harbour while the students and I debate the usefulness of the square-free case, and how well it is preserved under rescaling so that the circumcentre is a lattice point.

As we emerge above ground, Jacob is entranced by the live-action Finding Dory playground at Causeway Bay, and we toy with buying a pig’s trotter from a nearby market, but not even Lawrence is feeling adventurous enough with another exam tomorrow. We travel over to Kowloon via double-decker tram and ferry, and fortified by ice cream, take lots of photographs of the unique HK skyline, where even the giant waterfront office towers are dwarfed by Victoria Peak, which the contestants will visit while I’m marking. On our return journey, some of the team are impressed by the HK rush hour, indicating that they’ve clearly never tried to change line at Leicester Square around 6pm on a Friday…

Tuesday 12th July

Another morning, another trek uphill to a 4.5 hour exam. Time passes rapidly, especially now I’ve worked out how to order coffee without the ubiquitous condensed milk. The security arrangements concerning the deputies’ copies of the paper have been increased even further, but the IMO photographers have outdone themselves, and published on Instagram some pictures of the exam room with a level of crispness such that it’s clear the paper includes no geometry, and after finally getting hold of a proper hard copy, it looks like a paper which the UK team should really enjoy.

As so often after IMO papers, there is a range of reactions. Lawrence is unsure whether he presented his exemplar polynomial in a form that actually works. Joe knows and I know that he could easily have got at least 35 on these papers, but after over-meta-thinking himself on Q5, this isn’t his year. Like Aeneas gazing on the ruins of Troy, sunt lacrimae rerum, but also plans for new foundations. By contrast, Harvey has atoned for yesterday’s geometric lapse with what sounds like a perfect score today. Warren and Neel seem to be flying overall, and are doing a good job of keeping their excitement under control while the others muse. There’s plenty to think about, and Geoff has now arrived bearing yesterday’s scripts and several novels’ worth of anecdotes from the leaders’ site.

Before getting down to business, it feels sensible to walk off the Weltschmerz, and provide an outlet for joy in the nearby Clearwater Bay country park. There’s a long trail all over the New Territories, and we join it for a brief but purposeful stroll up through the light jungle and along the ridge. We’re confident we didn’t find the global maximum, but we find a couple of local maxima with great views out around the coastline, which seems to have Hausdorff dimension slightly greater than 1. We see some enormous spiders (though the Australians are substantially less impressed) before ending up an uncontroversial minimum where Jill has bedded in with merciful bottles of water on the beach. To say we are sticky doesn’t even begin to cover it but, crucially, we are no longer consumed by the morning’s events.

The UK boys are now masters of the complicated UST food court ordering process, and Warren endears himself to Geoff by producing a steaming bowl of spicy ramen as if by magic. The contestants have a ‘cultural night’, which apparently includes a greater number of hedge fund representatives than one might have expected. For me, it’s a night in with Geoff, green tea and the scripts for Q2. Joe and Neel have filled fourteen pages between them checking a construction in glorious detail, a step which Harvey has described in its entirety with the words ‘glue them together’. Overall, they are complicated but precise, and I have few concerns, so it’s only necessary to burn the candle at one end.

Wednesday 13th July

It’s time for coordination, where Geoff and I agree the UK marks with a team of local and international experts. The scheduling has assigned us the Q1 geometry early in the morning, which is a clear case of five perfect solutions, so we move to Q2. Coordinator Stephan seems very well-prepared for the UK scripts, so again we are finished in a matter of minutes. This allows us to bring forward our discussion of Q4. Jacob has made several small errors, all of which could be fixed by attacking his script with a pair of scissors and some glue. I believe the mark scheme should award this 4+2, and coordinator Juan thinks it should be 5+1. We are both open to each other’s interpretations, and have at least basic proficiency in addition, so again there is little need for debate.

The early evening brings the main challenge of the day, Q6, at which the UK has excelled. Our frogmaster Geoff has listed marks for five of our attempts, but the final script belonging to Joe has generated only the comment ‘magical mystery tour’. His solution to part a) diverges substantially from the most natural argument, and indeed involves wandering round the configuration, iteratively redirecting lines [1]. I am eventually convinced by the skeleton of the argument, though unconvinced I could complete the details in the finite time available.

We discuss the script with Lisa Sauermann, who explains some of the main challenges [2]. After a short pause for thought, we’re convinced by Lisa’s suggestion of equivalence with a point on the conventional markscheme. It would have been nice to have had more time to think about the subtleties myself, but this was some really interesting maths and we pack up for the day feeling very impressed with the quality of coordination here so far.

We and the coordinators are also very impressed with the quality of Harvey’s art. As a result, we now have an answer to the question ‘What should you do if you finish the IMO two hours early?’ Harvey’s answer at least is to draw a diagram of the Q6 configuration in the case n=3, where at each of the intersection points with the outer boundary stands a member of the current UK team. Precisely UNKs 1, 3 and 5 are wearing a frog. The real life sextet have been taken by Allison to Disneyland today, so some are potentially now wearing a princess. But while the contestants can let it go now, it’s off to work I go, as there’s still two sets of scripts left to ponder.

Harvey Q6[1] The mechanism for this redirection is neither canonical nor explained, and even in the best setup I can come up with in an hour or so of trying a huge class of diagrams, exactly half of the indices in the resulting calculation are off by \pm 1. The pressure of IMO Day Two can indeed derail even the most well-prepared contestants.

[2] There is a non-trivial difficulty when the area enclosed by our path is concave, as then some intersection points on the path arise from lines which are also part of the path. Handling the parity of such points looks easy once you’ve been shown it, but is definitely not obvious.

IMO 2016 Diary – Part Two

Wednesday 6th July

After starting the third exam, Mike, Jo and I go for a walk through some of the smaller villages on the other side of the ridge. Along the way, we pick up a bunch of local rascals who ask us, via their English-speaking henchman, many questions about basketball, and the colour of Mike’s shoes. Jo asks him why they aren’t in school, but this remains shrouded in mystery. Partly as a means of escape, we take a detour through a grove of the famous Tagaytay pineapples, which are indeed a striking crimson just before they ripen fully. I’m nervous about beard tanlines so am looking for a barber, but it seems I’m one of only two people in the Philippines with facial hair. (The other is Neel, who is adamant that his school approves of the ‘Wild man of Borneo’ look.)

We return to find that the students have been issued with cake. Its icing is impossible to manage without a fork. It is also entirely purple, and Lawrence describes it as ‘tasting of air’. None of this has distracted the UK students, who all solve the first two problems perfectly, which bodes well for the IMO itself, now less than a week away. To fill some time and provide a brief variation from the constant problem-solving, I give a talk about correlation and graphs, based on a subsubsubsection of my thesis and for now, fortunately no-one finds any logical holes.

Thursday 7th July

To add variety, today the two teams have set each other a paper, which they will spend the afternoon marking. It transpired late last night that the hotel has no means of printing or photocopying documents, and we haven’t brought copies of tomorrow’s final exam. So today’s paper has been painstakingly written on whiteboards, and some of the adults set off round Tagaytay in search of a working printer. The mode of transport is the ‘tricycle’, a small motorcycle with one place behind the rider and two in a bone-shaking pillion enclosed within a lace curtain. Availability of tricycles is infinite, availability of photocopiers is positive but small, and availability of printers is zero. We’ll be going for the handwritten, personal touch.

Both teams have chosen their papers so as to get some fiddly answers, and both teams have helped the exercise by writing some rubbish. Mostly it is all correct on close inspection, but much requires serious digestion, and gives the students at least a flavour of what Andrew and I have to endure on a daily basis. The Australians have rephrased a combinatorial problem in terms of Neel wandering through security checks at an airport, and the UK boys have proved that whatever happens here, a gold medal at the International Metaphor-Extending Olympiad seems inevitable.

Courtesy of Australian student Wilson, a penchant for fedoras has swept through the camp. Joe and Harvey look like extras in an ultra-budget production of Bugsy Malone. Our mock coordination has taken most of the afternoon, so we have not been tracking the imminent supertyphoon Nepartak as carefully as we ought, but at least the new headwear fashion offers some protection from the elements.

Friday 8th July

This morning is the final training exam, and in keeping with tradition is designated the Mathematical Ashes. Whichever team wins gets to keep an impressive urn, filled with the charred remains of some old olympiad scripts. The urn is quite heavy, so for the Cathay Pacific weight restrictions, it would be convenient for me if Australia won this year. The lack of an actual Ashes this year renders the competition all the more important in some people’s eyes, though if there were a test match here today, the covers would be on all day as the typhoon squalls.

The Ashes paper is the original Day Two paper [1] from IMO 2015. The problems are supposed to be secret until after this year’s IMO (exactly because of events like the one we are running) but the entire shortlist has been released overnight on the internet. Fortunately none of the students have been checking the relevant forum over breakfast, but ideally people will curb their admirable enthusiasm and follow the actual rules in future years. I mark the second problem, a fiddly recursive inequality, which invites many approaches, including calculus of varying rigour. Whatever the outcome, both teams have done a good job here.

For dinner, we are hosted by Dr Simon Chua, and some of his colleagues involved in the Philippines maths enrichment community, who suggested this location, and helped us set up this camp. We are treated to various Philippine dishes, including suckling pig and squid in its own ink, with a view of sunset across the lake as the storm clears. We’re very grateful to Simon, Joseph and their colleagues for tonight and their help and advice in advance.

We finish the marking after dinner, and the UK has consolidated our position on the third question, including a superb 21/21 for Warren on a genuinely hard paper, and we have won 82-74. It is late, everyone is tired, and there is packing required, so the celebrations are slightly muted, though it gives Jacob an excellent opportunity to lose his room key again, an alternative competition in which he is certainly the unique gold medallist. We transfer to the main event in Hong Kong early tomorrow, so it’s an early night all round.

[1] – Potted summary: some copies of this paper were accidentally released before they should have been, and so the paper had to be re-set.

Saturday 9th July

After a disturbed night, it has been vociferously recommended that we leave at 6am to beat the Manila traffic, with the result that we have four hours at the airport. I try to remain stoic, with difficulty. Joe practises sleeping on every available surfaces while the rest of us have a sudden enthusiasm to solve N8 from last year’s shortlist. It turns out the UKMT travel agent has outdone themselves, and booked half the group in premium economy, and half in regular economy, though the only real difference seems to be armrest width.

We are met in HK by Allison, our local guide for the week, and escorted onto coaches across from the airport on Lantau island to the University of Science and Technology in the New Territories. The check-in process is comprehensive: I sign and initial to confirm that they have correctly provided us with seven laptop sleeves, and then repeat for an infinite supply of other branded goods. Finally, we are allowed out to explore the spectacular campus, which stretches steeply down to Clearwater Bay. It is a novelty to take elevators up a total of 37 floors, and arrive on something called ‘Ground Floor’.

After a confusingly-managed dinner at the student cafeteria, a few of us head out to look at the nearby neighbourhood of Hang Hau. We pass the olympic velodrome, which gives Lawrence a good opportunity to explain gearing to those among his colleagues who do not naturally seek out applied mathematics. We return to find that Harvey decided to go to sleep before working out how to turn on his air conditioning. In humid hindsight, this was a poor strategy, as this was one of HK’s hottest days since records began. We have arrived back at the perfect time to watch the awesome thunderstorm from dry safety, which hopefully isn’t an omen of terrible things to follow in the contest, which starts on Monday.

IMO 2016 Diary – Part One

Friday 1st July

It’s my last morning as an Oxford resident, and I have to finish the final chapter of my thesis, move out of my flat, print twenty-four boarding passes, and hurtle round town collecting all the college and department stamps on my pre-submission form 3.03 like a Pokemon enthusiast. Getting to Heathrow in time for an early evening flight seems very relaxed by comparison, even with the requirement to transport two boxes of IMO uniform. Because I wasn’t paying very much attention when I signed off the order, this year we will be wearing ‘gold’, but ‘lurid yellow’ might be a better description. Hopefully the contestants might have acquired some genuinely gold items by the time we return to this airport in two weeks.

Saturday 2nd July

Our flight passes rapidly. I proved an unusual function was locally Lipschitz, watched a film, and slept for a while. Others did not sleep at all, though I suspect they also did not prove any functions were locally Lipschitz. The airport in Hong Kong is truly enormous; for once the signs advertising the time to allow to get to each gate have a tinge of accuracy. We have plenty of time though, and there is substantial enthusiasm for coffee as we transfer. Cathay Pacific approach me with a feedback form, which turns out to include 130 detailed questions, including one concerning the ‘grooming’ of the check-in staff, while we all collectively tackle an inequality from the students’ final sheet of preparatory problems.

Before long though, we have arrived in Manila, where Jacob is uncontrollably excited to receive a second stamp in his passport, to complement his first from Albania at the Balkan Olympiad last month. As we bypass the city, we get a clear view of the skyscrapers shrouded in smog across the bay, though the notorious Manila traffic is not in evidence today. We pass through the hill country of Luzon Island, the largest of the Philippines and get caught in a ferocious but brief rainstorm, and finally a weekend jam on the lakeside approach to Tagaytay, but despite these delays, the fiendish inequality remains unsolved. I’m dangerously awake, but most of the students look ready to keel over, so we find our rooms, then the controls for the air conditioning, then let them do just that.

Sunday 3rd July

We have a day to recover our poise, so we take advantage of morning, before the daily rain sets in, to explore the area. We’ve come to Tagaytay because it’s high and cool by Philippine standards, so more conducive to long sessions of mathematics than sweltering Manila. We follow the winding road down the ridge to the shore of Taal Lake, where a strange flotilla of boats is docked, each resembling something between a gondola and a catamaran, waiting to ferry us to Taal Volcano, which lies in the centre of the lake. The principal mode of ascent from the beach is on horseback, but first one has to navigate the thronging hordes of vendors. Lawrence repeatedly and politely says no, but nonetheless ends up acquiring cowboy hats for all the students for about the price of a croissant in Oxford.

Many of us opt to make the final climb to the crater rim on foot, which means we can see the sulphurous volcanic steam rising through the ground beside the trail. From the lip we can see the bright green lake which lies in the middle of the volcano, which is itself in the middle of this lake in the middle of Luzon island. To the excitement of everyone who likes fractals, it turns out there is a further island within the crater lake, but we do not investigate whether this nesting property can be extended further. After returning across the outer lake, we enjoy the uphill journey back to Tagaytay as it includes a detour for a huge platter of squid, though the van’s clutch seems less thrilled. Either way, we end up with a dramatic view of an electrical storm, before our return to the hotel to await the arrival of the Australians.

Monday 4th July

Morning brings the opportunity to meet properly the Australian team and their leaders Andrew, Mike and Jo. We’ve gathered in the Philippines to talk about maths, and sit some practice exams recreating the style of the IMO. The first of these takes place this morning, in which the students have 4.5 hours to address three problems, drawn from those shortlisted but unused for last year’s competition.

After fielding a couple of queries, I go for a walk with Jo to the village halfway down the ridge. On the way down, the locals’ glances suggest they think we are eccentric, while on the ascent they think we are insane. About one in every three vehicles is a ‘jeepney’, which is constructed by taking a jeep, extending it horizontally to include a pair of benches in the back, covering with chrome cladding, and accessorising the entire surface in the style of an American diner. We return to find that the hotel thinks they are obliged to provide a mid-exam ‘snack’, and today’s instalment is pasta in a cream sauce with salad, served in individual portions under cloches. Andrew and I try to suggest some more appropriate options, but we’re unsure that the message has got across.

I spend the afternoon marking, and the UK have started well, with reliable geometry (it appears to be an extra axiom of Euclid that all geometry problems proposed in 2015/2016 must include a parallelogram…) and a couple of solutions to the challenging number theory problem N6, including another 21/21 for Joe. Part of the goal of this training camp is to learn or revise key strategies for writing up solutions in an intelligible fashion. At the IMO, the students’ work will be read by coordinators who have to study many scripts in many languages, and so clear logical structure and presentation is a massive advantage. The discussion of the relative merits of claims and lemmas continues over dinner, where Warren struggles to convince his teammates of the virtues of bone marrow, a by-product of the regional speciality, bulalo soup.

Tuesday 5th July

The second exam happens, and further odd food appears. Problem two encourages solutions through the medium of the essay, which can prove dangerous to those who prefer writing to thinking. In particular, the patented ‘Agatha Christie strategy’ of explaining everything only right at the end is less thrilling in the realm of mathematics. It’s a long afternoon.

We organise a brief trip to the People’s Park in the Sky, based around Imelda Marcos’s abandoned mansion which sits at the apex of the ridge. In the canon of questionable olympiad excursions, this was right up there. There was no sign of the famous shoe collection. Indeed the former ‘palace’ was open to the elements, so the style was rather more derelicte than chic, perfect for completing your I-Spy book of lichen, rust and broken spiral staircases. Furthermore after a brief storm, the clouds have descended, so the view is reminiscent of our first attempt at Table Mountain in 2014, namely about five metres visibility. A drugged parrot flaps miserably through the gloom. Even the UK team shirts are dimmed.

There is a shrine on the far side of the palace, housing a piece of rock which apparently refused to be dynamited during the construction process, and whose residual scorchmarks resemble the Blessed Virgin Mary. A suggested prayer is written in Tagalog (and indeed in Comic Sans) but there is a man sitting on the crucial rock, and it’s not clear whether one has to pay him to move to expose the vision. Eventually it clears enough to get a tolerable set of team photos. Joe tries to increase the compositional possibilities by standing on a boulder, thus becoming ten times taller than the volcano, so we keep things coplanar for now. Harvey finds a giant stone pineapple inside whose hollow interior a large number of amorous messages have been penned. He adds

\mathrm{Geoff }\heartsuit\,\triangle \mathrm{s}

in homage to our leader, who has just arrived in Hong Kong to begin the process of setting this year’s IMO papers.

Balkan MO 2016 – UK Team Blog Part Two

This short blog records the UK team at the Balkan Mathematical Olympiad 2016, held in Albania. The first part is here. A more mathematical version of this report, with commentaries on the problems, will appear at the weekend.

Sunday 8th May

Gerry and I are separated by 15km, so we can’t work together until this morning, when I also get a chance to see the UK team at their base in Vore, before they are whisked off to a beach. We now have the chance to work on the geometry together, which includes two sensible trigonometric arguments, and a nice synthetic proof only with reference to an inverted diagram. We quickly decide that this isn’t a major error, and aim to schedule our meetings as quickly as possible.

The coordinators for questions 3 and 4 seem very relaxed, and we quickly get exactly what we deserve, plus a spurious extra point for Michael because he used the phrase ‘taxicab metric’ in his rough. Thomas’s trigonometry, especially its bold claim that ‘by geometry, there are no other solutions’ when an expression becomes non-invertible, seems not to have been read entirely critically. Michael’s inverted diagram is briefly a point of controversy, but we are able to get 9 rather than the 7 which was proposed, absurdly for an argument that was elegant and entirely valid in the correct diagram up to directed angles. Question 1 is again rapid, as the coordinators say that the standard of writing is so clear that they are happy to ignore two small omissions. It transpires after discussion with, among others, the Italian leader, that such generosity may have been extended to some totally incorrect solutions, but in the final analysis, everything was fair.

So we are all sorted around 11.30am with a team score of 152, a new high for the UK at this competition. This is not necessarily a meaningful or consistent metric, but with scores of {20,21,22,29,30,30} everyone has solved at least two problems, and the three marks lost were more a matter of luck than sloppiness. Irrespective of the colours of medals this generates, Gerry and I are very pleased. We find a table in the sun, and I return to my introduction while we await progress from the other countries’ coordinations, and our students’ return.

This does not happen rapidly, so I climb the hill behind the hotel up a narrow track. A small boy is standing around selling various animals. Apparently one buys rabbits by the bucket and puppies by the barrel in Albania. Many chickens cross the road, but key questions remain unanswered. From the summit, there is a panorama across the whole Tirana area, and the ring of mountains encircling us. One can also see flocks of swifts, which are very similar to swallows, only about twice as large, and their presence in any volume makes no comment on the arrival of the British summer.

The students return mid-afternoon, and are pleased with their scores. Jamie explains their protracted misadventure with a camp bed in their ‘suite’ of rooms, and Jacob shows off his recent acquisitions: a felt hat, and a t-shirt outlining the border of a ‘greater Albania’. The fact that they didn’t have his size seems not to have been a deterrent, but hopefully the snug fit will discourage him from sporting it in Montenegro, which might lead to a political incident.

Hours pass and time starts to hang heavily as dinner approaches, with no sign of the concluding jury meeting. Finally, we convene at 10pm to decide the boundaries. The chair of the jury reads the regulations, and implements them literally. There’s a clump of contestants with three full solutions, so the boundaries are unusually compressed at 17, 30 and 32. A shame for Thomas on 29, but these things happen, and three full solutions minus a treatment of the constant case for a polynomial is still something to be happy about. Overall, 4 bronze and 2 silvers is a pleasing UK spread, and only the second time we have earned a full set of medals at this competition. The leaders are rushed back to Tirana, but hopefully the teams have enough energy left for celebration!

Monday 9th May

Today is the tutti excursion, but on the way the leaders stop at the city hall to meet the mayor of Tirana. He is new to the office, reminiscent of a young Marlon Brando, and has a bone-crushing handshake. He improvises an eloquent address, and negotiates with flair the awkward silence which follows when the floor is opened for speeches in response. In the end, the Saudi leader and I both say some words of thanks on behalf of the guest nations, and soon we are back on our way south towards Greece. The Albanian motorway is smooth and modern, but we find ourselves competing for space with communist-era windowless buses and the occasional pedestrian leading by hand a single cow.

Our destination is Berat, known as the city of a thousand windows, and home to a hilltop castle complex from which none of the thousand windows are visible. The old orthodox cathedral is now a museum of icons and other religious art, and we get a remarkably interesting tour from a local guide. The highlight is a mosaic representation of the Julian calendar, and we discuss whether the symmetries built into the construction would be more conducive to a geometry or a combinatorics question.

Back in Tirana, we reconverge at the closing ceremony, held in the theatre at a local university for the arts. While we wait, there is a photo montage, featuring every possible Powerpoint transition effect, in which Jacob and his non-standard hat usage makes a cameo appearance. We are then treated to a speech by Joszef Pelikan, who wows the crowd by switching effortlessly into Albanian, and some highly accomplished dancing, featuring both classical ballet and traditional local styles.

The ministry have taken over some aspects of the organisation here, and there is mild chaos when it’s medal time. The leaders are called upon to dispense the prizes, though the UK is snubbed for alphabetic reasons. The end result is that forty students are on stage with neither medals nor any instructions to leave. Eventually it vaguely resolves, though it is a shame there is no recognition for the two contestants (from Serbia and Romania) who solved the final problem and thus achieved a hugely impressive perfect score.

P1000371_compressed

As you can see, the UK team look extremely pleased with themselves, and Michael’s strategy to get to know all the other teams through the medium of the selfie is a storming success. A very large number of photographs are taken, and Thomas is not hiding in at least one of them. The closing dinner is back in Vore, which is very convivial and involves many stuffed vine leaves. Rosie suggests we retire somewhere quieter, but by the time we establish how to leave, she has instead dragged the rest of the team onto the dancefloor, where near-universal ignorance of the step pattern is no obstacle to enjoying the folk music. The DJ slowly transitions towards the more typical Year 11 disco playlist, and Jill feels ‘Hips don’t lie’ is a cue for the adults to leave.

Tuesday 10th May

Our flight leaves at 9pm so we have many hours to fill. It turns out that we have one of the shortest journeys. The Serbians have caught a bus at 3am, while the Cypriots are facing stopovers in Vienna and Paris! It is another beautiful day, so we hire a small van to take us to Lezhe, the hometown of our guide Sebastian, and the nearby beach at Shengjin.

We walk to the tip of the breakwater, and watch some fishermen hard at work, though apparently today is a lean catch. The buildings along the beachfront are a sequence of pastel colours, backing onto another sheer mountain, and we could easily be in Liguria. Jamie is revising for his A2-level physics and chemistry exams, which start at 9am tomorrow morning, and the rest of the team are trying to complete the shortlist of problems from IMO 2007. They progress through the questions in the sand, with a brief diversion as Jacob catches a crab in the shallows with his bare hands for no apparent reason.

After a fish-heavy lunch, we return to Vore, and I’ve run out of subsubsections to amend, so propose another walk into the hills. The animals we meet this time appear not to be for sale. Some scrabbling in the undergrowth is sadly not the longed-for bear or wolf. Many of its colleagues are loitering on the local saddle point, and our Albanian companion Elvis describes them as ‘sons of sheep’, while Renzhi confidently identifies them as cows. They are goats. There is a small but vigorous goatdog, who reacts with extreme displeasure to our attempt to climb to one viewpoint, so Gerry leads us off in another direction up the local version of the north face of the Eiger. We do emerge on the other side, dustier but with plenty of heavily silhouetted photographs.

Then the hour of departure, and time to say goodbye to the organisers, especially Adrian, Matilda and Enkel who have made everything happen, and in a wonderful spirit; and our guide Sebastian, who has set an impossibly high bar for any others to aspire to. We wish him well in his own exams, which start on Thursday! Albania has left a strong positive impression, and it will sit high on my list of places to explore more in the future, hopefully before too many others discover it. The airport affords the chance to spend the final Leke on brandy and figurines of Mother Teresa, and the flight the chance to finish problem N5, and discuss our geometry training regime with Rosie and Jacob as they work through some areal exercises.

2am is not a thrilling time to be arriving in Oxford, and 2.30am is not a thrilling time to be picking up solutions to past papers (and an even less thrilling time to discover that no such solutions have been handed in). But this has been a really enjoyable competition, at which the UK team were delightful company, and performed both strongly and stylishly at the competition, so it is all more than justified. We meet again at half-term in three weeks’ time to select the UK team for the IMO in Hong Kong, and hopefully explore some more interesting mathematics!

Balkan MO 2016 – UK Team Blog Part One

The Balkan Mathematical Olympiad is a competition for high school students from eleven countries in Eastern Europe, hosting on an annually rotating basis. For the 33rd edition it was Albania’s turn to host, and the UK was invited to participate as a guest nation.

A report with more mathematics, less frivolity and minimal chronological monotonicity can be found [SHORTLY].

Wednesday 4th May

I put the finishing touches to another draft of another chapter of my thesis, cajole the Statistics Department printer into issueing eighteen tickets, six consent forms and a terrifyingly comprehensive insurance policy, and head for Gatwick to meet the team. The UK imposes a policy that we will only take anyone to the Balkan MO once, so as to maximise the number of students who get to experience an international competition. The faces aren’t entirely new though – all six attended our winter programme in Hungary over New Year and the recent selection camp in Cambridge. They are showing the right level of excitement: the level that suggests they will enjoy the competition but won’t lose their passports in the next thirty minutes. As a point of trivia, this UK team are all sixth-formers, which, after checking not very carefully, doesn’t seem to have happened for any UK team for a long time, possibly not since 2008 when I was a contestant.

As of February this year, it’s now possible to fly direct to Albania on British Airways, which is a major improvement on the alternatives featuring either a seven-hour layover in Rome, or a nailbiting twenty-five minute interchange in Vienna. A drawback of the diary format is the challenging requirement to say interesting things about flights. In this instance, my principal challenge is to find some leftover room in my seat, as my neighbour’s physique has the same level of respect for the constraining power of armrests as the sea for the battlements of a child’s sandcastle. Across the aisle, Renzhi and Thomas face the twin challenges of a sheet of functional equations I’ve collated, and the well-meaning attempts of cabin attendants and their own neighbours to discuss said functional equations.

Later, over dinner next to Mother Teresa Airport in Tirana, we discuss the role of mathematics in recent films. Based on a sample size of at most two, we decide that `The Man who Knew Infinity’ is slightly better than `The Imitation Game’, partly because the former had fewer mathematical errors, or at least mispronunciations, about which Gerry feels strongly.

Thursday 5th May

The drawback of the new BA route is that it doesn’t run on Thursdays, so we are actually almost a full day early. Morning brings a cloudless summer’s day, and views of the imposing mountains that encircle Tirana. The students have assembled a healthy collection of past problems that they are keen to attempt as practice, and it seems natural to attempt this in a slightly more interesting place than the hotel lobby for at least some of the day.

Our guide Sebastian waves his Blackberry and rapidly conjures up an excursion to Mount Dajti, a small resort two-thirds of the way up a small mountain accessed from suburban Tirana via cable car. We follow a sign that seems to point to the summit, but the trail has distinctly horizontal ambitions. We are rewarded nonetheless with some pleasant views over the mountain range down past enclosed cerulean lakes down to the Adriatic, and even beyond to Italy.

Gerry is concerned about whether our return route is actually taking us where we want to go. He is right to be concerned, but not for that reason. It is the correct direction, but through a military base. Despite this, we make it back to the top of the cable car in the correct number of pieces. There’s the chance to alter this with some diverting activities, namely horse-riding and target-shooting. The targets are balloons, mounted on a clothes line at roughly horse-head-height. We move along.

Several years of attending maths competitions has increased both my ability to solve problems in Euclidean geometry, and also my suspicion of anything with a title like ‘Museum of National History’. I’m going to have to adjust the latter, because the recently-opened Albanian version, called BunkART, was actually excellent. It was housed in the five-level 108-room bunker built into the mountain to protect Enver Hoxha from nuclear attack. The rooms detailed the recent, fragmented history of the country, and were interspersed with aggressively modern art installations. In one basement which used to house the isotope filters, we were treated to a video loop of blood dripping onto barbed wire set to Mahler’s 5th Symphony.

While some regional competitions have adopted the ‘benign dictatorship’ approach to choosing the problems, the Balkan MO still has a problem selection phase. So I separate from the students and spend a pleasant few hours playing around with some of the proposals in the rooftop lounge of the leaders’ hotel on a balmy night in central Tirana.

Friday 6th May

The task for today is to construct a paper. A committee has selected a shortlist of problems, and we have to narrow this down to four, with one from each topic area, with an appropriate range of difficulty. The shortlist definitely contains some gems and some anti-gems, and more thoughts about these can be found in the official report.

The only dramatic moment comes when the Greek leader flourishes a webpage and an old IMO shortlist problem, which does indeed contain a proposed question as a lemma, and so it is rejected. Partly as a result of this, a medium geometry problem is chosen quickly; and the hard combinatorics shortly after lunch, since everyone likes it, and no-one can propose a better alternative. Selecting the final two problems, from number theory and algebra produces several combinatorial challenges in its own right. A rather complicated, multi-round election takes place (in which the UK, as a guest nation, does not get a say), and the final two problems are chosen, and the paper is complete.

Interestingly, this matches exactly the ideal paper I’d been hoping for last night, but with the middle questions the other way round. I think the UK students will enjoy it, and I’ll be very pleased for anyone from any country who solves the final problem. It’s fascinating to talk to the leaders of Bosnia and Montenegro, who discuss in detail why their respective education systems mean they are confident their students will struggle much more with Q3.

P1000166_compressed

In the middle of the selection process, there was a rapid transfer to the students’ site in Vore, 15km away, to attend a brief opening ceremony. There is a warm speech from the deputy minister for education, some brief dancing, and the parade of teams. The wholesaler had a bargain on quartered polo shirts, so, unlike the UK flag they are carrying, our team are invariant under both reflection and rotation.

I am summoned to be an expert on the usage of English to prepare the final version of the paper. I feel that the problem authors have done an excellent job, and there is little work to do except suggest some extra sentence breaks and delete some appearances of the word ‘the’. Pity then the other leaders who return to the Harry Fultz school to translate and approve all the versions in their respective languages. It’s midnight as a I write this, and no sign of their return…

Saturday 7th May

This is what we’ve all come for, as the contestants are transported into Tirana for the 4.5 hours of the competition paper. They are allowed to ask questions of clarification during the first half hour. Twenty-five minutes pass, and we are untroubled, so we smugly conclude we must have achieved a wording with total clarity. In fact, the exam is starting slightly late, and a mild deluge begins, mostly concerning the definition of ‘injective’. Both the era of UK students asking joke questions and UK students asking genuine questions have passed, so I am left in peace.

Somehow, Enkel Hysnelaj has single-handedly produced LaTeX markschemes for all four problems overnight, and these are discussed at some length, though it’s to his credit that they didn’t require even longer. The leaders and deputies are then wheeled off on an excursion. Our destination is Kruje, famous as the hometown of Skenderbeg, the Albanian national hero, and just before that is Fushe-Kruje, famous as the place where George W. Bush’s watch was stolen during an official visit. On the way up to the castle and museum we pass through a bazaar where there is the opportunity to buy a carpet, a felt hat, or a mug decorated with a picture of Enver Hoxha. I will be sure to drop some hints to the UK students about ideal choices of gift for Gerry.

The scripts will be arriving a bit later, so there’s the chance for a wander around Tirana in the early evening sun. My planned trip to the Museum of Secret Surveillance is sadly foiled since it hasn’t yet been opened, but there are several more statues of Skenderbeg to enjoy. The question of why he wears a goat head on his helmet remains open. Since dinner is a mere two hours after another meat-centric five course lunch, I turn my attention to the UK scripts which have just arrived. I glance at questions 1 and 4 and the latter is mostly bare while the former is pointedly well-written. The same applies to question 3. All of our nagging about clear written work has very much been rewarded here. As a personal bonus, I can therefore spare time for a late dinner. My attempt at ordering a quick snack results in about a kilo of ribs with the ubiquitous lemons, but will hopefully deflate slightly during coordination in the morning.

IMO 2015 Diary – Part Four

Sunday 12th July

I spend many hours reading the students’ scripts for the medium questions 2 and 5. Psychologically, this solitude is quite a sudden shift after so many days of constant group interaction. Although only one of the twelve solutions is complete, I’m really pleased with how everyone has presented their progress. We’ve spoken a lot at the camps during the year about how to write up maths under various kinds of pressure so that it is intelligible to other human beings. All the boys have been very clear this year, so they should get plenty of marks and coordinating won’t cause much drama.

By comparison with the student site, the leaders’ hotel has slightly better views, slightly better food, and an even more appalling lift availability algorithm. When the work is done for the day, I meet Jill and the students at the night market, where Lawrence is sharing round a packet of fried giant crickets. They have enjoyed their excursion, especially the visit to an umbrella and other handicraft factory, where it seems they did their best to re-inflate the Thai economy. Neel has a three foot wide fan, hand-painted in a style evoking My Little Pony. While it doesn’t quite conjure the demure grace of, say, Callas as Madam Butterfly, it does induce a billowing wind tunnel effect, which is appreciated in the back of our taxi.

Monday 13th July

Today is the main day of coordination, when Geoff and I meet local markers to agree the UK students’ scores. Over breakfast we decide to ask for a solitary 1 for Joe’s hastily-written summary of Q6 in our first meeting. After some not especially thrilling wrangling about the meaning of the phrases ‘combinatorial description’ and ‘non-trivial progress’, we get what we want without having to deploy my carefully-worded speech.

This will turn out to be by some margin the most challenging meeting. On Q2, they have already decided to forgive Warren’s microscopic omission, and the mark schemes are extremely precise, especially for the middle problems which normally cause the most trouble. Everyone seems to be interpreting them sensibly and similarly so there are no delays, and we are able to bring forward the easier geometry meeting, and confirm all our marks by 5pm. We have {10,17,19,19,19,25}, which is certainly respectable, even if it does mean, to Geoff’s infinite chagrin after his boasts at breakfast, that we are beaten by France.

We’ve been keeping the students up to date via text while they’ve been petting elephants and dipping their feet in hot springs. We meet them for dinner, where they are disappointed at the lack of dramatic gossip about the process, but pleased with their scores, especially the efficient accumulation of part marks on the harder questions. It remains to be seen tomorrow what colour of medals all of this will generate.

Tuesday 14th July

While the UK is done, and I find some more obscure temples in town, other countries continue their final coordinations. It looks like Australia will have its best ever performance, with at least two students sure to receive gold medals, and the rumour is snowballing that USA has won, for the first time since the mid 90s. The students have been attending the IMO lectures this morning, and it seems that Ravi Vakil’s talk on `The Mathematics of Doodling’ has really got the UK boys thinking about space and the meaning of orientation.

Tiring of the comical lift process, I investigate the hotel’s external fire exit, disturbing a flock of pigeons, and a rat the size of a small dachshund. In pursuit of more interesting wildlife, Jill suggests we take the students to Chiang Mai Zoo for the afternoon. Sam and Harvey enjoy the real-life version of Hungry Hippos, and we find an enclosure with a large (ie at least 9), odd number of tortoises, of which precisely one is feeling rather, ahem, left out. The main attraction though is the giant panda Chaung Chaung, who we get to see eating his bamboo with the satisfied langour of a chubby toddler.

We diverge again so I can attend the final jury meeting, where after some brief admin, we pass rapidly to the medal boundaries. There is a new protocol in place this year, which I will leave for Geoff to explain, but the only non-trivial decision to be made is whether the gold cut-off should be rather higher than ideal or slightly lower than ideal. I disagree very strongly with some of the baffling comments which are made on both sides, but only the leaders have a say in this, and the end result is a narrow victory for the higher cutoff*. The UK upshot is that our triumvirate scoring 19 scrape into the silvers, while Warren unfortunately misses out on gold by one point for the third competition in a row. It’s hard to know what to say in these circumstances, but at least by meeting up with the Australian and American teams, we find other students in similar positions, and the feelings of elation and disappointment can be more widely shared.

[*As a result, about 1/15 rather than the statuted 1/12 students get the top award. The other option would have been 1/10.5. So all those leaders concerned about the ‘de-evaluation of the gold’ etc can sleep easy. So can any of their current and past gold-winning students, who had been so worried about retrospective reappraisal of their abilities. You’re right – this was ludicrous.]

Wednesday 15th July

I’ve got the rest of my life to lie in, so decide to cycle to the temple at the top of Doi Suthep. I rent the fanciest bike I can find, for B300, and, to the astonishment of everyone, a helmet for B200. Given the standard of driving, which is at times even worse than Colombia, this seems an absolute bargain. The ride itself though is more exertive than enjoyable, with no real views except the temple at the top, which is more extensive and more gold than the others in town, but also far more busy, which rather spoils the effect.

The real business of the day is the closing ceremony, held through the afternoon in the giant theatre within the student hotel. There’s an excellent drumming and dancing ensemble, and a beautifully-edited video of the IMO activities, which one probably ought to describe as comprehensive rather than a vignette. After about an hour, the medals are awarded, with a great deal more efficiency than normal. The idea to go in decreasing order of score within increasing order of medal is unusual, but does mean that our 19-ers receive their silvers together. Warren and Michael from USA compete for who can get their flag in the premier position. There are a few speeches, and a preview of IMO 2016 in Hong Kong, before we are released for more photographs and an early dinner.

The notion of having an indoor food market as part of the closing banquet is a good one, though it is a struggle to decide whether items are sweet or savoury. Lawrence, Joe and Sam get the chance to show off just how far their chopstick abilities have improved with tricky numbers like ribs and fruit salad. Then the live music starts, and whoever did the soundcheck has some questions to answer, as we can genuinely feel the bass vibrating through our chairs. We retire to the lobby which is, despite the continuing efforts of Elvis, much quieter. As various teams gather, and the students loiter to make final use of the games in the recreation room, this year’s IMO draws to a close.

Thursday 16th July

My flight to Mandalay is not until later, but I join Geoff to meet the rest of the UK group at Chiang Mai airport at 7am. Some of our students are looking rather rough round the edges, for a mixture of illness- and fatigue-related reasons, and there is enthusiasm only for a final round of anti-nausea medication. I’m sure it will be a fun 36 hours for everyone. In any case, soon they are off for a 12 hour layover in KL then home, and I have several hours to ponder.

My only negative thought about this year’s IMO was that the difficulty of the papers reduced the number of students who could feel the satisfaction of completing a medium or hard problem. Earning silver medals based on the easiest problems and part marks is not, in my opinion, entirely the idea, but of course it is the same for everyone. It’s probably also a good reflection on our training programme that the majority of our students feel they wanted to do much better, while we nonetheless came 22nd, with an entirely respectable medal haul. Certainly any disappointment felt about this result should not negate the value of everything they’ve learned by solving problems, and from discussions with each other and the staff during our training. In all other regards this IMO seemed a triumph. Students from all countries seem to have enjoyed themselves, and I’ve had a good time too.

Our camp for new students will be held in Oxford in just a few weeks’ time, and five of this team are eligible for Hong Kong next year. There’s plenty of interesting mathematics just around the corner. But right now, I’ve got to board the world’s most questionable aircraft, so consider it announced that I might have solved the Riemann hypothesis, and we’ll let fate run its course.

DSC_6104_compressed

Final Words

Training a UK team and taking them to the IMO requires a huge amount of effort from a large number of people. Thanks are particularly due to:

  • All the academic and pastoral staff at our camps this year in Oxford, Hungary, Cambridge and Tonbridge, and the UKMT office, especially Bev, who ensured everything ran smoothly. Also everyone who helped set just about enough problems to sate the voracious appetites of our students.
  • Alison, Lina, Mun, and the other staff at Nexus International School, where our stay was pleasant and conducive to good mathematics.
  • Everyone involved with IMO 2015 who ran a competition which was, from the angles I saw at least, almost faultless. In particular, our guide, Korn, who couldn’t have been more helpful. We all wish him the best as he moves to Columbia next month.
  • Paul Janssen, the inventor of Imodium, without whose contribution to science many moments of this trip would have been much less comfortable for the protagonists.
  • Geoff and Jill, who were excellent colleagues in every sense through the challenging and the joyous moments of this year’s trip.
  • Our team, comprising Joe, Lawrence, Sam, Warren, Neel and Harvey, who are all thoroughly nice people. It’s been a pleasure to watch them improve together through the past few months, and I’m sure they will go far in whatever mathematical or non-mathematical avenues they choose over the years to come.