Visualising combi, ft. IMO 2024/3

(Glen here.)

I had the privilege of being a Coordinator at this year's IMO, which, along with some extra perks such as a lot of free food and being able to witness Singapore's 3rd-best ever team placement (!), came with the benefit of seeing this year's IMO problems a couple of days before everyone else. This also meant that I had a couple of days to make predictions about how each problem would be received, and I turned out to be wildly wrong about one problem in particular: Problem 3. I'd found this a lot easier than its single-digit solve-rate would suggest (this took me less than an hour without paper), and so I figured that I should write something about my thought process behind this problem. For obvious reasons, I don't have an actual record of solving the problem, but everything has been reconstructed to the best of my memory.

The problem

I first saw this problem on the Saturday before the IMO. There was a nice fancy dinner for Coordinators and Leaders, and I'd gone to say hi to Audrey, a former Singapore contestant whom I'd first met at the previous Bath IMO, where she was a Coordinator and I was an Observer B. The IMO problems had been voted in an hour or so before, and she'd got ahold of the combi ones. And hence I got my first glimpse of the IMO 2024: the now infamous Turbo problem, and:

(IMO 2024/3) Let $N$ be a positive integer and let $a_1, a_2, \ldots$ be an infinite sequence of positive integers. Suppose that, for each $n>N$, $a_n$ is equal to the number of times $a_{n-1}$ appears in the list $a_1,\ldots,a_{n-1}$. Prove that at least one of the sequences $a_1,a_3,a_5,\ldots$ and $a_2,a_4,a_6,\ldots$ is eventually periodic.

But it wasn't until much later that night (after much eating, pub quizzing, and catching up with people I hadn't seen in a year) that I began attempting this problem.

Initial observations

Fast forward to 2.30am on Saturday night (or Sunday morning, depending on how you look at things). I'd finally figured out the solution to Turbo, and for obvious reasons, my mind was racing too much for me to go to sleep. And so while lying in bed, I started thinking about the other combi problem.

The obvious thing to do is to try examples. Here's what the sequence looks like when $N=1$ and $a_n=2$:

Really, I'm just putting this here so that the preview picture isn't a spoiler.

But I didn't have enough RAM to keep track of all of that, so it made sense to think of it as some sort of frequency plot:

Whenever you place something in row $k$, the next thing is placed in column $k$.

Imagining dots appearing on a grid turned out to be a lot easier to do mentally than keeping track of a sequence of numbers, so I stuck with that.

Here's a more interesting example starting with $3,3,1,...$:

I don't know how to make gifs, so imagine the lighter-coloured ones appearing later or something.

Of course, I tried more than two examples, but there were some very clear patterns.

Observation 0: The recurrence is "memoryless" in the following sense: if the sequence works for $N$, then it works for all larger $N$. In other words, in the picture above, we could have made the black things red. Moreover, for the terms in the "initial conditions", we don't actually need to know what order they came in; we just need to know what came last.

So in visualising the sequence, we can think about it as a giant block of red stuff, followed by a final red dot, and then the rest of the sequence.

You might think this is common sense, and I guess it sort of is, but it does help with intuition.

Observation 1: Everything is stuck in an L-shape.

Nothing outside of the blue dashed lines!

This turned out to be very easy to prove using extremal principle: Pick a giant L-shape such that the initial configuration is contained within the bottom left square:

Giant blue L bounds initial conditions.

Consider the first time something appears in the forbidden region:

The purple dot is the first thing in the forbidden region.

But for this to happen, its column index must have appeared $>k$ times before this, which contradicts the purple dot being the first occurrence in the forbidden region.

It turned out that getting to this point was already worth 1/7.

Observation 2: The dots eventually bounce between the bottom part of the L and the top part of the L.

Indeed, once you've drawn every dot in the bottom left square that eventually ends up being drawn (there are finitely many such dots), everything in the first $k$ columns is followed by something in the bottom of the L and vice versa.

It turned out that this tiny extra step bumped the 1/7 to a 2/7.

At this point, it becomes pretty evident why we care about $a_1,a_3,a_5,\ldots$ and $a_2,a_4,a_6,\ldots$: one of these will end up representing the stuff in the left side of the L, and we want to show these go through the columns periodically.

At this point, I had some pretty clear ideas of what to try next, but I was content with how much I'd got in a small amount of time, so I went to sleep.

More observations

Most of Sunday and Monday was spent in discussions about the marking scheme of the question that I was grading (Problem 1), and the rest of my free time went to attempting the FE. (That was hard. I spent something like 4-5 hours on it and only got like 2-3 marks' worth of partials. Truly tragic.) So it wasn't until Tuesday morning, the morning of Day 1, that I got back to thinking about this problem again. I was sitting on the bus from the Leaders' site in Bristol to the main IMO site in Bath, and my friend beside me was busy ploughing away at the FE, so I decided to think about Problem 3 (the only problem I thought I could reasonably attempt without paper) again to feel productive.

I remember thinking about whether everything inside the L had to be filled up eventually. It's not hard to find a counterexample:

Big initial configuration results in tiny limit. The tall red column can be as tall as you like. Blue dashed lines are outside of the picture.

But this did lead to a correct observation:

Observation 3: Only finitely many rows and columns go to infinity.

This is, of course, obvious from Observation 1.

In fact, it's not hard to guess which rows and columns these should be:

Observation 4: The rows and columns which go to infinity are precisely the first $m$, for some $m$.

While trying to prove this, I noticed something stronger:

Observation 5: Eventually, the first $k$ rows look like:

Outside of the green blob, the rows have all their dots and their rightmost points are in (not necessarily strictly) decreasing order.

These columns originally started out empty, so if column $c$ has $r$ dots, then $r$ of the first $k$ columns must have reached height $r$. Assuming $r > k+1$ and the initial configuration was originally in the bottom $k\times k$ square, then at least $r$ columns have reached height $r-1$ from an initially lower height, so column $r-1$ has $\ge r$ dots, which must occupy the first however many rows.

This proves Observation 4, since if row $r$ goes to infinity then all the rows below it must also go to infinity. And if exactly rows $1$ to $m$ go to infinity, then the columns which get stuff placed in them infinitely many times are exactly columns $1$ to $m$.

In hindsight, I've drawn the green blob a little too large, but my excuse is that Observation 4 lets us view the problem instead as:

We can shrink our original L to a smaller L. The new green blob is the stuff in the rows/columns that don't go to infinity.

and this is how I've been thinking of this problem ever since I made that observation.

You've probably noticed that I've drawn some question marks in the left side of the L. I very briefly thought that the columns also had to be monotone in some direction, but it turned out to be very easy to construct a counterexample; something like this works:

Columns stay in whatever random order as we go to infinity.

But playing around with some examples and looking closer at our proof of Observation 5 tells us something about the column heights:

Observation 6: The heights of the first $m$ columns eventually correspond to the heights of the first $m$ rows.

The proof of Observation 5 gives this as well if we take "eventually" to mean "after all the stuff in the square containing the green blob has been drawn".

Reducing the diagram

At this point, my mental picture consisted of a nice staircase at the bottom right, a big blurry blob in the bottom left, and some random skyscrapers in the top left. That's kind of big and annoying. Fortunately, Observation 6 lets us reduce the diagram: there's a bijection between the first $m$ rows and columns given by matching heights/lengths, so we can label the rows with the columns they correspond to. However, we could have ties, which is kind of annoying, so the best we can really do is to label each vertical edge with the set of indices it corresponds to:

Columns $\{a_{11},\ldots,a_{1n_1}\}$ have the lowest height. Columns $\{a_{21},\ldots,a_{2n_2}\}$ have the next lowest height. And so on.

Now, the bottom row has to go to infinity, so let's imagine what happens when it gets extended by $1$. This happens when one of the tallest columns grows by $1$, say column $c$. So the right-hand side of our picture looks like:

The last set has size $1$ and contains only $c$.

What happens next? The next dot lands in column $1$, so the move after that lengthens the bottommost row corresponding to $1$. In other words, in our reduced diagram, we're looking for the set which contains $1$, and pushing the lowest row it corresponds to to the right by a space:

The $1$ moves one step to the right.

Of course, this is overly simplistic: this could very well end up merging with the next vertical face, in which case $1$ is added to that set.

Now, what happens next? Well, suppose we've lengthened row $r$, then we're looking for the set that contains $r$ and then repeating the process as above.

And then we do this again and again, except that the sets might keep moving and splitting and merging and it becomes hard to keep track of in your brain and aaaaaaaahhhhhhhhhhh.

Let's look at the annoying case in which we lengthen a row and it matches the length of the next row. So some index $a$ moves from one set to the next.

Lengthened row corresponds to column $a$.

Problems arise if we have to look for the index $a$ again, because then $a$ "overtakes" some stuff in its new set. But can this happen? Let's think about when we look for the index $a$. Actually, let's go back to right before the bottom row is lengthened and look at which vertical faces could lead to which columns:

The lowest vertical face can only give indices $1$ to $a_1$ for some $a_1$. The next can only give indices $a_1+1$ to $a_2$. And so on.

Suppose we have not yet looked for the same index twice. Then each index has a unique vertical face that could lead to it, and conversely, this vertical face can only produce that index once. (More concretely, suppose we have some column index $i$ and $a_j +1 \le i \le a_{j+1}$. Then we look for index $i$ on the $(i - a_j)^\text{th}$ time an index lands in the $j^\text{th}$ set.) So roughly speaking, for something to go wrong, something must have already gone wrong...hence we should be using the extremal principle.

Consider the first time an index $i\ne c$ is chosen again. Right before this, the picture, as compared to right before the bottom row was lengthened, looks like this:

All rows have been lengthened by at most $1$, by the argument in the previous paragraph.

We can't have chosen $i$ again, otherwise row $i$ would have advanced twice (which would require something in the $j^\text{th}$ set to have been chosen twice), contradiction.

Hence, we have:

Observation 7: Until $c$ is chosen again and the bottom row lengthens by $1$ yet again, each other index has been chosen at most once.

This partially resolves our tracking issue with sets splitting and merging all the time: instead of merging an element into the next set whenever we move it, we may instead keep them separate and only merge them whenever the bottom row is lengthened:

The stuff in orange only start mattering again once the bottom row gets lengthened.

At this point, I was convinced that I was almost done.

Finishing up

Suppose that when the bottom row is lengthened, all the rows have been lengthened by $1$. Then we're done: the next $2m$ moves will proceed in exactly the same way, etc., ad infinitum.

So we only need to consider the case when not all indices move.

Suppose none of the orange sets merge with the remaining blue sets, then the next cycle will end up moving the exact same indices in the exact same order, and the orange sets move a further spot to the right. If a merge never happens, then our picture must look like this:

Blue stuff is to the left of the orange stuff.

But then (by induction) only the orange stuff will ever move, which contradicts the blue rows going to infinity.

So, eventually a merge happens. Now what? The indices we look for will remain exactly the same, until the first time we're looking for an index $j$ which has been merged to the next set.

Instead of lengthening the same row as last cycle, we instead lengthen one of the rows corresponding to the set we merged into.

At this point, the next index we seek is strictly less than the index we sought last cycle. This screams "monovariant". Indeed, if we write down the indices we've been looking for (so in the notation above, $1, r, \ldots, c$), then the indices for this cycle are lexicographically smaller than the ones from the previous cycle (the sequence $a_1, \ldots, a_s$ is lexicographically smaller than $b_1, \ldots, b_t$ if for some $n \le s, t$, $a_i=b_i$ for all $i < n$ and $a_n < b_n$. It's an alphabetical order, but for numbers). But since each index appears at most once, there are only finitely many such sequences, and these are totally ordered by the lexicographical ordering. Hence, eventually no more merges can occur and we're back to one of the cases we've already considered, so we're done!

At this point, I was still halfway through an hour-long bus journey to Bath. I spent the rest of it feeling very smug.

Commentary

Alternate solutions

There are a couple of points at which one can diverge from whatever I did and still arrive at a solution. I'll talk about them briefly.

Instead of looking at the bottom $m$ rows, one could look at the first $m$ columns. The columns' indices along with the order of their heights encodes the same information that I was looking at with the rows labelled by column indices.
Instead of looking for a monovariant, one could instead realise that the proof of Observation 7 didn't actually use anything about the first row being the first row; it in fact shows that eventually, between any two occurrences of a column index $i$, at most one $j$ (for each $j\ne i$) can appear. Periodicity can be deduced directly from this very strong fact.

Apparently, most of the coordinators who were test-solving this problem did bullet point #1 instead, but not bullet point #2.

Beauty

This is exactly the sort of combi problem I love; you stare at the process until you understand what's going on, and then the solution arises naturally. At the time of solving, my only complaint about this was that it was too easy to be a Problem 3, but...

Difficulty

Having a structural combi as Problem 3 reminded me of IMO 2019 (the previous Bath IMO), and I couldn't help but compare the two years: both had easy algebra, a technical but somewhat routine medium problem, and a structural combi. At that point, I hadn't really tried the number theory yet but I was assuming it was comparable to 2019/2, so with the other problems on 2024 Day 1 being (in my opinion) easier than their 2019 counterparts, I was predicting 40 full solves on 2024/3. Boy was I wrong:

Left: Stats from 2019 Day 1. Right: Stats from 2024 Day 1. The 6s on 2019/2 are morally 7s; for some stupid reason 2019 was the unique year in which a mark was docked if you didn't consider some parallel line edge case separately. Well, 2002/2 also has a similar proportion of 6s and allegedly had the same problem captain, so maybe "unique" is wrong...

I'm still not entirely sure how this happened. My best theory is that combi problems such as this truly get a lot easier if you have the right picture in your head. But then again, the graphical representation isn't hard to come up with (and in the David & co. livesolve, they did come up with this approach - see point 5 - but didn't progress any further). There isn't much machinery involved - even the final monovariant is unnecessary. Maybe having done some basic analysis has made me more comfortable with the ideas of eventual behaviour and stuff? No idea.

Another thing to note is that the 2 mark partial isn't really that hard to get - I wonder if more people would have got the marks if they had been actively partial-farming. I expected this to bump the gold cutoff to 30 (indeed, the number of people who scored $\ge 2$ is more than the number of golds), but I suppose the general chaos caused by Turbo along with people dropping marks here and there was enough to push it down to 29.

Search This Blog

SIMO Retiree Blog