(The only) Five ISLs that I can remember
Hi everyone! Sheldon here.
I've been working for a while, so I haven't had many opportunities to do Olympiad math recently (or at college, for that matter). However, a few days ago, some of my friends and I had the privilege to attend an event where we met some students who had gone to this year's IMO. Watching some of them stare at geometry diagrams and trying to solve questions they remembered from AoPS certainly brought back memories (maybe not the geometry part in my case). One of my friends mentioned how he'd be unable to remember any math questions now, which led us to discuss how many ISLs we can still remember.
Without much thought, I immediately said "at least 5", which was met with some incredulous looks. I quickly pointed out that there many famous (or infamous) IMO questions out there with memorable techniques, so they clarified that I wasn't allowed to count any IMO questions, and that I had to be able to reproduce the entirety of the question (in a way that someone else could solve). "Surely this still can't be too hard", I thought to myself, as I began to trawl through the depths of my memories.
I quickly thought of two questions, but I realized I was getting stuck. It took me another 1-2 minutes to think of a third, another 1-2 minutes to think of a fourth... and finally, after around 10 minutes, I had thought of 5 ISLs.
For the readers who are currently practicing for MOs, recalling 5, 10, or even 20 ISLs is probably a piece of cake, or maybe even somewhat expected. But as someone who hasn't touched ISLs in years, I came to realize that remembering actual questions is hard. (In my defense, I was also interacting with people while I tried to think of questions.) Perhaps this is a meta-point too: even though I found that I could remember way fewer questions than I thought, it felt like I had remembered more because I associated so many questions with techniques or insights which I could actually remember (like "the question where you can use this trick/method to obtain that"), and ultimately, it's remembering the learning points from each question that's more important.
Nevertheless, since I could apparently only remember 5 ISLs out of several hundred (I did eventually think of a couple more over the next few days), I thought it'd be nice to note them down and think about what made them so memorable. So it's time for a trip down memory lane...
(Note: these questions are unsurprisingly combi-focused because it's infinitely harder to remember every detail of a typical algebra/NT problem, and geometry is just algebra anyway. If the conditions for recalling problems had been relaxed a little, I'd probably have been able to come up with a more balanced mix.)
I figured that I'll list the problems in the order I first encountered them, so we'll start with a throwback to a question from the 2010 ISL:
Problem 1 (2010 C1)
In a concert, 20 singers will perform. For each singer, there is a (possibly empty) set of other singers such that he wishes to perform later than all the singers from that set. Can it happen that there are exactly 2010 orders of the singers such that all their wishes are satisfied?
This problem was memorable because it was the first question we received in Math Club (Core), back when it first became a thing. For our first session, I walked into the classroom, saw an A4 paper on my table with only this question on it, and got down to work.
I first tried to see what numbers I could construct a set for. Clearly 1 worked, and we could get n! from n singers. If we could get a orders from m singers and b orders from n singers, then we could get ab orders from (m+n) singers. Also, we can get n orders from n singers, so we can construct every number... but 2010 > 20. Sad.
Since the question is a yes/no question, I must surely have spent some time pondering if a construction was even possible. I don't recall any parts of this thought process, so I either didn't get very far or just assumed that it had to be possible, which is perhaps dangerous in retrospect. In any case, two hours later, I had tried constructing in many different ways - I mostly had figured out that I probably wanted to find a construction for 67 since I already had a neat construction for 30 - but I still hadn't solved the question, and I don't think anyone around me was able to either.
I don't think there was much of a key insight/novel learning point to this question; the actual construction(s) isn't very mindblowing, and I'll spare the reader the details. On the contrary, the question stuck with me because of how accessible both the question and the solution were: instead of requiring some elegant approach or sophisticated analysis as many combi questions do, the question just required some SMO Round 1 (somewhat like AMC/AIME)-level counting in an exploratory way. In a way, it felt somewhat cute that we were trying to set a question to achieve a desired answer.
Most of us who were in the room at that time would probably be able to solve this question in a matter of minutes now. But for someone who was just trying to enter the realm of ISLs and more advanced proof-based questions back then, this was a very welcoming introduction which I appreciated. For those who are looking to make the same transition now, I'd encourage you to start with some questions like these too: nothing too fancy and probably too mundane to enter any problem collections' hall of fames, but easy to think about even if you don't solve it. And for those who are past the stage of practicing 1's and 2's, it's a nice reminder of how simple some ideas in Olympiads can be.
Problem 2 (2013 C3)
A crazy physicist discovered a new kind of particle wich he called an imon, after some of them mysteriously appeared in his lab. Some pairs of imons in the lab can be entangled, and each imon can participate in many entanglement relations. The physicist has found a way to perform the following two kinds of operations with these particles, one operation at a time.
(i) If some imon is entangled with an odd number of other imons in the lab, then the physicist can destroy it.
(ii) At any moment, he may double the whole family of imons in the lab by creating a copy $I'$ of each imon $I$. During this procedure, the two copies $I'$ and $J'$ become entangled if and only if the original imons $I$ and $J$ are entangled, and each copy $I'$ becomes entangled with its original imon $I$; no other entanglements occur or disappear at this moment.
Prove that the physicist may apply a sequence of such operations resulting in a family of imons, no two of which are entangled.
Fast forward 2-ish years to the summer of 2014, when I'm preparing for my first IMO with the rest of the Singapore team. The above problem appeared as Problem 5 in a 2-day mock exam we were given - a critical position for many medal cutoffs - and I had plenty of time to work on it after a routine Q4.
I had high hopes of solving this question, but no obvious approaches stuck out to me. I first checked for all the "elegant" methods (invariants/monovariants/considering max/min etc) to no avail, so I fell back on one of the more generally applicable approaches - induction. Inducting on the number of vertices (with some sensible assumptions) seemed like the most natural choice, so I began to work on that, but it only led me down one rabbit hole after another.
Nevertheless, as someone who believes pretty strongly in solving one question before moving on to the next (within reason, of course - one prerequisite is that you'd have to believe that the questions are indeed in a "usual" order of difficulty, which is true for the IMO but not true for some other competitions), I plodded on. Bashing one case led me to a smaller subcase, and an even smaller one... With time running out, I hastily found some arguments to wrap up each case and say that I was done.
Was I actually done? Honestly, I had no idea myself, which was perhaps one of the largest red flags. In my eagerness to work through the cases and reach some kind of conclusion I had lost all my trains of thought, and failed to gain any intuition on the problem. When our trainers reviewed our solutions, they soon discerned that my "solution" was just a bunch of ideas thrown together, and each line took the proof in a completely different direction from the previous, culminating in absolutely nothing.
For those who aren't familiar with the question, there's one really neat solution using (redacted, in case anyone wants to find it for themselves), and a few others that use induction/monovariants in appropriate ways. The first solution felt magical to me when I first saw it - it still feels magical, to be honest - and it's one of those concepts that you'd only really remember after a problem like this comes out, which is one of the reasons the question became so memorable for me. But maybe, if I had spent more time trying to understand the problem and think on a larger scale before letting myself get bogged down by the details of a seemingly promising approach, I'd have had a better shot at finding a solution that made more sense.
Problem 3 (2014 A3)
For a sequence $x_1,x_2,\ldots,x_n$ of real numbers, we define its $\textit{price}$ as\[\max_{1\le i\le n}|x_1+\cdots +x_i|.\]Given $n$ real numbers, Dave and George want to arrange them into a sequence with a low price. Diligent Dave checks all possible ways and finds the minimum possible price $D$. Greedy George, on the other hand, chooses $x_1$ such that $|x_1 |$ is as small as possible; among the remaining numbers, he chooses $x_2$ such that $|x_1 + x_2 |$ is as small as possible, and so on. Thus, in the $i$-th step he chooses $x_i$ among the remaining numbers so as to minimise the value of $|x_1 + x_2 + \cdots x_i |$. In each step, if several numbers provide the same value, George chooses one at random. Finally he gets a sequence with price $G$.
Find the least possible constant $c$ such that for every positive integer $n$, for every collection of $n$ real numbers, and for every possible sequence that George might obtain, the resulting values satisfy the inequality $G\le cD$.
This question was memorable, in part, for its historical significance. To give some context, Singapore's IMO Team Selection Test used to consist of 10 questions - 4 on Day 0 (which was half-weighted), 3 on Day 1, and 3 on Day 2. Generally 4/6 questions on Day 1/2 would've been seen as a "decent" performance, similar to solving 4 questions at the IMO. However, in the 2015 selection test, a relatively easy Day 0 meant that a handful of students went into Day 1/2 with perfect scores, and somehow Day 1/2 were both easier than expected too. It became apparent that some students had solved all 10 questions, and several more had dropped points on at most one. True enough, the cutoff for that year was 49/56 - 2 students had perfect scores, 2 more had near-perfect scores, and the last two had missed the same question.
The question was the problem above, which was Problem 3 of Day 1, and one of the 2 qualifying students who missed it was me.
I can still remember the range of feelings I had between Day 1 and results day. I didn't think much about failing to solve this question during the test - it was a Problem 3, and failing to solve Q3/6's on the IMO/TST was expected, wasn't it? I emerged from the test thinking that I had turned in a "routine" performance which should've kept me in a safe position, only to hear rumours that many people had aced the entire test. Someone then told me the solution, which seemed so glaringly easy in retrospect, and I couldn't believe how I'd missed it the whole time. I then told myself that I'd have to try to solve all 3 questions on Day 2 as a result, and I did, only to find that solving 3 questions on Day 2 was the norm too. I spent the following week pondering just how high the cutoff could be, and hoping I wouldn't rue missing this question.
After the results were released, we could finally look back and comment on what an extraordinary paper it had been. It felt like such a freak result, and yet it was real, and it challenged many of the principles and strategies I had believed in. The maxim that solving Problems 1/2/4/5 and scraping partials on 3/6 was always the gold standard didn't have to hold true. Q3/6's were usually seen as out of our reach and there for us to earn as many marks as we could, but when they could turn out to be surprisingly easy, was it still safe to approach them with such a mindset anymore?
Sometimes such a mindset could turn out to be detrimental when the problems were actually much more accessible than one would've expected, as they'd subconsciously fail to notice easy ideas while getting fixated on hard ones. During the test, I was mostly stuck because I'd somehow become convinced that the numerical answer to the question was something else, and never wondered if the answer I was trying to prove could be wrong. This seems like such a rookie mistake - trying other values (or proving yes instead of no) when one gets stuck is one of the most basic pieces of advice that a student is exposed to, but it somehow didn't cross my mind the entire time. Maybe if I'd had treated this like a Problem 2, or a question that I was expected to solve, the warning bells would've gone off in my head, because I'd have actually been alarmed that I wasn't solving it. But in retrospect, I think that treating the question like a "bonus" instead of an expectation was probably one of the reasons why I forgot all the advice that I had known. I'm glad that I was able to react to Day 1 and resolve to just try to solve everything on Day 2, since that turned out to be necessary too.
In some ways, the 2015 NTST was ahead of its time. After many years of rather mundane IMO medal cutoffs (around 4 questions for a gold, 3 questions for a silver, and 2+ question for a bronze), the 2022 IMO saw a sudden spike in cutoffs, where 5 questions was required for a gold and 4 questions wasn't even enough for a silver. This persisted at the 2023 IMO, although the cutoffs were slightly lower. On the other hand, the 2015 IMO itself saw a deviation from the normal cutoffs in the other direction: the gold cutoff was 26, the lowest in many years, and the record for lowest gold cutoff was again broken in 2017 with 25. With the recent increase in volatility of cutoffs, aiming to solve certain questions and partial others has only become more risky. While it's probably still true that there's some differences in facing a Q3/6 instead of a Q1/4, one thing I learned from Diligent Dave was that there's some underlying principles when attempting any problem, and these shouldn't go out of the window just because one doesn't expect to solve it.
Problem 4 (2014 C4)
Construct a tetromino by attaching two $2 \times 1$ dominoes along their longer sides such that the midpoint of the longer side of one domino is a corner of the other domino. This construction yields two kinds of tetrominoes with opposite orientations. Let us call them $S$- and $Z$-tetrominoes, respectively.
Assume that a lattice polygon $P$ can be tiled with $S$-tetrominoes. Prove that no matter how we tile $P$ using only $S$- and $Z$-tetrominoes, we always use an even number of $Z$-tetrominoes.
Compared to the previous 3 problems, this one is much less historic. It appeared as the second question of one of the mock papers during the 2015 IMO training sessions, and its statement is pretty bland.
Unlike the previous 3 questions, I actually solved this one during the test, and I mostly remember it because of how I solved it. The setup of the question made coloring seem especially appealing. To obtain the desired conclusion, we'd probably want some coloring where $Z$-tetrominoes must cover an odd number of some color, while $S$-tetrominoes don't. But what coloring would fit this? All the colorings I could think of didn't seem to work.
Undaunted, I decided that it was time to bash some combi. Since we know what conditions the coloring needs to satisfy, we can just start by fixing the colors in some cells, throwing $S$ and $Z$-tetrominoes on the grid to solve for all the neighboring colors, and repeat until we obtain a recognisable pattern. Of course, the first problem in doing this is knowing what colors to start with... but what if we didn't need to know that either? If we start by choosing the colors of $n$ cells, then there's only $2^n$ ways to choose them, so we can just check each one till we find one that works. (The actual number of cases would become much smaller once we factor in symmetries and other patterns that we can skip past easily too.)
I don't remember what the value of $n$ I required was, or how many cases I checked in total (I think it was around 6 and 10-20 respectively), but I found the pattern I was looking for within an hour, and everything clicked. I don't know if I'd had been able to find the coloring through any other means, and bashing cases until one works still feels like the most intuitive approach to me. It started a trend of me cheekily saying that "everything is algebra - including combi", because there were often ways to reduce problems to checking a finite amount of cases, which were manageable if handled intelligently (brainless bashing is usually too inefficient to be successful).
Over the next few years, I came to rely on this saying several times, most notably at the 2016 IMO, where I was reduced to showing that the sum of each row, column and diagonal in a 3x3 square couldn't be 1 (mod 3) in Problem 2. (I listed all the possible values of the upper left L in mod 3, and showed that none of them resulted in a solution.) Listing cases can seem exhausting or uninspiring, but when done efficiently, it can be an art in itself too.
Problem 5 (2010 C5)
$n \ge 4$ players participated in a tennis tournament. Any two players have played exactly one game, and there was no tie game. We call a company of four players bad if one player was defeated by the other three players, and each of these three players won a game and lost another game among themselves. Suppose that there is no bad company in this tournament. Let $w_i$ and $l_i$ be respectively the number of wins and losses of the $i$th player. Prove that $$\sum_{i=1}^n(w_i-l_i)^3\ge 0.$$
We finally end on a light-hearted note by visiting the oldest ISL on this list, which I attempted after I had already graduated and my IMO days were long over. A junior had asked me to try solving this question, and I figured I'd might as well give it a shot.
My first thought was how to think about the $w_i - l_i$ condition. Since $w_i$ is the number of wins that player $i$ has and $l_i$ is the number of losses that player $i$ has, what if we just let each win have a value of 1 and each loss have a value of $-1$, so that $w_i - l_i$ is just the sum of all these values?
The funny thing is that this method just works. I couldn't believe that all the terms just expanded and came together so beautifully when I first did it, so I checked it again and again before showing it to my junior. Eventually I became convinced that I couldn't find anything wrong with it, and neither could he, so I called it a day and posted my solution on AoPS.
It's sometimes easy to have expectations of what a solution to a question of a certain difficulty should look like - a solution to a C1 should probably look different from a solution to a C3, C5, or C7. But when one chances upon a solution that feels intuitive, the problem can feel out of place. This doesn't imply that the question itself is misplaced: just because a solution feels obvious to one person doesn't mean that it's obvious to most. Everyone thinks about math differently despite the trainings we may go through. On the other hand, just because we expect the solution to be obvious (or unobvious) to most doesn't mean we should expect it to be the same to ourselves, which is something that we often overlook, and keeping this in mind can lead us in directions we might otherwise forget to explore.
(Another example in the same vein would be the 2016 IMO Q6, which was a C7, but I wasn't allowed to use it here since it appeared in the IMO, and I don't remember the details of the question well enough anyway.)
Comments
Post a Comment