More combi visualisation: ISL 2018 C6

It's Glen again.

Last week, I mentioned how the relative difficulty levels of the ISL 2018 C4, C5 and C7 felt off to me. Out of curiosity, I looked up the C6 to see where it'd fit, and subsequently ended up solving it in the shower. (Yes, recurring theme, I know.) Anyway, this post will be about my thought process in solving this problem (sans paper, because shower).

(ISL 2018 C6) Let $a$ and $b$ be distinct positive integers. The following infinite process takes place on an initially empty board.

1. If there is at least a pair of equal numbers on the board, we choose such a pair and increase one of its components by $a$ and the other by $b$.
2. If no such pair exists, we write two times the number $0$.

Prove that, no matter how we make the choices in (i), operation (ii) will be performed only finitely many times.

Preliminary thoughts

• Here's a way of visualising this problem: we can think of representing our numbers as chips on a number line. Then, operation (i) corresponds to picking up two chips which have the same location, and then moving one $a$ to the right and the other $b$ to the right. Operation (ii) corresponds to putting two new chips at $0$.

• When phrased this way, this looks a lot like a chip-firing problem. In particular, it reminds me of the One Famous Chip-Firing Problem:

(Folklore) We have $n$ chips on a number line. If two chips are at the same location, we can pick them up, move one $1$ to the left and the other $1$ to the right. Prove that eventually every location has at most one chip (and so the process terminates) and that the final configuration is independent of the moves made.

• If you haven't seen this problem before, I'd encourage you to try it! Here's a hint: the first half (showing that it terminates) involves finding an invariant and a monovariant, while the second half...relies on something that is also applicable here!

Observation 0. The order in which moves are made doesn't matter! In particular:

• the change in the number of chips on each space depends only on the (multi)set of the moves performed (e.g. doing move (i) on $2$ twice, then $6$ is the same as doing move (i) on $6$, then $2$ twice), and
• if a move of type (i) is legal at some point, then it always remains legal until it gets performed.

• This lets us reorder moves however we want. In particular, nothing (except for the annoying condition in the problem) is stopping us from just doing all the operation (ii)s first. Let's try to get around that. 

• Suppose otherwise for sake of contradiction, then we must perform (ii) infinitely many times. In other words, if we limit ourselves to a finite number of (ii)s, the process eventually terminates and we get stuck. But by our observation, this would have given the same result as applying all the (ii)s first, and then applying a bunch of (i)s.

• Thus, what we want to show is:

Reformulation. Start with $2n$ chips on $0$. Prove that for some $n$, operation (i) can be performed infinitely many times.

• This immediately makes things a lot easier to visualise: instead of having to go through cycles of spamming (i) and getting stuck and introducing more chips via (ii), we can just start with a pile at $0$ and repeatedly apply (i). Moreover, since the order of moves doesn't matter, we can just greedily apply (i) however we want.

• It remains now to just find some $n$ (probably in terms of $a,b$) that gives some configuration that "moves off to infinity". 

• Moreover, this reformulation gives us even more leeway with the use of operation (ii):

Observation 1. We can WLOG perform extra operation (ii)s at the start.

• Indeed, to find a contradiction, we just need to show that for some $n$ the starting configuration with $2n$ chips goes off to infinity. While in the original formulation, the restriction that operation (ii) can only be performed if we get stuck means that we're forced to use operation (ii) the minimal number of times, in our new formulation we just want to show that the process can't terminate for all $n$, so nothing is stopping us from finding an $n$ that isn't minimal.

Some examples for intuition

• Having made these observations, this is now a matter of construction: can we find a configuration that goes off to infinity? This reminds me a little of the spaceships in Conway's Game of Life, but I don't remember much about that. Also, I am in the shower so it's not like I could look it up even if I wanted to.

• Let's try to work with general $a$ and $b$. Then, instead of having a number line, we'd instead have an infinite grid, with each move corresponding to moving one piece up and one piece right:

• Wait, except this process always terminates regardless of the number of things we put at the origin in the beginning. The fast way to see this is that it reduces to the folklore chip-firing problem upon projection onto the line $y=-x$. But also, one could try to cook up some sort of monovariant argument. When I first pictured this in my head, the argument I had in mind was to show that if a chip was in column $k$, then there was also a chip in column $k-1$, and so chips can't move past column $2n$ (and similarly, past row $2n$).

• So whatever we do has to use the fact that $a,b$ are integers somehow - if we had e.g. $a=1,b=i$, then the question would be wrong.

• Let's try the simplest nontrivial case: $a=1,b=2$. The picture looks like this (some steps skipped for the sake of my sanity):

• We see that the trio of chips ends up moving off to infinity. The last one is left behind, but that doesn't really matter. Sorry, Republican education policy.

• With this in mind, there are two things that we want to do: (1) find some configuration that moves off to infinity, and (2) prove that there's some $n$ that can achieve it.

Finding legal configurations

• The second seems a little easier, because we can use abstract properties of chip firing to figure out what configurations we can achieve. In particular, we can superpose two configurations, by just taking the chips in each location and combining them into one big pile. Then notice that:

Observation 2. If configuration $A$ can be obtained from $n$ chips at $0$ and configuration $B$ can be obtained from $m$ chips at $0$, then their superposition can be obtained from $n+m$ chips at $0$.

In other words, the superposition of two legal configurations is legal.

• So for a configuration to be legal, all we need is each location involved to be legal. But we know exactly what that should be: it's just an application of the Chicken McNugget Theorem. In particular, WLOG $\gcd(a,b)=1$. Then,

Observation 3. All sufficiently large integers are legal.

• This comes from visualising the 2D case from before, where we didn't care about the values of $a$ and $b$. We could reach the entire diagonal $x+y=1$ from two chips at the origin. Then, doubling everything, four chips at the origin gives us two copies of the diagonal $x+y=1$, which then gives us the diagonal $x+y=2$ (plus some extras). We can repeat inductively, so every $an+bm$ can be reached. Then, we can just apply the Chicken McNugget Theorem.

• But since a configuration that moves to infinity should only depend on the relative locations of the pieces, we should have leeway to create whatever configuration we want, since as long as we put it sufficiently far to the right, it will be legal. That's extremely loose!

Guessing the spaceship

• It remains to guess a configuration that can move off to infinity.

• Earlier, we left a chip behind, but we can't keep doing that; since we only have finitely many chips eventually we have to stop leaving chips behind. So, maybe we should try to find configurations that never leave chips behind.

• Then, since order doesn't matter, such a configuration should move off to infinity by repeatedly applying operation (i) on the leftmost chips.

• What should this look like?

• My initial guess is to try a rectangle:

• Each column would have to have an even number of chips, so nothing gets left behind. But after one move, things get bad, unless the number of chips was a multiple of $4$? But after that, it gets messy and I'm not entirely sure what happens.

• We could try a rectangle, but with holes at $a,b$? But after we clear the first column we get a rectangle again, which is similarly bad.

• Maybe, we could try a case that is more complicated than $a=1,b=2$ and see what happens. Let's try, like, $a=2,b=5$. The first step looks like this:

• The next column probably started with two things as well, so we should have:

• The next one probbably started with one chip? And the one after that as well.

• It seems like a starting configuration that would have worked is:

• Indeed, applying (i) to the leftmost column moves the chips to the ends of their respective rows.

• This generalises! For general $a,b$, we can instead have one row of length $a$ and one of length $b$, and this goes off to infinity for the same reasons.

• Finally, placing this configuration sufficiently far to the right, this is a legal combination, and so we're done.

Remarks

I personally found this a little easier than C7, but that's probably because I've done enough chip-firing problems to have seen all the tricks. (In particular, the ideas about reordering operations and superposing configurations.) C7 required me to actually draw things out. On the other hand, having to come up with a construction here is a step that one actually has to make up by oneself, while in contrast C7 it's a matter of repeatedly strengthening some observations about the problem. So there would be an argument for either to be the more difficult one.

In any case, I think they're both certainly easier than C5, which has a pretty finnicky construction and a a tricky counting argument - the final answer to that is some weird-looking formula, which should already tell you that something funny has happened. (And indeed, when I tried C5 when it came out in NTST, it took me a couple of hours, which is longer than C6 and C7 took combined.) And of course, C4 was an IMO problem with (checks notes) only 11 full solves. So I'm still crying foul play about the shortlist order.

About the construction: this generalises to moving $k$ chips by $a_1,\ldots,a_k$, which is pretty cool. Moreover, this can be done so in such a way that keeps each chip in the same "row", i.e. each chip ever only jumps by one possible distance! In a way, this is like a superposition of $k$ distinct processes, each with one chip moving repeatedly to the right by $a_i$. See also the chip-firing problem in this old post by David.