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 (\oplus) 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 P(n) = \dfrac{n^5 + a}{b} 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 b \mathbb{Z} is an ideal of \mathbb{Z}, we can add multiples of b and multiply by integers whilst retaining divisibility by b. Consequently, the polynomials n^5 - (n-1)^5 = 5n^4 - 10n^3 + 10n^2 - 5n + 1 and (n+1)^5 - n^5 = 5n^4 + 10n^3 + 10n^2 + 5n + 1 must also be multiples of b.

Hence, b and n are coprime, and both 20n^3 + 10n and 10n^4 + 20n^2 + 2 are divisible by b, so we can conclude (eventually) that b|11. For the case where b = 1, all integer values of a trivially work. For the other case of b = 11, 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.

egmo-q5

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.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

9 Responses to EGMO synopsis

  1. Andrew Carlotti says:

    Note that problem 6 does not require you to show such a schedule is possible. Thus the stuff involving the Fano plane is not necessary to solve the problem, and you merely need to consider the Hamming weights of the points adjacent to each ‘codeword’. The only way in which doing it for 23 dwarves, etc., is harder, is that the arithmetic involves bigger numbers (nothing bigger than 7 digits though).

    • apgoucher says:

      I disagree. The construction of the binary Golay code is far more complicated than that of the Hamming codes, and (unlike the Hamming codes) it is entirely non-obvious that it should even exist.

      Anyway, I would love to be proved wrong. How would you solve the problem in the case of 23 dwarves?

      • Andrew Carlotti says:

        I didn’t say anything about constructing the Golay code. I only stated that it is possible to prove that, if one exists, and 00…00 is in it, then 11…11 is also in it. Here’s Daniel’s solution to the original EGMO problem (mine is identical, and I couldn’t be bothered to write it up). The extension to 23 dwarves should be fairly obvious.

        “EGMO 6
        view it as finding columns at least three swaps away from each other. We may as well use 0s and 1s to represent the jobs. It is helpful to think of the 7 dimensional cube, or graph theory, though unnecessary.

        supposing we can find a 16 column schedule for the 2^7 3-swap problem. Then for each of those 2^4 columns, there are a total of 8 at most 1 swap away (include itself). But none of these 16 octets of columns can share an element, as that would imply those two columns were only 2 swaps away.
        But 8×16=2^7 so every column is either one of our 16 or 1 swap away from a unique one of the 16.

        So we know we start with a column full of zeros. obviously among the Column 16 none have 1 or 2 zeros in. there are 21 columns with two zeros, and so in our Column 16 we need some columns with 3 zeros in to be 1 swap away from them. Each column with 3 zeros yields a set of 3 columns with 2 zeros that are 1 swap away. So 7=21/3 of our Column 16 necessarily have 3 zeros.

        Then, similarly 7 have 4 zeros to cover the 35=7+4×7 3 zero columns. Then none have 5 or six similarly, and the last one has to be a column of 1’s.”

        • apgoucher says:

          Right. I admit that considering the 4-subsets of {1,2, …, 23} will allow you to prove that there must be 23C4 / 7C4 = 253 codewords of Hamming weight 7, and then considering the 5-subsets will give you (23C5 – 253*(7C5)) / 8C5 = 506 codewords of weight 8. And then you can consider the 8-subsets and (after some arithmetic) deduce that there are (23C8 – 253*(16C1) – 253*(16C2)*(7C1) – 506 – 506*(15C2)*(8C1)) / 11C8 = 1288 codewords of weight 11. Then considering the 9-subsets will give you (23C9 – 253*(16C2) – 506*(15C1) – 506*(15C2)*(8C1) – 1288*(11C9)) / 12C9 = 1288 codewords of weight 12.

          It looks as though you could, in principle, continue this method to obtain the 506 codewords of weight 15, 253 codewords of weight 16, and then 1 codeword of weight 23 (see sequence http://oeis.org/A002289 for the complete weight enumerator). So I suppose you win. Nevertheless, it’s significantly more complicated than the 7-dwarf problem, not least because we’re trying to tile the space with spheres of radius 3 instead of 1.

          • Andrew Carlotti says:

            Oh, right, I forgot the spheres now had radius 3. But at least it would work without requiring any new ideas.

  2. Frederic Harnald says:

    For Q5, can we come up with a name to replace the portmanteau ‘inverflection’? Reciprocation might do.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s