EGMO 2019

Posted on May 15, 2019 by dominicyeo

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 $a^2b+c = b^2c+a$ , after noting that the setup is cyclic (but not symmetric) in the variables, under cycling $a\to b \to c\to a$ .

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 $c$ with $c(ab+bc+ca)$ , 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 $a(1-ab)=c(1-bc)$ , from which the condition gives $a(bc+ca)=c(ab+ac)$ .
Shortly after this, we find $a^2c=ac^2$ , which means $a=c$ 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 $\{a,c\ne 0\}, \{a\text{ or }c=0\}$ 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 $\{a,b,c \ne 0\}$ and $\{a\text{ or }b\text{ or }c=0\}$ , because then in the latter case you could assume that $a=0$ 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 $a_n$ 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 $B=(b_i)$ . (*)
Certainly the case where the $(a_i)$ s themselves form a complete n-residue system is ‘easiest’ and certainly straightforward. One might say that the case where the $(a_i)$ are equal (or at least congruent) is ‘hardest’ (in that $(b_i-a_i)$ 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.

Continue reading →

Balkan MO 2018 – UK Team Blog

Posted on May 15, 2018 by dominicyeo

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

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

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

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

Problem selection

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

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

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

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

The contest

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

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

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

A brief excursion

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

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

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

Coordination

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

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

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

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

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

Round and about

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

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

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

Finishing up

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

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

Harmonic ranges and Balkan MO 2018 Q1

Posted on May 15, 2018 by dominicyeo

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

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

Balkan MO 2018 Problem One

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

An alternative synthetic approach

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

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

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

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

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

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

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

Harmonic ranges

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Balkan MO 2018 – Questions 2,3,4

Posted on May 15, 2018 by dominicyeo

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

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

Problem Three

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

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

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

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

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

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

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

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

Problem Two

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

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

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

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

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

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

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

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

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

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

Problem Four

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

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

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

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

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

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

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

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

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

So we may now write

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

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

Claim II: each $r_i\equiv 1$ modulo p.

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

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

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

Going back to (1), we have

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

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

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

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

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

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

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

EGMO 2018

Posted on April 18, 2018 by dominicyeo

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

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

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

Problem Two

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

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

as this is instantly suggestive of a telescoping product such as

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

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

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

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

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

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

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

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

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

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

$\alpha+\beta+1=n,$

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

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

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

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

Problem Three

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Problem Four

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

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

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

Problem Six

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Symmedians and Balkan MO 2017 Q2

Posted on May 6, 2017 by dominicyeo

While I was away, I wrote about my latest approach to teaching geometry at olympiad camps. This post will end up being about Q2 from the Balkan MO which took place yesterday in Macedonia, but first there is quite a long prelude. My solution, and probably many solutions, to this problem made use of a standard configuration in triangle geometry, namely the symmedian. I want to introduce the configuration, give some simpler examples in practice, and along the way talk about my slightly patched-together philosophy about the merits of practising Euclidean geometry.

The symmedian

Draw a triangle ABC, with A at the top of the page, and extend the rays AB and AC. The median is the line from A through M, the midpoint of BC. Now take points D and E on AB and AC respectively. The following properties are equivalent:

DE is parallel to BC;
triangle ADE is similar to triangle ABC;
the median of ABC passes through the midpoint of DE, and thus is also the median of ADE.

I think it’s a little awkward to prove either of the first two from the third – ratios of areas works – but the rest of the equivalences are straightforward. Later I’m going to talk about the difference between an exercise and a problem. These are all, at best, exercises.

Now take B’ on the ray AC, and C’ on the ray AB such that triangle AB’C’ is similar to triangle ABC. One way to achieve this is to take B’ and C’ to be the reflections in the angle bisector of A of B and C respectively (so then AB’=AB and AC’=AC). We say the line B’C’ is antiparallel to BC, as is any other line DE parallel to B’C’. (Probably this should say ‘with respect to triangle ABC’ or similar, but the context here is very clear, and I want this to seem natural rather than opaque.) Note that DE is an antiparallel line iff BCED is a cyclic quadrilateral. We should remember that, as cyclic quadrilaterals are the signposts for progress in both exercises and problems.

The median of triangle AB’C’ obeys the same equivalences as described above, and so bisects any antiparallel segment. We call the median of triangle AB’C’ the symmedian of triangle ABC. Using the first set of equivalences, the symmedian of triangle ABC bisects any line antiparallel to BC. Furthermore, by construction, the symmedian is the image of the median of ABC under reflection in the bisector of the angle at A. We sometimes say that the symmedian is the isogonal conjugate of the median.

That’s my definition. Note that there was essentially one definition then a couple of easy equivalent definitions. At no point again will I discuss the equivalence of these definitions – we have to take that for granted if we want to get on to more interesting things.

Intersection of tangents + concurrency

Now, in triangle ABC, draw the tangents to the circumcircle at B and C. These meet at P. It turns out that AP is the symmedian. This could have been our definition of a symmedian, but it wasn’t, so let’s quickly prove this.

Trigonometric arguments are very accessible, but I’ll give a Euclidean argument. Draw the antiparallel DE through P, as shown. Our task is to show that EP=PD. At this point, I would again say that this is an exercise.

We colour the angle ABC in green. Two angles around point C share this measure by the alternate segment theorem. The angle at E shares this measure because DE is antiparallel. Therefore CPE is isosceles, and so EP=CP. But CP=BP, so by applying the same argument for the orange angles, we get EP=CP=BP=DP as required.

Pause to regroup. Proving this wasn’t hard, but it was perhaps surprising. If this was all new to you, and I told you to consider the reflection of the median in the angle bisector, you probably wouldn’t instantly exclaim “it goes through the tangent intersection!” So this is a useful piece of knowledge to have gained, in case we ever have to work with the intersection of two tangents like this. Maybe it won’t be useful, but maybe it will. Maybe the statement itself won’t but some extra insights from the proof will be useful, like the fact that we actually showed P is the centre of the circle BCED, and thus angles ECD=EBD=90.

A second property is that in a triangle ABC, the symmedian from A, the symmedian from B and the symmedian from C intersection at, naturally, the symmedian point, which is usually denoted K. This comes from the fact that each symmedian is the isogonal conjugate of the respective median, and the medians are known to concur at the centroid. I’m not going to get into this now.

Configurations – an example

Here’s a problem. Take an isosceles trapezium ABCD as shown (ie throughout I don’t want to worry about alternative diagrams).

Let M be the midpoint of AD, and let E be the point on CM such that angle DBM = EBA. Prove that ABCDE is cyclic.

Well, certainly ABCD is cyclic. So we just need to show E also lies on that circle. And we have two equal angles, but they aren’t in the right place to conclude this immediately. However, we have angle MCA = DBM = EBA, so ABCE is cyclic, and the result follows.

Why is angle MCA = DBM? Well, the isosceles trapezium has an axis of (reflective) symmetry, and MCA is the is image of DBM under that reflection. Simple. If we wanted to do it with congruent triangles, this would all be a bit more laborious. First have to show BD=AC using one set of congruent triangles, then CM=BM using another, finally finishing using DM=MA. This is much less interesting. The symmetry of the configuration is a higher-level observation which could be proved from the axioms of geometry if necessary, but gives us more information more quickly. When we use a configuration like the symmedian configuration, we are really doing a higher-again-level version of this.

Anyway, that problem is fine, but it’s not especially difficult.

Consider instead the following problem. (I saw this online, possibly with slightly different notation, a few days ago and can no longer find the link. If anyone can help, I will add the link.)

Let AB be a chord of a circle, with midpoint M, and let the tangents at A and B meet at P. Consider a line through P which meets the circle at C and D in that order. Extend CM to meet the circle again at E. Show DME is isosceles.

Here’s a diagram, though it includes some clues.

I thought this was a fun problem, and for a while I couldn’t do it because despite lots of equal angles and equal lengths, I couldn’t conjure any congruent triangles in the right places, and I didn’t care enough about solving it to get involved in trigonometry. Then came the moment of insight. We have a midpoint, and also the intersection of the tangents. So DP is the symmedian of triangle DAB, and DM is the median. This gives us the two equal orange angles. Cyclicity gives us an extra equal angle at E as well.

Note now that the situation is very very similar to the previous question (after changing some of the labels), only this time we know ACBDE is cyclic, but don’t know that ABDE is an isosceles trapezium. If ABDE is an isosceles trapezium, we are clearly finished, as then by the same symmetry argument, EM=DM. This direction is probably harder to prove than the direction of the previous problem. Again there are a couple of ways to proceed, but one way is to consider the point E’ such that ABDE’ is an isosceles trapezium, and arguing that E’ lies on the given circle, and the circle through BME, and thus must coincide with E, in a reverse reconstruction argument.

Anyway, this is all slightly a matter of taste, but I would say the second problem is much much more fun than the first problem, even though the second part of the solution is basically the first problem but in a more awkward direction. If you’re going to do Euclidean geometry at all (very much another question), I think you should do questions like the second question wherever possible. And the enjoyable ‘aha moment’ came from knowing about the symmedian configuration. Is it really plausible that you’d look at the original diagram (without the dashed orange lines) and think of the antiparallel to AB in triangle DAB through point P? Probably not. So knowing about the configuration gave access to the good bit of a nice problem.

‘Philosophy of this sort of thing’

If the goal was to solve the second problem in a competition, knowing about the symmedian configuration would be a big advantage. I’ve tried to justify a related alternative view that knowing about the configuration gave access to an enjoyable problem. The question is how many configurations to study, and how hard to study them?

We tend not to think of cyclic quadrilaterals as a special configuration, but that is what they are. We derived circle theorems from the definition of a circle so that we don’t always have to mark on the centre, every single time we have a cyclic quadrilateral. So becoming familiar with a few more is not unreasonable. In particular, there are times when proofs are more important than statements. In research (certainly mine), understanding how various proofs work is the most important aspect, for when you try to extend them or specialise. And in lots of competition problems, the interesting bit is normally finding the argument rather than basking in wonder at the statement (though sometimes the latter is true too!).

To digress briefly. In bridge, I don’t know enough non-obvious motifs in bidding or gameplay to play interesting hands well. I trust that if I thought about some of it very very carefully, I could come up with some of them, especially in gameplay, but not in real time. And it is supposed to be fun right?! Concentrating very very hard to achieve a basic level of competence is not so enjoyable, especially if it’s supposed to be a break from regular work. The end result of this is that I don’t play bridge, which is a shame, because I think the hurdles between where I am currently and a state where I enjoy playing bridge are quite low. If I knew I was going to play bridge regularly, a bit of time reading about conventions would be time well spent. And obviously this applies equally in pursuits which aren’t directly intellectual. Occasionally practising specific skills in isolation broadens overall enjoyment in sport, music, and probably everything. As anyone who’s played in an orchestra knows, there are standard patterns that come up all the time. If you practise these occasionally, you get to a stage where you don’t really need to concentrate that hard in the final movement of Beethoven 5, and instead can listen to the horns, make funny faces at the first violins, and save your mental energy for the handful of non-standard tricky bits. And of course, then move on to more demanding repertoire, where maybe the violas actually get a tune.

This is highly subjective, but my view is that in all these examples are broadly similar to configurations in geometry, and in all of them a little goes a long way.

How? In lots of the geometry configurations you might meet in, for example, a short session at a training camp, most of the conclusions about the configurations have proofs which, like in our symmedian case, are simple exercises. Once you’ve got over some low initial experience hurdles, you have to trust that you can normally solve any simple exercise if required. If you can’t, moving on and returning later, or asking for help is a good policy. The proof shown above that symmedians pass through tangent meet points (and especially a trigonometric alternative) really isn’t interesting enough to spend hours trying to find it. The statements themselves are more useful and interesting here. And it can often be summarised quite quickly: “symmedians are the isogonal conjugates of the medians, so they bisect antiparallels, meet at K, and pass through the alternate tangent meeting points.” Probably having a picture in your mind is even simpler.

There’s a separate question of whether this is worthwhile. I think solving geometry problems occasionally is quite fun, so I guess yes I do think it is worthwhile, but I understand others might not. And if you want to win maths competitions, in the current framework you have to solve geometry problems under time pressure. But from an educational point of view, even though the statements themselves have no real modern research value, I think a) that’s quite a high bar to set, and there’s no a priori reason why they should – >99.9% of things anyone encounters before university have no value to modern research maths; b) in terms of knowledge acquisition, it’s similar in spirit to lots of things that are relevant to later study. I don’t have to solve PDEs very often, but when I do, I hope they are equivalent or similar to one of the small collection of PDEs I do know how to solve. If I worked more with PDEs, the size of this collection would grow naturally, after some initial struggles, and might eventually match my collection of techniques for showing scaling limits of random processes, which is something I need to use often, so the collection is much larger. Maybe that similarity isn’t enough justification by itself, but I think it does mean it can’t be written off as educationally valueless.

Balkan MO 2017 Question Two

An acute angled triangle ABC is given, with AB<AC, and $\omega$ is its circumcircle. The tangents $t_B,t_C$ at B,C respectively meet at L. The line through B parallel to AC meets $t_C$ at D. The line through C parallel to AB meets $t_B$ at E. The circumcircle of triangle BCD meets AC internally at T. The circumcircle of triangle BCE meets AB extended at S. Prove that ST, BC and AL are concurrent.

Ok, so why have I already written 1500 words about symmedians as a prelude to this problem? Because AL is a symmedian. This was my first observation. This observation is then a route into non-Euclidean solutions. It means, for example, that you can describe the point of concurrency fairly explicitly with reference to triangle ABC. If you wish, you can then proceed using areal coordinates. One member of the UK team, whom I know is perfectly capable of finding a synthetic solution, did this. And why not? It’s a competition, and if you can see a method that will definitely work, and definitely take 45 minutes (or whatever) then that’s good.

I was taking a break from work in my office, and had no interest in spending the time evaluating determinants because that isn’t enjoyable at any level, so I focused on the geometry.

I think there’s a good moral from the diagram above, which is the first moderately correct one I drew. I often emphasise that drawing an accurate diagram is important, as it increases the chance that you’ll spot key properties. In this case though, where you’re trying to examine a known configuration, I think it’s more important what you choose to include on your diagram, than how accurately you draw it. (In a moment, we’ll see why it definitely wasn’t very accurate.)

In particular, what’s not on the diagram? E is not on the diagram, and S got added later (as did the equal length signs in TB and CS, which rather spoil what’s about to happen). My first diagram was wildly incorrect, but it also suggested to me that the line ST was hard to characterise, and that I should start by deducing as much as possible about S and T by themselves. So by symmetry, probably it was enough just to deduce as much as possible about T.

Label the angles of triangle ABC as <A, <B, And therefore TB is an antiparallel in triangle ABC. (Note this doesn’t look antiparallel on my diagram at all, but as I said, this didn’t really matter.) Obviously you then guess that CS is also an antiparallel, and on a different diagram I checked this, for essentially the same reasons.

We haven’t yet made any use of the symmedian, but this is clearly where it’ll be useful. Note that if we didn’t know about everything in the prelude, we might well have deduced all of this, but we might not have thought to prove that AL bisects TB unless we’d drawn a very accurate diagram.

At this point, we have to trust that we have enough information to delete most of the diagram, leaving just {A,B,C,S,T} and the line AL. There are a few ways to finish, including similar triangles if you try very hard or trigonometry if you do it right, but again knowledge of some standard configurations is useful. Probably the quickest way is to use Ceva’s theorem in triangle ACS. You can also use Menelaus’ theorem in ABC, so long as you know a little bit about where the symmedian meets the opposite side.

An alternative is the following. We have a complete quadrilateral here, namely BTCS, and the intersection of all its diagonals. One is A, one is the proposed point of concurrency, and one is the point at infinity, since TB || CS. You can chase that, but I found it more clear to let P be the intersection of ST and BC (which we want to prove lies on AL), then look at the complete quadrilateral ATPB. Then AT and BP meet at C, and AB and TP meet at S. So if we look at where the diagonals of ATPB meet the line CS, we have a harmonic range.

If I’d wanted, I could instead have written the prelude about harmonic ranges, but I had fewer ideas how to set these up in a slick Euclidean way. Also, it feels better to talk about the start, rather than the end of a proof, especially when there were alternative endings. Anyway, a harmonic range is a collection of two pairs of points on a line (A, B; C, D), satisfying the following ratio of directed lengths:

$\frac{AC}{BC} = -\frac{AD}{BD}.$

A classic example is when D is the point at infinity, the RHS is -1, and so C is the midpoint of AB. Being happy about using the point at infinity is a property of projective geometry, of which this is a good first example. Anyway, returning to the problem, we are looking at where the diagonals of ATPB meet line CS, and this pair of points forms a harmonic range with (C,S). TB meets CS at the point at infinity, and so AP meets CS at the midpoint of CS. But from the symmedian configuration, AL bisects CS, so AP and AL are in fact the same line, and so P lies on AL as required.

I think was a brilliant example of when knowing a bit of theory is enjoyable. It wasn’t at all obvious initially how to use the symmedian property, but then the observation that TB is antiparallel felt like a satisfying breakthrough, but didn’t immediately kill the problem.

Balkan MO 2017 – Qs 1, 3 and 4

Posted on May 5, 2017 by dominicyeo

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.

EGMO 2017 – Paper One – Geometric subconfigurations

Posted on April 30, 2017 by dominicyeo

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!

RMM 2017 – UK Team Blog

Posted on March 15, 2017 by dominicyeo

This is the customary and slightly frivolous account of a trip to Bucharest for the ninth edition of the Romanian Master of Mathematics, an annual competition for school students, widely recognised as the hardest of its kind.

I discuss the problems in two previous posts (here and here), and there is also a pdf with fewer pictures, which includes both the discussion and this diary, as well as some more formal comments about the competition itself, the results, and thanks.

Wednesday 22 February

Did you know that trains in Moldova use different width tracks to trains in Romania? Well, I didn’t know either, but I found out at 1am today, as my wagon lit from Chisinau was painstakingly jacked up to allow the transfer from ex-Soviet gauge to Western gauge. Outside, a man in a smart uniform and epaulettes shouted loudly and continuously at a group of men in smart uniforms without epaulattes. When their task was done, four sets of border and custom checks remained before the opportunity for another visit to the samovar, and finally a chance to sleep.

All of which is to say that I have arrived at maths competitions in better mental shape than 6am today at Gara de Nord. The UK students have a more conventional itinerary, but their flight from Luton doesn’t arrive until mid-afternoon. After my first Haifa ‘winter’, I’m craving pork and snow, and find both in the mountain town of Sinaia, an hour away by train in Transylvania. I also find a bear. The bear seems very scared.

I return in time to meet the UK students as well as James and MT. Some of our contestants are now into their fourth year of attending international competitions, and the labour of finding them fresh material resembles Hercules against the hydra, but some problems on combinatorial geometry with convexity seem to have kept everyone entertained on the flight. Dinner is at the Moxa campus of the University of Economics, and features chicken with one of two possible carbohydrates, as in fact do the next six meals. However, today is Thomas’s 18th birthday, and so his parents have arranged a delicious cake, which elicits considerably more enthusiasm. On the short walk back to our meeting, we notice it is possible both to buy fireworks and get a tattoo among other options, so Thomas is spoiled for choice about how to take advantage of his majority.

The team’s activities remain a mystery to James and me though, as we have to join the other leaders for the first meeting, to receive the proposed problems. We spend some time thinking about them separately then together, and our initial impression is that it’s a very suitable paper, that hopefully our team will enjoy.

Thursday 23 February

The leaders meet to finalise the choice and statement of the problems. With a bit more time this morning, I’ve solved Q1, Q2, Q5, and proved Q3 once I’d looked up the correct bound. James eats conics for breakfast and shows me a glorious range of interpretations of Q4. We feel happy that our students will have a chance at all of these, while Q6 may prove more restricting. Either way, it’s clearly an appropriate set for this competition, and is approved quickly. So it’s time to finalise the English version of the paper, or finalize the American version. Many alternatives to the word sieve are proposed. Andrea from Italy is clearly already craving home comforts, but his suggestion of cheese grater is not taken up. This time I’m sorting the LaTeX, so get to settle the commas, but also take the blame for inconsistently spacing the rubric between the two papers. I’m sure everyone noticed.

While all this has been happening, the students have been at a lecture by Sergiu Moroianu at the Institute of Mathematics. Joe Benton gives an account of what they learned in the longer pdf version of this report.

For all the charms of Chipping Norton, I sense MT is enjoying the grittier nature of Bucharest Sector 1, and has been shepherding the students round various sites in between attempts at practice problems. I join them for a brief visit to a geology museum. I am very cynical, but it slightly exceeds my expectations, and is infinitely better than the nearby Museum of the Romanian Peasant, which currently ties with the Hanoi Ethnology Museum as my least favourite olympiad excursion of all time.

The opening ceremony is held in the grand hall of the university, and includes several welcoming and thoughtful speeches from the Mayor of Bucharest and the headteacher of Tudor Vianu, the school which hosts this competition every year. Each team briefly presents themselves on stage. Joe and Neel have accumulated a large collection of UK flags from previous competitions, and should hereby consider themselves publicly shamed for forgetting their promise to bring them. It is over soon, and while the students enjoy a quiet evening and an early night, the leaders have to finalise markschemes for all the problems. The walk back takes us through Victory Square, and past the protesters whose fires and slogans have been on front pages around the world in the past months. It’s an interesting time, and the atmosphere of this city feels very different from my first visit, for the inaugural edition of this competition in 2008.

Friday 24 February

The first day of the contest starts at 9am. The British students seem fairly relaxed, and hopefully are aiming high. Contestants may ask questions of clarification during the first 30 minutes. Rosie does this, and I send my reply to her two queries back via the courier. Five minutes later it is returned to me with the explanation that the student does not understand the answer. Even under competition pressure this seems unlikely, given that my answers are, respectively ‘yes’, and putting a ring around one of three options she has listed. It turns out that actually the student courier did not understand what to do with the answer, and the situation is quickly corrected.

We approve more markschemes. The US deputy leader Po-Shen and I share our views on the challenge of correctly finding the bound in Q3, and our suggestion that this instead be worth 2 points is upheld. Various further discussions fill the morning, and we return just in time to meet the students at the end of the exam. Harvey claims all three problems with a relaxed grin, while Joe claims all three problems with the haunted look of a man whose twelfth espresso of the day has just worn off. Alexander and Thomas say that they spent most of the time making sure their solutions to Q1 were totally watertight, which, given the intricacy of the arguments, was clearly a very sensible strategy.

To provide a distraction, if not actually a break from time-pressured problem-solving, I’ve booked a pair of escape rooms for the UK students later in the afternoon. Bucharest is the home of these games, where the aim is to solve themed puzzles as part of a story in time to escape a locked room. I join one of the rooms, where there are some theatrical reveals involving wrenches, and clues hidden in combination-locked cabinets, where ability to add three-digit numbers proves useful. Someone’s carrying voice means we get to enjoy some of the drama and twists of the other room too. Anyway, this proved an ideal way to avoid useless post-mortems, and I highly recommend Vlad and his pair of rooms.

Later, James and I get to look at the students’ work from this morning. Their assessments are pretty accurate. Harvey’s solutions to everything are beautiful, while Neel’s bounding argument in Q2 is certainly the most vulgar (and, in fact, unnecessary) calculation of the year so far. Joe’s solution to Q3 bears such obvious resemblence to an official solution that his uncharacteristic abundance of small errors probably won’t matter, including the memorable set $A_i\backslash\{i\}$ , where the two is mean different things. Some of the team might reflect that a moment of casualness in checking the n=2 case on Q2 is a frustrating way to lose a potential mark, but when I compare notes with James, it sounds like the slow and steady approach to Q1 has indeed paid off for everyone, so hopefully it will not be too painful to agree the scores tomorrow.

Saturday 25 February

It’s the second day of the competition, and the UK team look bright-eyed and positive at breakfast. They aren’t the only ones under pressure this morning, as James and I must settle the scores from yesterday’s questions with local markers, known as coordinators. It’s hard to guess in how much detail one will have to explain your contestants’ scripts, so it is safer to prepare almost line-by-line. On this occasion though, perhaps we have over-prepared, as every meeting ends quickly with offers of 7/7 exactly where we were hoping, and indeed in a couple of places where we were not hoping. The markschemes are very clear about certain omissions which carry a point deduction, so to ensure fairness and consistency, we insist that two scores are moved down. I’m confident that any British student would prefer an honourable 41/42 than an accidental 42/42.

No-one’s going to be scoring 41 nor 42 unless they solve the extremely challenging geometry Q6, and as we meet our students afterwards, it turns out they have not managed any progress there. However, they claim an almost full set of solutions to Questions 4 and 5, which, if accurate, is a very good return. Everyone is in a good mood, and after I explain a couple of approaches to Q6, no-one seems too disappointed that they didn’t spot these.

There are various schedules floating around, listing multiple locations and times for lunch, but our space-time trajectory intersects none of them, so we follow the Chinese team to a recommended cheap Szechuan restaurant round the corner. Various circle theorems are explored via the Lazy Susan, and there is a grand reveal of the marks we’ve recently confirmed. There’s time for another pair of escape rooms while the second day scripts arrive. As Rosie remarks, two in two days can lead to excessive outside-the-box thinking. Sometimes a radiator really isn’t a sinister prop, a device for encoding five-digit numbers, or a clue to a Templar tunnel; it’s just a radiator. Otherwise we’d be cold.

When the scripts arrive, as expected the cupboard is pretty bare on Q6. If there were marks for quantity, Neel might get some, and if there were marks for most uses of esoteric theory in a single page, Alexander might get one. No set of scripts for an international-level medium combinatorics problem will ever be perfect, but our Q5s come close. It’s therefore not a long evening, and we can join the students for dinner with the American team. For most of them it’s their first visit to Europe, and there’s much comparing of culture and maths training programmes. There’s also a long discussion of whether it’s sensible to teach maths in primary school. Those present who have small children or younger siblings weigh in on the mysteries of the ‘grid method’, and whether toddlers implicitly understand commutativity, even if they can’t spell it.

Sunday 26 February

The UK leaders gather early in the ‘philosophical anti-cafe’ opposite Vianu school, to ponder the final scripts with a coffee and a view of an artfully-arranged folio of Spinoza. James has a loyalty card here. Unfortunately two of our students have clear algebraic errors in Q4, but apart from that everything is very straightforward. Though following last night’s conversation, we note that maybe a revision clinic on mathematical spelling might prove useful. Anonymous student X thinks there’s one L in ‘ellipse’, counterbalanced by anonymous student Y who thinks there are two in ‘column’. The word ‘parallel’ comes in many disguises.

Of course, the coordinators couldn’t care less about that, and they don’t even mind Neel’s two-cases-at-once inductive step, so again we get what we ask for on Q5 immediately, and on Q4 in the time it takes James to draw a lozenge tiling representing Thomas’s shearing argument. For Q6, it turns out there clearly is a mark for most uses of esoteric theory in a single page, so Alexander gets it. They show us a diagram with over a hundred lines which suggests that the exotic equivalence he claims is actually true. There we go. Overall, the quality of our written solutions has been extremely high. It feels like I say this every time now, but it isn’t idle propaganda. We remember the horrors that used to emerge occasionally, and the effort to make this improvement permanent feels well worth it.

Meanwhile, to fill the day, the students have gone to Sinaia. Two of their guides went with them to help with tickets at the station, apparently under the impression that never having taken a train before wouldn’t be an obstacle to this role. Either way, they made it, and following my request for material for this report, I receive a trickle of presentable photos, though there is talk afterwards of some rather more informal versions which are apparently not suitable. The Transylvanian winter is thawing, but slowly and messily, and Harvey reports that several of the group spent more time horizontal than vertical. Irrespective of their preferred axis, there’s no comment on whether they saw my bear, or any other bear. But since my bear was scared of me, one wonders what it would make of MT’s telling-off face? (Last seen by me during the notorious ‘balcony incident’ at a summer school in 2005, but hardly forgotten.)

The students return in time for confirmation of the results and their medals. As so often, there is pleasure that we have done so well collectively, mixed with mild disappointment for those who ended up just short of a boundary, and that the UK was so close to placing first. Because of the strength of the invited countries, earning a medal of any colour is a very worthwhile achievement, and so Rosie is impressively sanguine about missing out so narrowly in such an unfortunate manner. Alexander was closer than it appears, and could have two more opportunities to take part.

The closing ceremony at Vianu school proceeds rapidly. There is the usual challenge of photographing the students receiving their prizes, but this time is easy. Thomas is about a foot taller than everyone else on the stage, while Neel is flanked by almost the entire Russian team, but his chutzpah trumps their numerical advantage, with laughter all round. Joe claims this year’s gold medal is substantially weightier. He hasn’t brought his previous pair, so the chance to verify this and recreate a Mark Spitz moment goes begging.

It’s 7pm, and UK student enthusiasm for the closing disco (not my words) is about as high as MT’s enthusiasm to chaperone the closing disco. Instead we find a Middle Eastern restaurant, and it’s refreshing to eat hummus in a place which doesn’t claim to be the ‘best in Israel’ though I don’t think Abu Said in Akko will be rushing to steal the recipe. Po-Shen outlines his vision of a year-long maths camp. I think present company are tired enough after five days here. Some are interested to view, if not actually participate in, the protests in Victory Square, but it seems tonight is a quiet one and nothing is being burned, so late-night cards and a perusal of each others’ scripts will have to do.

Monday 27th February

The rest of the group have a flight back to London later today which apparently cost 99p per person before tax. I don’t know how much less the 5am option was, but I think it’s probably worth it. My own flight is truly at 5am tomorrow and I plan to stay up all night. The students return to school tomorrow, doubtless to receive a glorious mix of adulation and apathy. Harvey requests whether next year this trip can be timed differently so that he can miss the whole of his local Eisteddfod, rather than just one day. I promise to ask the organisers, say goodbye, then head for the hills on a train journey long enough to write the entirety of this report.

3am at Bucharest airport, and thoughts can now turn to the future. Many of us will meet in five weeks’ for another round of mathematics in the more tranquil setting of Cambridge. Meanwhile, I certainly enjoyed, admittedly through red eyes, the entertainment of a flight to Israel where baggage size regulations are actually enforced at the boarding gate, and apparently everyone else made it back safely too.

RMM 2017 – Problems 2, 3 and 6

Posted on March 14, 2017 by dominicyeo

In the previous post, I discussed Problems 1, 4 and 5 from this year’s Romanian Master of Mathematics competition. In this post, I discuss the harder problems (modulo my subjective appreciation of difficulty).

Problem 2

Determine all positive integers n satisfying the following condition: for every monic polynomial P of degree at most n with integer coefficients, there exists a positive integer $k \leq n$ , and (k+1) distinct integers $x_1,\ldots,x_{k+1}$ such that

$P(x_1) + P(x_2) + \cdots + P(x_k) = P(x_{k+1}).$

Parsing this question deserve at least a moment. Straight after a first reading, I find it worth writing down any key quantifiers which I might forget later. Here, it’s the words at most. If you want to show the statement holds for n=2, you need to investigate monic polynomials with degree zero, one and two. You should also make sure that any instances of $x_i$ really are always distinct.

This matters in competitions! Two of our contestants failed to get the mark for showing n=2 works, precisely because of not checking the linear case, and a third could have lost it for using examples which are sometimes not distinct. On hard papers, one mark actually is the difference between triumph and frustration. And of course it matters outside competitions too, since small cases are exactly what your reader might examine first, to check they understand the problem posed, so it’s not a good place for awkward errors.

I started by trying to show that it couldn’t possibly happen that every polynomial with degree at most n had this property, for some combinatorial reason. For example, that if every set of distinct integers could only be a solution set for a small number of polynomials, then we would end up with not enough polynomials. But I couldn’t make this work at all; every bound ended up heavily in the wrong direction.

The next natural question is, does a typical polynomial of degree at most n have this property? But choosing a typical polynomial is hard, so in fact I asked, do the simplest polynomials of degree at most n have this property? I think the simplest polynomials of degree at most n are $\{1,x,x^2,\ldots,x^n\}$ . Under what circumstances does

$x_1^m + \ldots x_k^m = x_{k+1}^m,$ (1)

have solutions in distinct integers? Famously, when k=2 and $m\ge 3$ this is a very very hard problem indeed. So the first point is that it though it might be useful to use Fermat’s Last Theorem, it would be foolish to pursue a strategy which, if successful, would have a proof of FLT as a sub-problem. At least, it would be foolish if the aim was to finish this strategy within a few hours.

So my main comment on this question is meta-mathematical. If lots of attempts at general arguments don’t work, there must be some special example that does it. And what properties do I want this special example to have? Maybe one might have thought of this from scratch, but my motivation came from (1) in the case m=p-1. Then, by Fermat’s Little Theorem, all the summands are equal to 1 or 0 modulo p. If k>p, then after discounting any uniform factors of p, we obtain a congruence equation which is, in informal terms,

$\left(0\text{ or }1\right)+\ldots+\left(0\text{ or }1\right) \equiv \left(0\text{ or }1\right).$

This looks really promising because it’s quite restrictive, but it’s still just a bit annoying: there are quite a few solutions. But it does give us the right idea, which is to find a polynomial P for which $P(x)\equiv 1$ modulo n. The equation $1+\ldots+1\equiv 1$ modulo n has solutions only if the number of summands on the LHS is 1 modulo n. So in this context, this reduces to showing that P is, additionally, injective on the integers, ie that P(x)=P(y) only when x=y.

It’s a nice exercise to show the existence of polynomials which are constant modulo n, and a good problem to work out how to force injectivity. If a polynomial is increasing everywhere, then it is certainly injective, and so the problem ends up being slightly easier in the case where the degree is odd than when the degree is even, but this is a nice conclusion to a nice problem, so I’ll save it for any interested readers to finish themselves.

Problem 3

Let n be an integer greater than 1 and let X be an n-element set. A non-empty collection of subsets $A_1,\ldots, A_k$ of X is tight if the union $A_1 \cup \dots \cup A_k$ is a proper subset of X and no element of X lies in exactly one of the $A_i$ s. Find the largest cardinality of a collection of proper non-empty subsets of X, no non-empty subcollection of which is tight.

Note. A subset A of X is proper if $A\neq X$ . The sets in a collection are assumed to be distinct. The whole collection is assumed to be a subcollection.

By Neel Nanda:

If |X|=n, there are $2^n$ possible subsets, so at first glance the answer could be a variety of things, from a linear to an exponential function of n, each of which would suggest a different approach. So the first step is to conjecture an answer, and by examining small cases it seems impossible to do better than 2n-2. There are several natural constructions for this bound, such as n subsets of size (n-1) and (n-2) subsets of size 1, so we guess this to be our answer (which later turn out to be right!).

From here, a solution is deceptively simple, though empirically the five full solutions in the contest show that it was by no means easy to find. We proceed by induction on the size of X, and want to show that any collection of subsets S has size at least (2n-2). By assumption all subcollections are not tight, so if the union of a subcollection is not the whole set X, then there is an element which appears in exactly one subset. This is a useful result, so we’d like to force a subcollection whose union is not the whole set X.

One way to guarantee that the union of a subcollection is not X is by taking the subcollection of all subsets not containing some element b. So there is some element c which appears in only one subset not containing b. If we choose b so that it’s the element contained in the fewest subsets of S, c is in at least as many subsets of S, but in only one subset not containing b. This means that at most one subset containing b doesn’t contain c. This is useful, because after removing at most 2 subsets (the coefficient of n in 2n-2, importantly!), we now have that every subset in S either contains both b and c or neither. This means that we can replace the pair (b,c) with a new element d, to get a new collection of subsets S’ of a set X’, of size n-1, so by induction $|S| \le |S'|+2\le 2n-2$ .

There is also the case where all subsets contain b, but we can create an equivalent collection of subsets of X \ {b} by removing b from all subsets. So again by induction we are done.

Problem 6

Let ABCD be any convex quadrilateral and let P, Q, R, S be points on the segments AB, BC, CD, and DA, respectively. It is given that the segments PR and QS dissect ABCD into four quadrilaterals, each of which has perpendicular diagonals. Show that the points P, Q, R, S are concyclic.

I thought this problem was extremely hard. The official solution starts with a ‘magic lemma’, that isn’t quite so magic if you then read how it’s used. The overall claim is that PQ, RS and AC are concurrent (or parallel), and this is proved using the fact that the radical axis of the two circles with diameters PQ and RS also passes through this point of concurrency. Hunting for key properties of subsets of points in the diagram is an important skill in hard olympiad geometry, since it exactly reflects how problem-setters produce the problems. All the more so when there is lots of symmetry in the construction. But this is a hard example – there are a lot of potentially relevant subsets of the configuration.

When you’re really stuck with how to get involved in a synthetic configuration, you might consider using coordinates. Some of the UK students have been reading some chapters of a book (Euclidean Geometry in Mathematical Olympiads by Evan Chen. I’ve only had my own copy for a couple of days, but my initial impression is very positive – it fills a gap in the literature in a style that’s both comprehensive and readable.) focusing on various analytic approaches, so James and I felt it was safer to make sure we knew what the best settings were, and how far we could take them.

You almost certainly want the intersection of PR and QS to be your origin. I wanted to set up the configuration using the language of vectors, referenced by (P,Q,R,S). This was because $PQ\perp BO$ and so on, hence $\mathbf{b}\cdot (\mathbf{q}-\mathbf{p})=0$ and so on. An alternative is to use complex numbers, which makes this condition a bit more awkward, but is more promising for the conclusion. Concyclity is not a natural property in vectors unless you can characterise the centre of the circle, but can be treated via cross-ratios in $\mathbb{C}$ . You also have to decide whether to describe the collinearity of A, B and P by expressing $\mathbf{p}=\lambda_{\mathbf{p}} \mathbf{a}+(1-\lambda_{\mathbf{p}})\mathbf{b}$ , or via something more implicit. There definitely are not four degrees of freedom here, since specifying A certainly defines at most one valid set of (B,C,D), so one is mindful we’ll have to eliminate many variables later. We also have to account for fact that $\mathbf{r}$ is a negative scalar multiple of $\mathbf{p}$ , and it’s not clear whether it’s better to break symmetry immediately, or use this towards the end of a calculation.

The point of writing this was that if your initial thought was ‘this looks promising via coordinate methods’, then I guess I agree. But there’s a difference between looking promising, and actually working, and there are lots of parameterisation options. It’s certainly worth thinking very carefully about which to choose, and in this case, challenging though they were, the synthetic or synthetic-trigonometric methods probably were better.

Eventually Almost Everywhere

A blog about probability and olympiads by Dominic Yeo

Category Archives: International Maths Olympiad

EGMO 2019

Balkan MO 2018 – UK Team Blog

Harmonic ranges and Balkan MO 2018 Q1

Balkan MO 2018 – Questions 2,3,4

EGMO 2018

Symmedians and Balkan MO 2017 Q2

Balkan MO 2017 – Qs 1, 3 and 4

EGMO 2017 – Paper One – Geometric subconfigurations

RMM 2017 – UK Team Blog

RMM 2017 – Problems 2, 3 and 6