July 23 – Day One
It’s 1am. I know it because I stole a glance at the clock two minutes ago and it said 12.58am, and I’ve been counting the seconds that pass, one after one after one, tick tock tick tock. I face the IMO in the morning, and I can’t sleep.
I’ve always had sleeping problems, but I can’t believe that it’s happening right here right now, at the worst possible time in the worst possible place. If you’ve ever had insomnia, you know the feeling – the sick crawling feeling as you lie perfectly still in bed and feel exhausted but your mind is running a goddamn marathon. I went to bed at 9 and I’m still awake at 1. This cannot be happening.
I got out of bed and went onto the balcony. Irotama was right next to the sea, so the sounds of the rolling waves crashing onto the sea were audible. I sit down and just stare into space blankly. I’m still not sure how long I was outside, but that was the kicker. I started to calm down, my heartbeat slowed, and I regained my logical train of thought. I inhaled and exhaled for god knows how many times. Meditation. It works. I went back to bed and woke up at around 4:30am. I felt great.
On to the exam, then.
First impressions of the paper are pretty important. Right off the bat, we have a number theory for P1, combinatorics for P2, and a geometry for P3. What else could I do other than feel good? Let’s go.
P1: I traditionally take quite a while to solve NT’s, and I chose to do it this way instead of trying to find some magic path to the solution. Small cases first: for k=1 everything was trivial, so let’s move on to k=2. This took up quite a chunk of time before I found the odd/even solution. Firstly I was convinced that there wasn’t an obvious closed form construction, so I thought of induction.
As it turns out, induction actually works, but I didn’t find it. After some more thinking, I went, “OK, we have 2^k and k terms, so um, binary.” I played around with this idea for a while. Somewhere along the way I wrote down the m_i for n equals power of 2. There was something strange going on with my examples because they were just too nice. After a minute two things hit me:
1. the terms telescope from the denominators and numerators, and
2. I just had to ensure that the numerator divides the denominator.
So then from this point it was really clear that it was equivalent to just bitwise flipping on n with the restriction that you can’t flip bits after the last 1, and that you only could use each bit once. So…that was it, 9:45 solve.
After writing a second page linking this game and the actual problem, I moved on to P2 at 10am, knowing that I had went a little overtime on this one.
P2: Problem statement was rather long-winded, but it was pretty clear. Given some red and blue points in the plane, split them into regions with straight lines such that no region contains two points of the same color.
This didn’t seem hard at all. Looking at the small cases, I found upper bounds for the small cases, then proved the respective lower bounds through case analysis. By this time it was quite clear what the answer should be for the general problem. I took a chance and started off trying to prove the upper bound. After some thinking I found a short proof for my upper bound: a convex polygon with points grouped on both sides of the polygon. This was good: one direction already done, and I had 3 hours left. Time for the lower bound. I tried the first thing: an explicit construction.
This turned out pretty badly, so I changed my approach quickly. After several failed attempts, I was beginning to get frustrated. I had 2 hours left, and this may leave me with insufficient time to solve problem 3, even if it was a geometry problem. I raised my WC card and went for a bathroom break. Mind cleared, I returned to my seat, and spontaneously started induction.
This…turned out to be the right approach: I soon saw how I could remove two points if I considered the convex hull. This was, however, assuming that there would be points of both colors on the convex hull, which still left a huge case to be considered. I played around with this notion for a while before giving it up and restarting induction. This was when I thought of the halving line argument from two years ago. I soon found a suitable line to split the plane into two smaller configurations that worked, after an extension of the result to the even numbers. I started writing my proof, which took quite a few pages. Finished, I glanced at the clock. 1 hour left. This was bad.
P3: I went into hyper drive. Reading the problem statement for problem 3, I decided that it would be good to construct it with the incircle instead of the excircles and I began drawing my diagrams. I noticed that the converse of the problem statement seemed to be true, and moreover, the given circle seemed to be quite easy to access just by using the properties of the tangency points. I stared at the diagram for 15 minutes as I became increasingly flustered. One shot at a perfect day 1, and I had 30 minutes left. Oh no oh no oh no…I couldn’t see anything. 15 minutes before the end of the competition, I gave up on problem 3 in favor of checking my solutions to the first two problems. I read and reread my proofs, making sure that I didn’t miss any special cases, no wording errors, no silly mistakes. A loud beeping startled me, and the invigilators announced the end of the competition. Ding ding ding. Day 1 was over. I put my solutions in the folders and walked out of the exam hall feeling frustrated.
- – -
I walked into the sea of contestants and found my teammates. ‘How many did you get?’ was the question that was repeated over and over again by everyone. ’1 and 2′, I would reply. It turned out that none of us had managed to settle problem 3, but four of us had complete solutions to the second problem, and another had made significant progress on it. Five of us claimed complete solutions to the first problem. We discussed our solutions as buses arrived to ferry us back to the official hotel.
I talked to Si Wei about the second problem. He was saying how he had misunderstood the problem statement and only discovered the error an hour before the end of the exam, but managed to fix it in the end. I was amused at how he could misunderstand a problem on such an important competition, and started describing my solution to him.
While talking about my extension to the even cases, I explained my answer to him. Upon hearing this, he looked confused. ‘No, this isn’t the answer,’ he said, and presented me with a smaller case of 4 points and said that it was impossible to split this configuration with only one line. I pointed out the obvious solution to him: a line dividing it into two with one point of each color in each region. “But there’s still two points of different color in this region,” he replied.
Halfway through the debate, I suddenly realized that we were talking about different problems. Heart pounding, I read the problem again…and again, and again. Si Wei was right. I had misread the problem. I held my head in my hands, speechless for a minute, and tried to get over the fact that I had just virtually thrown away a shot at a silver or gold medal. I was speechless, struck dumb. I didn’t know how to react.
I misread an IMO problem.
Eventually I got over it. Regardless, we still had a pretty good performance on Day 1. Back at the resort, we went around asking teams how they performed. As it turns out, a surprising number of people reported that they couldn’t finish P2, including some members of the US team. Very few people claimed solutions to P3: one from the US, one from Canada (Calvin) and a few from China and Korea. The Hong Kong team got 5 solves for P2, and we were quite puzzled indeed by our survey.
I went straight to bed after dinner. Thankfully, I got a good sleep this time around.