[IMO 2012 Part 4] The Inequality of Broken Dreams

I could spend all day coming up with post titles like this one. Really, I could. Anyway, after receiving the letter gently reminding me to turn in the official IMO report in Chinese, I finished that first and turned it in. This, plus the fact that I don’t have any way to do any of my summer homework yet, should make continued blogging much easier.

These months of preparation and anticipation, and in just over two days it will be behind us forever.

Thus were my thoughts at 3:30 in the morning, which were a much worse method of preparation than that which I used for the APMO, which involved trying for the first time to put my compass in its box and staring at a cryptic crossword. Twisted thoughts as I lay innocently in bed, trying to preserve my spirit and mathematical function. I got up at 6:30 and ate a breakfast nervously with the team.

We dispersed into the contest hall. Flat squarish white tables in orderly rows greeted us. They were considerably smaller than the arm-span tables we had last year in the Netherlands’ stadium, but the space was still ample compared to the ones we took our practice tests on at home. I floundered a bit looking for whoever was supposed to check our stuff for forbidden items, but none of the proctors paid any attention to that, so I flipped through my own jacket pockets paranoidly.

But preparation was too brief, and there were at least fifteen minutes left with nothing to do except try not to panic. I managed to fill these fifteen minutes by doing elaborate breathing exercises, raising and flapping my arms, counting down seconds, focusing on a color word, meditating badly, clearing out everything nonmathematical from my mind with a symbolic gesture. This is not a very coherent description, but I wasn’t feeling very coherent.

I opened an eye halfway and watched as the clock ticked down the last few seconds. The starting signal sounded. I opened up the problem envelope…

(nonessential expressions deLaTeXed; you’re welcome)

Problem 1. Given triangle ABC the point J is the centre of the excircle opposite the vertex A. This excircle is tangent to the side BC at M, and to the lines AB and AC at K and L, respectively. The lines LM and BJ meet at F, and the lines KM and CJ meet at G. Let S be the point of intersection of the lines AF and BC, and let T be the point of intersection of the lines AG and BC. Prove that M is the midpoint of ST.

(The excircle of ABC opposite the vertex A is the circle that is tangent to the line segment BC, to the ray AB beyond B, and to the ray AC beyond C.)

Point, point, point, segment, segment, segment. Pretty unremarkable G1 fare is all I have to say about it: not too clean and not too ugly, not too simple and not too complicated. For a couple moments while solving I thought M was actually defined as the midpoint of BC because of its name. But the solution was smooth: chase angles, find the inevitable miraculous concyclicity, and patch it all up with two applications of Menelaus with lots of equal tangents that canceled nicely, plus two parallel line ratios for good measure. Thirty-five minutes. No problem. There do seem to be shorter, clearer ways to the destination, but I doubt that any more intuitive paths would have been significantly more time-efficient for me.

Time to face the nightmare.

Problem 2. Let \(n\ge 3\) be an integer, and let \(a_2,a_3,\ldots ,a_n\) be positive real numbers such that \(a_{2}a_{3}\cdots a_{n}=1\). Prove that

\[(1 + a_2)^2 (1 + a_3)^3 \cdots (1 + a_n)^n > n^n.\]

Alas, all of our begging and pleading beforehand with our leader and OAs was not enough to save us from facing the first IMO inequality in years. I was no longer as hopelessly unequipped against inequalities as I might have been a year ago, but I still only had the same bag of mindless manipulations: expand, clear the denominator, complete the square; rearrangement, AM-GM, Jensen; in extremely lucky cases, maybe a Cauchy-Schwarz, Schur, or (yeah, right) Muirhead. And here I was facing an asymmetric \(n-1\)-variable inequality without an equality case and a typically inscrutable condition as the second problem of the IMO. Seven points that looked like they would cost me all hopes of getting another silver. The horror!

With fingers crossed, I took a look at the combinatorics.

Problem 3. The liar’s guessing game is a game played between two players A and B. The rules of the game depend on two positive integers k and n which are known to both players.

At the start of the game A chooses integers x and N with \(1 \le x \le N.\) Player A keeps x secret, and truthfully tells N to player B. Player B now tries to obtain information about x by asking player A questions as follows: each question consists of B specifying an arbitrary set S of positive integers (possibly one specified in some previous question), and asking A whether x belongs to S. Player B may ask as many questions as he wishes. After each question, player A must immediately answer it with yes or no, but is allowed to lie as many times as she wants; the only restriction is that, among any k+1 consecutive answers, at least one answer must be truthful.

After B has asked as many questions as he wants, he must specify a set X of at most n positive integers. If x belongs to X, then B wins; otherwise, he loses. Prove that:

  1. If \(n \ge 2^k\), then B can guarantee a win.
  2. For all sufficiently large k, there exists an integer \(n \ge (1.99)^k\) such that B cannot guarantee a win.

It was a massive text wall, the unique trademark of combinatorics problems, but I had no trouble grasping the essence after copying it down and getting rid of all the technical-issue wording. I tackled it right after crashing through #1. If there was one thing I learned from last year, it was not to trust the committee at determining relative difficulty.

Fiddle with the essence for intuition. Alright, so the problem is equivalent to disproving one integer and inducting. This is messy, let’s try some small cases. Zero… not allowed and completely trivial, never mind. \(k=1\), then? I threw questions together in vaguely patterened chunks and a mess of a strategy came up. Two questions with 1 and 2, reverse, interlace with 3s and push out a contradiction, boom.

It didn’t generalize. At all.

Okay, so I’m not that good at combinatorics.

Deep breaths, let’s give #2 a shot.

I expanded #2 for n = 3 and couldn’t do anything; my best attempt was just throwing AM-GMs together and it led nowhere. I had a vague idea that I ought to find the minimum for the left-hand-side and that it didn’t occur when the variable equaled 1, but I wasn’t sure how to put it into practice. Really. I was absolutely unprepared for inequalities.

I took a couple logs looking for Jensen or some other convexity argument, but the lack of an equality case kept bothering me. Finally I gave up looking for elementary solutions and tried to bash it with Lagrange multipliers, probably for the first time in over a year. Luckily (or not!) I had reviewed it on Wikipedia just a couple days before. It was actually straightforward, though tedious, to reduce everything to one inequality in one (auxiliary) variable with one constraint, but it was still impossible for me to see why the inequality would hold.

It was starting to look like both #2 and #3 would be hard fights.

Back to #3… I came up with something, started writing my solution, realized it didn’t work but that was okay because there was a good deal of preparatory work and lemmas that were still usable, fiddled around and came up with my new strategy. At first I thought it was too simple to work and that it would allow an asymptotic that would contradict the second half of the problem, but after looking for quite a while for a mistake, I convinced myself that it worked. I had avoided overcomplicating the problem: another of my weaknesses sidestepped, and the only way I could fail to solve an easy combinatorics problem (not saying that #3 is easy, mind you). I finished the write-up for #3.1, but in my estimate, that still only netted me 3 points: so far, hardly an ideal result to walk away from Day 1 with. There was only about an hour left, and I was now faced with a big decision: do I shoot for the second half? Do I go back and try #2, my eternal algebraic nemesis? Or do I try to multitask and hope that at least one works with only half the effort?

I went back to #2. I realized that it was only a freaking #2, last year was severely anomalous and even then the solution was simple, there had to be a simple solution using something easy… maybe the easiest nontrivial inequality I knew, AM-GM. Suddenly I realized how I could cut up the constant for AM-GM in order to get a clean variable term of a_2a_3a_n after applying all the exponents… and what do you know, everything else telescoped perfectly into the RHS. I facepalmed a couple times. I wrote down the solution, one spacious page compared to the bulky ten pages of scrappy bashing behind it. I facepalmed a couple more times. People around me may have cast sideways glances.

There were only maybe twenty minutes left, so after paranoidly checking everything I had written and jotting down all the header information as quickly as possible, I scribbled some intuitive shots in the dark for #3.2. Guess: you need to exponentiate a constant \(c^r\), likely to be asymptotically squeezed between \((1.99)^r\) and \(2^r\), but maybe not. Guess: for each potential x, you need to consider r as how many lies in a row A would have told already if it were the right x. Guess: you sum them and sort of compare the two sets. Happily, I was on the right track and managed to get 1 point of partial credit from those twenty minutes, but I was too panicked to continue, and after the test, was too lazy to keep trying. I put everything in the right order in the right folders.

And Day 1 was over. As I left, I noticed a guy sitting a couple seats ahead of me had drawn his geometry diagram on the answer folder, which was something you weren’t supposed to do, according to Kazakhstan precedent.

Later, for problem 3, I would see the continuation of my method in three different places: (1) AoPS, second solution for that part, because the first one references Tychonoff and Lovasz Local Lemma and after looking them up on Wikipedia I decided to postpone understanding that proof for a long time; (2) Facebook where HPW, our combinatorics master from last year who got an extra point on the windmill for proving that the area where the line didn’t pass over had to be connected, decided to solve them by himself; (3) the marking scheme.

It works! 1 point extracted from 20 panicked minutes! (And I might have had an extra point if I had written c = 1.995… oh well. Time pressure sucks. During our mock tests what usually happened is we solve one or two problems and stare blankly at the third for an hour or so.)

I met up with WL and CPT and we discovered that we were now faced with a real-time coordination game: how, without any strategizing beforehand, do we go about finding the other three people in the team? Most of the contestants were standing about doing the same thing, and some had already sat down in the chairs (I thought they said we weren’t supposed to sit there…) and were discussing the problems fervently. It would be hard to find anybody in the crowd. We found the professors after walking up and down the balcony a few times, and then, after a long while, learned that the rest of the team had returned to their rooms, thinking we would do the same.

Game theory is hard.

Problem analysis (yet again!) I’m not going to comment specifically on my teammates’ performances, only roughly, just FYI.

  • #1. Easy, unremarkable geometry. Some people say it was too easy. Last year’s #1 was “too easy”. Or I just continue to suck at geometry; who knows? Our team had no problem, obviously, because I’m probably the worst at geometry in it.

  • #2. Okay so there are a zillion people who repeat that this is too easy for an IMO #2 because a complete solution consists of five lines at the absolute maximum. I mean. Okay, AM-GM is an easy technique, term-splitting is a little harder but perfectly familiar, but why would you want to apply that to this problem? I received an AoPS comment that says you can think of it when you try to overcome the asymmetry. I still can’t make it seem justified to myself. And there is a calculus solution, but it’s not straightforward.

    Even now, supposing I were cloned before the test, I would not bet on my clone solving #2 under test conditions. I don’t know how I thought of it. Too much metagaming?

    Also, if you don’t think of using AM-GM and aren’t smashingly excellent at calculus, partial credit is nearly impossible no matter how much time you use. So, all in all, does this remind you of any problem from last year? It does to me.

    It didn’t break my dreams, somehow, but overall it hurt our team a lot.

  • P3. Alright, it’s a pretty cool combinatorics problem. The sad thing is that there are two parts, each takes a whole lot of time to think through, and the help they give to solving each other is virtually nonexistent (I think there’s a little shared intuition at most). The point-efficiency of this problem is therefore rather low, even though, in my humble opinion, it’s not that difficult for a P3. This seems to be an overall theme for the entire test.

    All the basic strategies I went through in our cross-training (largely a very, very brief cover of Engel) were pretty much useless here. The closest thing I can think of that I mentioned is the idea of corresponding to 01-strings. But the followup is just found through exploration and the 1.995 weighting probably requires a little experience with problems where you prove asymptotics. So the number of points our team got here is also very small, including one fakesolve with a sadly broken induction. I don’t get how they can apply the probabilistic method after citing a bunch of scary college-level-sounding names. So even if I learned the probabilistic method carefully I don’t think I could possibly have gotten that solution.

I do not remember much of what we did that afternoon; maybe a few more problems, maybe a few games of the ripoff of the ripoff of Bang! we brought. That’s Day 1 for you.

(note: the commenting setup here is experimental and I may not check my comments often; if you want to tell me something instead of the world, email me!)