EGMO synopsis

I have returned from assisting at the Easter olympiad training camp at Trinity College, Cambridge. After we marked a selection test (the results of which I am not at liberty to divulge), a preliminary squad of nine people were selected, which will eventually be narrowed down to the six people that form the IMO team.

In addition to satisfying the role of General Dogsbody, I gave an unofficial talk on Ramsey theory at 7:00 am. Considering the early hour, lack of advertisement and the optional nature of the talk, the attendance (three people) was actually quite reasonable. I distributed a sheet of questions (PDF). If you wish to attempt them, I suggest familiarising yourself with the theorems in the third chapter (Combinatorics II) of MODA. Two of these were marked with a direct sum symbol () to indicate that they’re extremely challenging, and far beyond the hardest of IMO questions.

Another function of the Easter camp was to prepare our team of four girls for EGMO 2013, which was held in Luxembourg last week. The scores at the end of the competition were continually updated to a live online scoreboard, followed shortly after by the medal boundaries. Danielle Wang (USA) won the competition, with a total of 38 marks out of a possible 42. Three nations (Belarus, Serbia and the United States) were tied in equal first position, with cumulative scores of 99.

Solutions and commentary (spoiler alert!)

The problems appear to be arranged in strictly increasing order of how interesting they are, so I’ll only discuss the second paper here.

Problem 4: Quintic polynomial

This one isn’t actually particularly interesting; however, I’ll include it here for completeness, since it would seem strange to only discuss questions 5 and 6.

4. Find all ordered pairs of positive integers (a, b) for which there are three consecutive integers at which the polynomial takes integer values.

In problems such as this one, it is most convenient to let the three consecutive integers be {n − 1, n, n + 1}. Then, we require (n − 1)^5 + a, n^5 + a and (n − 1)^5 + a to all be divisible by b. Since is an ideal of , we can add multiples of b and multiply by integers whilst retaining divisibility by b. Consequently, the polynomials and must also be multiples of b.

Hence, b and n are coprime, and both  and  are divisible by b, so we can conclude (eventually) that . For the case where , all integer values of a trivially work. For the other case of , it suffices to consider the residues of n^5 (mod 11) to find all solutions for a.

Problem 5: Mixtilinear incircle

5. Let Ω be the circumcircle of ABC, and let ω be the mixtilinear incircle touching BC, AC and internally tangent to Ω at the point P. A line parallel to AB and intersecting the interior of triangle ABC is tangent to ω at the point Q. Prove that angles ACP and QCB are equal.

What makes this problem particularly appealing is that there are only five important points. In a situation like this, one would normally find a clever Euclidean construction involving additional points, or apply some algebraic bash. Quite remarkably, we can solve this problem without introducing any more points.

To solve this problem, we’ll use a Möbius transformation obtained by the composition of an inversion in a circle centred on C and orthogonal to ω followed by a reflection in the angle bisector of BCA. This is actually a natural thing to do, since lines through C remain as lines, the mixtilinear incircle ω is preserved, the circumcircle Ω is mapped to a line, and lines AC and BC are interchanged. Our Möbius transformation is an involution, although we don’t need this fact.

The image of Ω is the line A’B’, where A’ and B’ are the images of A and B. It shouldn’t be difficult to convince yourself that B’A’C is a homothetic copy of ABC, so A’B’ is parallel to AB. Also, A’B’ must be tangent to ω and intersect the interior of the triangle, so it is precisely the line used to construct Q. We can deduce, therefore, that P and Q are interchanged, whence it follows that angles ACP and QCB are indeed equal.

The Möbius transformation is colloquially referred to as an inverflection, being composed of an inversion in a circle followed by a reflection in a diameter of the circle. On the Riemann sphere, this operation is indistinguishable from a reflection in a point, which is why it is a natural thing to do. Sahl Khan applied this method to a difficult geometry problem on RMM 2011, and constructed several problems of his own relying on this principle.

Problem 6: Snow White and the Seven Dwarves

6. Snow White and the Seven Dwarves are living in their house in the forest. On each of 16 consecutive days, some of the dwarves worked in the diamond mine while the remaining dwarves collected berries in the forest. No dwarf performed both types of work on the same day. On any two different (not necessarily consecutive) days, at least three dwarves each performed both types of work. Further, on the first day, all seven dwarves worked in the diamond mine. Prove that, on one of these 16 days, all seven dwarves were collecting berries.

This is a thinly-veiled problem asking for you to essentially prove that the Hamming(7,4) code is optimal and unique. Its optimality follows from it being a perfect code; specifically, each of the 128 binary strings of seven digits is within a Hamming distance of 1 from precisely one of the 16 codewords.

Uniqueness is slightly more difficult. We are given that 0000000 is a codeword, and want to show that 1111111 is also a codeword. This must be a perfect code (essentially a space-filling sphere packing on the Boolean lattice), which means that every binary string must either be a codeword or differ from precisely one codeword in a single position. Consequently, every string of Hamming weight 2 (such as 1100000, 0010100 and 0001001) must differ from a codeword of Hamming weight 3 in a single position.

Essentially, we want to group the seven dwarves into overlapping ‘lines’ of three dwarves, such that any pair of dwarves determines a unique line. From this, we can deduce that each dwarf belongs to three lines, and thus there are seven lines (corresponding to codewords of Hamming weight 3). This describes the Fano plane, as Maria Holdcroft noticed when attempting this problem in the actual competition:

If the problem is false (i.e. 1111111 is not a codeword), then we must have a codeword of Hamming weight six. Without loss of generality, this is 0111111, and three of the other codewords are 1110000, 1001100 and 1000011. Now consider the string 0001111. This can’t be a codeword (since it differs from 0111111 in only two positions), so must differ from a codeword X in one position. Clearly, X cannot be 0101111 or 0011111 (since then it would be too close to 0111111). It can’t be 1001111 either, as that is too close to 1000011. Hence, X must be either 0001110, 0001101, 0001011 or 0000111. The first two ‘collide’ with 1001100; the last two collide with 1000011. Hence we obtain a contradiction, and our proof is complete.

A more difficult generalisation of this problem involves 23 dwarves who work for 4096 days, such that for any two days, at least 7 dwarves do different types of work. The unique solution is then given by the perfect binary Golay code.