EGMO 2019

Last week, we held our annual IMO training and selection camp in the lovely surroundings of Trinity College, Cambridge. Four of our students have subsequently spent this week in Kiev, for the ninth edition of the prestigious European Girls’ Mathematical Olympiad.

The UK team, none of whom had attended the competition before, and all of whom remain eligible to return at least once, did extremely well, placing fourth out of the official European countries, and earning three silver medals, and one gold medal, with complete or almost-complete solutions to all six problems between them. More details are available on the competition website.

In this post, I’m going to discuss some of the non-geometry problems. As a special treat, the discussion of Question 6 is led by Joe Benton, which is only fitting, since he wrote it. You can find the first day’s three problems here, and the second day’s problems here. The geometry problems are treated in a separate post.

Problem One

Triple equalities are hard to handle directly, so generally one starts with a single equality, for example the left hand one , after noting that the setup is cyclic (but not symmetric) in the variables, under cycling .

Some quick notes:

• The given equations are inhomogeneous, meaning that not every term has the same degree in terms of {a,b,c}. In complicated equations, normally we want to cancel terms, and we certainly can’t cancel terms with different degrees! So a good first idea is to find a way to make the equations homogeneous, for example using the condition, which is itself inhomogeneous. For example, one could replace with , and it’s clear this might lead to some cancellation. In this case, the algebra is more straightforward if one rearranges and factorises first to obtain , from which the condition gives .
• Shortly after this, we find , which means unless at least one of these terms is equal to zero.
• This case distinction should not be brushed over lightly as a tiny detail. This is the sort of thing that can lose you significant marks, especially if the omitted case turns out to be more involved than the standard case.
• This is a good example of planning your final write-up. The case distinction is really clumsy. What about b? We have already said that the setup is cyclic in (a,b,c), and it’s annoying to throw this aspect away. It really would be much much to have the overall case distinction at the start of your argument, for example into and , because then in the latter case you could assume that without loss of generality, then see what that implied for the other variables.
• In this setting, one really should check that the claimed solutions satisfy both the condition and the triple-equality. This is a complicated family of simultaneous equations, and even if you’re lucky enough to have settled on an argument that is reversible, it’s much easier to demonstrate that everything is satisfied as desired than actually to argue that the argument is reversible.

Problem Two

Maybe I speak for a number of people when I say I’m a little tired of domino tiling problems, so will leave this one out.

Problem Five

I liked this problem. A lot. It did feel like there were potential time-wasting bear traps one might slip into, and perhaps these comments are relevant:

• This feels like quite a natural problem to ask. In particular, the task specified by (A)+(B) is much more elegant than the RHS of (C). So unless you have immediate insight for the RHS of (C), it makes sense to start with the task, and aim for any bound similar to (C).
• There are a lot of transformations one could make, for example, repeatedly removing n from one of the s, or re-ordering them conveniently somehow, which shouldn’t affect any solution. You can also attack the RHS of (C) in a number of ways (perhaps with a case split for n odd or even?). As with involved but easy angle chases discussed in the companion post, it’s probably better to hold this in mind than instantly to do all of these, since it will just obscure the argument if you end up not using the result of the simplification!
• One should always try small examples. Here, it’s worth trying examples large enough to get a sense of what’s happening, because I think the crucial observation is that (unless you were very very unlucky) there are lots of suitable sequences . (*)
• Certainly the case where the s themselves form a complete n-residue system is ‘easiest’ and certainly straightforward. One might say that the case where the are equal (or at least congruent) is ‘hardest’ (in that might have to take the largest values in some sense), but is also straightforward. There’s certainly the option of trying to rigorise this, but I don’t know whether this can be made to work.

Advertisement

Chains and antichains

I’ve recently been at the UK-Hungary winter olympiad camp in Tata, for what is now my sixth time. As well as doing some of my own work, have enjoyed the rare diversion of some deterministic combinatorics. It seems to be a local variant of the pigeonhole principle that given six days at a mathematical event in Hungary, at least one element from {Ramsay theory, Erdos-Szekeres, antichains in the hypercube} will be discussed, with probability one. On this occasion, all were discussed, so I thought I’d write something about at least one of them.

Posets and directed acyclic graphs

This came up on the problem set constructed by the Hungarian leaders. The original formulation asked students to show that among any 17 positive integers, there are either five such that no one divides any other, or five such that among any pair, one divides the other.

It is fairly clear why number theory plays little role. We assign the given integers to the vertices of a graph, and whenever a divides b, we add a directed edge from the vertex corresponding to a to the vertex corresponding to b. Having translated the given situation into a purely combinatorial statement, fortunately we can translate the goal into the same language. If we can find a chain of four directed edges (hence five vertices – beware confusing use of the word ‘length’ here) then we have found the second possible option. Similarly, if we can find an antichain, a set of five vertices with no directed edges between them, then we have found the first possible option.

It’s worth noting that the directed graph we are working with with is transitive. That is, whenever there is an edge a->b and b->c, there will also be an edge a->c. This follows immediately from the divisibility condition. There are also no directed cycles in the graph, since otherwise there would be a cycle of integers where each divided its successor. But of course, when a divides b and these are distinct positive integers, this means that b is strictly larger than a, and so this relation cannot cycle.

In fact, among a set of positive integers, divisibility defines a partial order, which we might choose to define as any ordering whether the associated directed graph is transitive and acyclic, although obviously we could use language more naturally associated with orderings. Either way, from now on we consider posets and the associated DAGs (directed acyclic graphs) interchangeably.

Dilworth’s theorem

In the original problem, we are looking for either a large chain, or a large antichain. We are trying to prove that it’s not possible to have largest chain size at most four, and largest antichain size at most four when there are 17 vertices, so we suspect there may some underlying structure: in some sense perhaps the vertex set is the ‘product’ of a chain and an antichain, or at least a method of producing antichains from a single vertex.

Anyway, one statement of Dilworth’s theorem is as follows:

Statement 1: in a poset with nm+1 elements, there is either a chain of size n+1, or an antichain of size m+1.

Taking n=m=4 immediately finishes the original problem about families of divisors. While this is the most useful statement here, it’s probably not the original, which says the following:

Statement 2: in a poset, there exists a decomposition into chains, and an antichain such that .

Remark 1: Note that for any decomposition into chains and any antichain, we have , since you can’t have more than one representative from any chain in the antichain. So Statement 2 is saying that equality does actually hold.

Remark 2: Statement 1 follows immediately from Statement 2. If all antichains had size at most m, then there’s a decomposition into at most m chains. But each chain has size n, so the total size of the graph is at most mn. Contradiction.

Unsuccessful proof strategies for Dilworth

Since various smart young people who didn’t know the statement or proof of Dilworth’s theorem attempted to find it (in the form of Statement 1, and in a special case) in finite time conditions, it’s easy to talk about what doesn’t work, and try to gain intellectual value by qualifying why.

• Forgetting directions: in general one might well attack a problem by asking whether we have more information than we need. But ignoring the directions of the edges is throwing away too much information. After doing this, antichains are fine, but maybe you need to exhibit some undirected ‘chains’. Unless these undirected chains are much longer than you are aiming for, you will struggle to reconstruct directed chains out of them.
• Where can the final vertex go?: in a classic trope, one might exhibit a directed graph on nm vertices with neither a chain of size n+1 nor an antichain of size m+1. We attempt to argue that this construction is essentially unique, and that it goes wrong when we add an extra vertex. As a general point, it seems unlikely to be easier to prove that exactly one class of configurations has a given property in the nm case, than to prove no configurations has the same property in the nm+1 case. A standalone proof of uniqueness is likely to be hard, or a disguised rehash of an actual proof of the original statement.
• Removing a chain: If you remove a chain of maximal length, then, for contradiction, what you have left is m(n-1)+1 vertices. If you have a long chain left, then you’re done, although maximality has gone wrong somewhere. So you have an antichain size n in what remains. But it’s totally unclear why it should be possible to extend the antichain with one of the vertices you’ve just removed.

An actual proof of Dilworth (Statement 1), and two consequences

This isn’t really a proof, instead a way of classifying the vertices in the directed graph so that this version of Dilworth. As we said earlier, we imagine there may be some product structure. In particular, we expect to be able to find a maximal chain, and a nice antichain associated to each element of the maximal chain.

We start by letting consist of all the vertices which are sources, that is, have zero indegree. These are minima in the partial ordering setting. Now let consist of all vertices whose in-neighbourhood is entirely contained in , that is they are descendents only of . Then let consist of all remaining vertices whose in-neighourhood is entirely contained in (but not entirely in , otherwise it would have already been treated), and so on. We end up with what one might call an onion decomposition of the vertices based on how far they are from the sources. We end up with , and then we can find a chain of size k+1 by starting with any vertex in and constructing backwards towards the source. However, this is also the largest possible size of a chain, because every time we move up a level in the chain, we must move from to where j>i.

It’s easy to check that each is an antichain, and thus we can read off Statement 1. A little more care, and probably an inductive argument is required to settle Statement 2.

We have however proved what is often called the dual of Dilworth’s theorem, namely that in a poset there exists a chain C, and a decomposition into a collection of antichains, for which .

Finally, as promised returning to Erdos-Szekeres, if not to positive integers. We apply Dilworth Statement 1 to a sequence of real numbers , with the ordering if and . Chains correspond to increasing subsequences, and antichains to decreasing subsequences, so we have shown that there is either a monotone subsequence of length m+1.

 

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:

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

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

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.

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

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

EGMO 2016 Paper I

We’ve just our annual selection and training camp for the UK IMO team in Cambridge, and I hope it was enjoyed by all. I allotted myself the ‘graveyard slot’ at 5pm on the final afternoon (incidentally, right in the middle of this, but what England fan could have seen that coming in advance?) and talked about random walks on graphs and the (discrete) heat equation. More on that soon perhaps.

The UK has a team competing in the 5th European Girls Mathematical Olympiad (hereafter EGMO 2016) right now in Busteni, Romania. The first paper was sat yesterday, and the second paper is being sat as I write this. Although we’ve already sent a team to the Romania this year (where they did rather well indeed! I blame the fact that I wasn’t there.), this feels like the start of the olympiad ‘season’. It also coincides well with Oxford holidays, when, though thesis deadlines loom, I have a bit more free time for thinking about these problems. Anyway, last year I wrote a summary of my thoughts and motivations when trying the EGMO problems, and this seemed to go down well, so I’m doing the same this year. My aim is not to offer official solutions, or even outlines of good solutions, but rather to talk about ideas, and how and why I decided whether they did or didn’t work. I hope some of it is interesting.

You can find the paper in many languages on the EGMO 2016 website. I have several things to say about the geometry Q2, but I have neither enough time nor geometric diagram software this morning, so will only talk about questions 1 and 3. If you are reading this with the intention of trying the problems yourself at some point, you probably shouldn’t keep reading, in the nicest possible way.

Question 1

[Slightly paraphrased] Let n be an odd positive integer and . Show that

where we define cyclically in the natural way.

Thought 1: this is a very nice statement. Obviously when i and j are equal, the inequality holds the other way round, and so it’s interesting and surprising that constructing a set of pairs of inequalities in the way suggested gives a situation where the ‘maximum minimum’ is at least the ‘minimum maximum’.

Thought 2: what happens if n is actually even? Well, you can kill the right-hand-side by taking at least every other term to be zero. And if n is even, you really can take every other term to be even, while leaving the remaining terms positive. So then the RHS is zero and the LHS is positive.

The extension to this thought is that the statement is in danger of not holding if there’s a lot of alternating behaviour. Maybe we’ll use that later.

Idea 1: We can write

which gives insight into ‘the problem multiplied by 2’. This was an ‘olympiad experience’ idea. These transformations between various expressions involving sums of squares turn out to be useful all the time. Cf BMO2 2016 question 4, and probably about a million other examples. As soon as you see these expressions, your antennae start twitching. Like when you notice a non-trivial parallelogram in a geometry problem, but I digress. I’m not sure why I stuck in the absolute value signs.

This was definitely a good idea, but I couldn’t find a way to make useful deductions from it especially easily. I tried converting the RHS expression for i (where LHS attains minimum) into the RHS expression for any j by adding on terms, but I couldn’t think of a good way to get any control over these terms, so I moved on.

Idea 2: An equality case is when they are all equal. I didn’t investigate very carefully at this point whether this might be the only equality case. I started thinking about what happens if you start with an ‘equal-ish’ sequence where the inequality holds, then fiddle with one of the values. If you adjust exactly one value, then both sides might stay constant. It seemed quite unlikely that both would vary, but I didn’t really follow this up. In any case, I didn’t feel like I had very good control over the behaviour of the two sides if I started from equality and built up to the general case by adjusting individual values. Or at least, I didn’t have a good idea for a natural ordering to do this adjustment so that I would have good control.

Idea 3: Now I thought about focusing on where the LHS attains this minimum. Somewhere, there are values (x,y) next to each other such that is minimal. Let’s say . Therefore we know that the element before x is at least y, and vice versa, ie we have

and this wasn’t helpful, because I couldn’t take this deduction one step further on the right. However, once you have declared the minimum of the LHS, you are free to make all the other values of smaller, so long as they don’t break this minimum. Why? Because the LHS stays the same, and the RHS gets smaller. So if you can prove the statement after doing this, then the statement was also true before doing this. So after thinking briefly, this means that you can say that for every i, either or attains this minimum.

Suddenly this feels great, because once we know at least one of the pairs corresponding to i attains the minimum, this is related to parity of n, which is in the statement. At this point, I was pretty confident I was done. Because you can’t partition odd [n] into pairs, there must be some i which achieves a minimum on both sides. So focus on that.

Let’s say the values are (x,y,x) with . Now when we try to extend in both directions, we actually can do this, because the values alternate with bounds in the right way. This key is to use the fact that the minimum must be attained at least every other pair. (*) So we get

But it’s cyclic, so the ‘ends’ of this sequence join up. If modulo 4, we get next to each other, which means the RHS of the statement is indeed at least the LHS. If modulo 4, then we get next to each other, which contradicts minimality of unless x=y. Then we chase equality cases through the argument (*) and find that they must all be equal. So (after checking that the case really is the same), we are done.

Thought 3: This really is the alternating thought 2 in action. I should have probably stayed with the idea a bit longer, but this plan of reducing values so that equality was achieved often came naturally out of the other ideas.

Thought 4: If I had to do this as an official solution, I imagine one can convert this into a proof by contradiction and it might be slightly easier, or at least easier to follow. If you go for contradiction, you are forcing local alternating behaviour, and should be able to derive a contradiction when your terms match up without having to start by adjusting them to achieve equality everywhere.

Question 3

Let m be a positive integer. Consider a 4m x 4m grid, where two cells are related to each other if they are different but share a row or a column. Some cells are coloured blue, such that every cell is related to at least two blue cells. Determine the minimum number of blue cells.

Thought 1: I spent the majority of my time on this problem working with the idea that the answer was 8m. Achieved by taking two in each row or column in pretty much any fashion, eg both diagonals. This made me uneasy because the construction didn’t take advantage of the fact that the grid size was divisible by 4. I also couldn’t prove it.

Thought 2: bipartite graphs are sometimes useful to describe grid problems. Edges correspond to cells and each vertex set to row labels or column labels.

Idea 1: As part of an attempt to find a proof, I was thinking about convexity, and why having exactly two in every row was best, so I wrote down the following:

Claim A: No point having three in a row.

Claim B: Suppose a row has only one in it + previous claim => contradiction.

In Cambridge, as usual I organised a fairly comprehensive discussion of how to write up solutions to olympiad problems. The leading-order piece of advice is to separate your argument into small pieces, which you might choose to describe as lemmas or claims, or just separate implicitly by spacing. This is useful if you have to do an uninteresting calculation in the middle of a proof and don’t want anyone to get distracted, but mostly it’s useful for the reader because it gives an outline of your argument.

My attempt at this problem illustrates an example of the benefit of doing this even in rough. If your claim is a precise statement, then that’s a prompt to go back and separately decide whether it is actually true or not. I couldn’t prove it, so started thinking about whether it was true.

Idea 2: Claim A is probably false. This was based on my previous intuition, and the fact that I couldn’t prove it or get any handle on why it might be true. I’d already tried the case m=1, but I decided I must have done it wrong so tried it again. I had got it wrong, because 6 is possible, and it wasn’t hard from here (now being quite familiar with the problem) to turn this into a construction for 6m in the general case.

Idea 3: This will be proved by some sort of double-counting argument. Sometimes these arguments turn on a convexity approach, but when the idea is that a few rows have three blue cells, and the rest have one, this now seemed unlikely.

Subthought: Does it make sense for a row to have more than three blue cells? No. Why not? Note that as soon as we have three in a row, all the cells in that row are fine, irrespective of the rest of the grid. If we do the problem the other way round, and have some blues, and want to fill out legally the largest possible board, why would we put six in one row, when we could add an extra row, have three in each (maintaining column structure) and be better off than we were before. A meta-subthought is that this will be impossible to turn into an argument, but we should try to use it to inform our setup.

Ages and ages ago, I’d noticed that you could permute the rows and columns without really affecting anything, so now seemed a good time to put all the rows with exactly one blue cell at the top (having previously established that rows with no blue cell were a disaster for achieving 6m), and all the columns with one blue cell at the left. I said there were such rows and columns. Then, I put all the columns which had a blue cell in common with the rows next to the columns I already had. Any such column has at least three blues in it, so I said there were of these, and similarly rows. The remaining columns and rows might as well be and hopefully won’t matter too much.

From here, I felt I had all the ingredients, and in fact I did, though some of the book-keeping got a bit fiddly. Knowing what you are aiming for and what you have means there’s only one way to proceed: first expressions in terms of these which are upper bounds for the number of columns (or twice the number of columns = rows if you want to keep symmetry), and lower bounds in terms of these for the number of blue cells. I found a noticeable case-distinction depending on whether and . If both held or neither held, it was quite straightforward, and if exactly one held, it got messy, probably because I hadn’t set things up optimally. Overall, fiddling about with these expressions occupied slightly more time than actually working out the answer was 6m, so I don’t necessarily have a huge number of lessons to learn, except be more organised.

Afterthought 2: Thought 2 said to consider bipartite graphs. I thought about this later while cycling home, because one can’t (or at least, I can’t) manipulate linear inequalities in my head while negotiating Oxford traffic and potholes. I should have thought about it earlier. The equality case is key. If you add in the edges corresponding to blue cells, you get a series of copies of , that is, one vertex with three neighbours. Thus you have three edges for every four vertices, and everything’s a tree. This is a massively useful observation for coming up with a very short proof. You just need to show that there can’t be components of size smaller than 4. Also, I bet this is how the problem-setter came up with it…

Lagrange multipliers Part One: A much simpler setting

I am currently in northern Hungary for our annual winter school for some of the strongest young school-aged mathematicians in the UK and Hungary. We’ve had a mixture of lectures, problem-solving sessions and the chance to enjoy a more authentic version of winter than is currently on offer in balmy Oxford.

One of my favourite aspects of this event is the chance it affords for the students and the staff to see a slightly different mathematical culture. It goes without saying that Hungary has a deep tradition in mathematics, and the roots start at school. The British students observe fairly rapidly that their counterparts have a much richer diet of geometry, and methods in combinatorics at school, which is certainly an excellent grounding for use in maths competitions. By contrast, our familiarity with calculus is substantially more developed – by the time students who study further maths leave school, they can differentiate almost anything.

But the prevailing attitude in olympiad circles is that calculus is unrigorous and hence illegal method. The more developed summary is that calculus methods are hard, or at least technical. This is true, and no-one wants to spoil a measured development of analysis from first principles, but since some of the British students asked, it seemed worth giving a short exposition of why calculus can be made rigorous. They are mainly interested in the multivariate case, and the underlying problem is that the approach suggested by the curriculum doesn’t generalise well at all to the multivariate setting. Because it’s much easier to imagine functions of one variable, we’ll develop the machinery of the ideas in this setting in this post first.

Finding minima – the A-level approach

Whether in an applied or an abstract setting, the main use of calculus at school is to find where functions attain their maximum or minimum. The method can be summarised quickly: differentiate, find where the derivative is zero, and check the second-derivative at that value to determine that the stationary point has the form we want.

Finding maxima and finding minima are a symmetric problem, so throughout, we talk about finding minima. It’s instructive to think of some functions where the approach outlined above fails.

In the top left, there clearly is a minimum, but the function is not differentiable at the relevant point. We can probably assert this without defining differentiability formally: there isn’t a well-defined local tangent at the minimum, so we can’t specify the gradient of the tangent. In the top right, there’s a jump, so depending on the value the function takes at the jump point, maybe there is a minimum. But in either case, the derivative doesn’t exist at the jump point, so our calculus approach will fail.

In the middle left, calculus will tell us that the stationary point in the middle is a ‘minimum’, but it isn’t the minimal value taken by the function. Indeed the function doesn’t have a minimum, because it seems to go off to in both directions. In the middle right, the asymptote provides a lower bound on the values taken by the function, but this bound is never actually achieved. Indeed, we wouldn’t make any progress by calculus, since there are no stationary points.

At the bottom, the functions are only defined on some interval. In both cases, the minimal value is attained at one of the endpoints of the interval, even though the second function has a point which calculus would identify as a minimum.

The underlying problem in any calculus argument is that the derivative, if it exists, only tells us about the local behaviour of the function. At best, it tells us that a point is a local minimum. This is at least a necessary condition to be a global minimum, which is what we actually care about. But this is a change of emphasis from the A-level approach, for which having zero derivative and appropriately-signed second-derivative is treated as a sufficient condition to be a global minimum.

Fortunately, the A-level approach is actually valid. It can be shown that if a function is differentiable everywhere, and it only has one stationary point, where the second-derivative exists and is positive, then this is in fact the global minimum. The first problem is that this is really quite challenging to show – since in general the derivative might not be continuous, although it might have many of the useful properties of a continuous function. Showing all of this really does require setting everything up carefully with proper definitions. The second problem is that this approach does not generalise well to multivariate settings.

Finding minima – an alternative recipe

What we do is narrow down the properties which the global minimum must satisfy. Here are some options:

0) There is no global minimum. For example, the functions pictured in the middle row satisfy this.

Otherwise, say the global minimum is attained at x. It doesn’t matter if it is attained at several points. At least one of the following options must apply to each such x.

1) ,

2) is not defined,

3) x lies on the boundary of the domain where f is defined.

We’ll come back to why this is true. But with this decomposition, the key to identifying a global minimum via calculus is to eliminate options 0), 2) and 3). Hopefully we can eliminate 2) immediately. If we know we can differentiate our function everywhere, then 2) couldn’t possibly hold for any value of x. Sometimes we will be thinking about functions defined everywhere, in which case 3) won’t matter. Even if our function is defined on some interval, this only means we have to check two extra values, and this isn’t such hard work.

It’s worth emphasising why if x is a local minimum not on the boundary and f'(x) exists, then f'(x)=0. We show that if , then x can’t be a local minimum. Suppose f'(x)>0. Then both the formal definition of derivative, and the geometric interpretation in terms of the gradient of a tangent which locally approximates the function, give that, when h is small,

where this ‘little o’ notation indicates that for small enough h, the final term is much smaller than the second term. So for small enough h, , and so we don’t have a local minimum.

The key is eliminating option 0). Once we know that there definitely is a global minimum, we are in a good position to identify it using calculus and a bit of quick checking. But how would we eliminate option 0)?

Existence of global minima

This is the point where I’m in greatest danger of spoiling first-year undergraduate course content, so I’ll be careful.

As we saw in the middle row, when functions are defined on the whole real line, there’s the danger that they can diverge to , or approach some bounding value while never actually attaining it. So life gets much easier if you work with functions defined on a closed interval. We also saw what can go wrong if there are jumps, so we will assume the function is continuous, meaning that it has no jumps, or that as y gets close to x, f(y) gets close to f(x). If you think a function can be differentiated everywhere, then it is continuous, because we’ve seen that once a function has a jump (see caveat 2) then it certainly isn’t possible to define the derivative at the jump point.

It’s a true result that a continuous function defined on a closed interval is bounded and attains its bounds. Suppose such a function takes arbitrarily large values. The main idea is that if the function takes arbitrarily large values throughout the interval, then because the interval is finite it also takes arbitrarily large values near some point, which will make it hard to be continuous at that point. You can apply a similar argument to show that the function can’t approach a threshold without attaining it somewhere. So how do you prove that this point exists? Well, you probably need to set up some formal definitions of all the properties under discussion, and manipulate them carefully. Which is fine. If you’re still at school, then you can either enjoy thinking about this yourself, or wait until analysis courses at university.

My personal opinion is that this is almost as intuitive as the assertion that if a continuous function takes both positive and negative values, then it has a zero somewhere in between. I feel if you’re happy citing the latter, then you can also cite the behaviour of continuous functions on closed intervals.

Caveat 2) It’s not true to say that if a function doesn’t have jumps then it is continuous. There are other kinds of discontinuity, but in most contexts these are worse than having a jump, so it’s not disastrous in most circumstances to have this as your prime model of non-continuity.

Worked example

Question 1 of this year’s BMO2 was a geometric inequality. I’ve chosen to look at this partly because it’s the first question I’ve set to make it onto BMO, but mainly because it’s quite hard to find olympiad problems which come down to inequalities in a single variable.

Anyway, there are many ways to parameterise and reparameterise the problem, but one method reduces, after some sensible application of Pythagoras, to showing

(*)

for all positive x.

There are simpler ways to address this than calculus, especially if you establish or guess that the equality case is x=1/2. Adding one to both sides is probably a useful start.

But if you did want to use calculus, you should argue as follows. (*) is certainly true when and also when $x\le \frac{2}{9}$. The function f(x) is continuous, and so on the interval it has a minimum somewhere. We can differentiate, and fortunately the derivative factorises (this might be a clue that there’s probably a better method…) as

If x is positive, the second bracket can’t be zero, so the only stationary point is found at x=1/2. We can easily check that , and we have already seen that . We know f attains its minimum on , and so this minimal value must be $\frac98$, as we want.

Overall, the moral of this approach is that even if we know how to turn the handle both for the calculation, and for the justification, it probably would be easier to use a softer approach if possible.

Next stage

For the next stage, we assess how much of this carries across to the multivariate setting, including Lagrange multipliers to find minima of a function subject to a constraint.

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.

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.

IMO 2015 Diary – Part Three

Wednesday 8th July

Because of my complicated post-IMO itinerary, AirAsia will be a major feature of my life over the coming weeks, so perhaps I should be careful what I say. First impressions are not good. The online check-in software would have been out-of-date in the late 90s, and within an at the time completely empty plane, the algorithm assigns us seats 23A, 23B, 23C, 23D, 23E, 23F, 24A and 8F. Still, you get what you pay for, and we did not pay a lot at all. What we get is a flight to Thailand, during which we meet the Malaysian team, and our own students attempt one of the hardest outstanding problems from last year’s shortlist.

We arrive in Chiang Mai, and find an impressive greeting party from the IMO, who seem organised, keen to present us with garlands, and even more enthusiastic about taking photos than me. Our guide, Korn, leads us onwards to the Lotus Hotel, where the students will be staying for the duration of the competition. Our initial impression is that the rooms are lovely, the lobby is full of familiar faces, and the dessert is bright blue jelly. So far seems an excellent venue choice.

I’ve been in touch with BBC World about a live interview tomorrow morning. There’s been some confusion with photographs, so they are particularly keen to talk to Neel about his experiences as a girl attending international maths camps. Even in the event of finding an alternative narrative arc, the arrival of 600 technophile teenagers is putting strain on the hotel’s wifi. Skype seems a distant possibility, given the difficulty even in following an exciting first day of the (original) Ashes, featuring our second favourite prodigious Joe, via text. The Anglophone viewers of SE Asia will have to contain their excitement for now.

Thursday 9th July

We are up painfully early, in order to arrive painfully early at the opening ceremony. We have our first experience of songthaew, the ubiquitous red taxi minibuses. Though rather reminiscent of a police van, at least it’s a chance to get to know each other better. The team have brought their flags and brushed up smartly, and seem keen to pose with everyone who asks. Security is very tight – we are scanned repeatedly and our temperatures taken. We have a three hour wait, the giant hall is very stuffy, and it’s not clear whether we will be allowed to leave in a medical emergency. Five of the team work on C8, while Joe continues his quest to experience the first aid facilities at every IMO he attends. The room is very well-equipped, and the staff seem keen to use as much of the equipment as possible on Joe, but eventually they are persuaded that a horizontal surface and a glass of water will more than suffice in this instance. I find this gently air-conditioned room by some margin the most pleasant place in Chiang Mai so far.

All of this endeavour is for the benefit and protection of the princess, who as an enthusiastic supporter of STEM and enrichment is guest of honour. Her throne is suitably gold, and her entrance suitably Sheba-esque. Because of the presence of royalty, we are informed that our team procession across the stage must be formal – no projectile key rings this year. She departs with commensurate fanfare at the end of a remarkably short ceremony with a tragic lack of folkloric dancing, then there is the opportunity for more spontaneity, and an infinite number of photographs. The trend of the past two years that UK team members should carry others on their shoulders at such events seems to have become firmly established, to the chagrin of risk assessment form writers everywhere, though Sam and Warren appear reliable chariots this time. I try to ask as many of the officials as possible what their medals are for, but it’s tough getting many replies. I guess Thais are uniformly very heroic.

The afternoon stretches out somewhat, so we visit the Suan Dok temple, where everything is gold or brilliant marble. Apparently anyone who rings all of the many bells and gongs that line the perimeter will become famous, and some of our team gleefully test this hypothesis, to the annoyance of the many feral dogs who had been enjoying a mid-afternoon snooze in the grounds.

The students are keen for an early night, but not before a dance-off to some Thai music videos. While channel-hopping, they find coverage of the opening ceremony on the news, including a brief clip of our sashay and bow across the stage. We were not together. At all. Jill and I retire to the lobby, where no-one seems to have the heart to tell the hapless Elvis impersonator that he has forgotten to turn on his microphone.

Friday 10th July

The students are up fairly early for the first paper. They are allowed to take in a ‘talisman’ small enough to fit in their hand, and a kedondong each, lovingly rescued from Malaysia, seems the perfect choice. There is a mixture of nerves and excitement, but the algorithm for getting 500 contestants into 500 desks seems sensible, and so there is little for me to do except offer best wishes.

During the exam itself, the deputy leaders were whisked off to visit an elephant sanctuary. I remain ambivalent about the principle of teaching animals to perform tricks, but at least this show was tasteful, with a penalty shootout building to a triumphant climax unfamiliar to England fans, and a sequence of live paintings that were genuinely remarkable. I also take the chance for a short ride. It is clear that going uphill is a great deal more comfortable than lurching downhill, especially when steps are involved. It was a memorable experience to see these magnificent animals up close, and I hope the existence of such places helps towards conservation in the wild too.

We return to meet the students directly after the exam. Warren seems unimpressed by Q2, despite having solved it, while the others’ moods range from disappointed to bitterly disappointed. We move on though, especially since it will turn out that many comparable countries have a similar reaction to this question, for which the crucial division into cases is more tedious than one might hope for under competition time pressure.

Mindful that the hotel is likely to be rife with unhelpful gossip all afternoon, the UK team and Luke from Ireland head off for the old walled city in the centre of Chiang Mai. First a museum of the region’s cultural heritage, with plenty of information about basket-weaving, and some answers to Neel et al’s further questions about karma, such as whether it is a universal conserved quantity. The Lan Chang temple offers further sleeping dogs, gilded dragons and the chance to meditate on the fact that there’s more to life than technical number theory problems. We go again tomorrow.

Saturday 11th July

The second paper dawns. Neel and Joe seem to be competing to see who can wear the team polo shirt for the most days consecutively, so again we watch our mostly turquoise band file through the various entrances into the exam hall. The deputies have nothing to do this morning, so John from USA and James from Canada and I attempt to go walking up the lower reaches of the Doi Suthep mountain. Despite about 600,000 hits on Google for ‘Chiang Mai hike’, both our guides and the hotel staff tell us this is literally impossible, but recommend walking along the side of the three-lane highway instead.

The hikes mentioned online turn out to be literally entirely possible. I briefly slip flat on my back, and now have the exact imprint of a bottle cap in the middle of my spine, but otherwise it is entirely enjoyable. Lunch at a nearby restaurant offering North-Eastern Thai food is incredible, and it’s lucky the exam is finishing soon, otherwise I would have happily eaten twice my body weight.

We return to find the lobby overwhelmed with the news that today’s paper was hurriedly rewritten last night, after the original version was revealed accidentally to some DLs yesterday. The British students are again unhappy. It’s been a long year of enjoyable mathematics and worthwhile training, and no one likes to see it end in tears of frustration. But maths competitions are exciting precisely because sometimes even strong students struggle, and it doesn’t reduce the value of the mathematics they have experienced together during preparation.

While that might hold in abstract, in practice it seems sensible to find more active immediate distraction. We find a path to the bottom of a waterfall, then a trail to the top of the same waterfall through the jungle. Lawrence enjoys using a leaf almost as long as himself as a fan, and Warren, leading our march, regularly shakes a particularly luscious tree besides the path, to induce a refreshing shower onto those bringing up the rear. By the end, we are all sweatier, but I hope also more grounded about the cosmic importance (or not) of making the most shrewd substitutions in a functional equation.

Geoff is now allowed to see the students, and we enjoy a relief from rice with a rare Western meal, before I transfer to the leaders’ hotel, where we will be working hard at the scripts over the next few days.