Challenge the rules!

Hi all! I'm Kelin, a rising 11th grade student from the US. I've been studying Olympiad math for more than 2 years now, and although I'm mostly retired, I still find Olympiad problems beautiful and I'm always down to share my favorite concepts with other math enthusiasts. In my spare time, I'm getting acquainted with competitive programming and higher math.

Combinatorics is my favorite math contest subject since it's easy to get started with. It requires no heavy theory, and difficult combinatorics problems usually embody brilliant ideas.

I will began my post with a folklore problem:

On a 1-meter stick, 1000 ants start at different positions, each moving at 1 meter per second and towards the left or the right. Every time two ants collide, they each reverse their orientations. What's the longest that any ant can remain on the stick?

If you've never seen this one before, please try it out for a few moments before proceeding, even if you are a beginner. It's probably closer to a puzzle than a contest problem.

Solution:

Each time two ants collide, an ant ends up going to the left and an ant ends up going to the right.
Before the collision, an ant was going to the left and another was going to the right... do you see any resemblances?

That's right; if the ants moved past each other instead of turning to the opposite direction, we would still get two ants moving in the same direction and in the same positions. So, we can assume that ants always move in the same direction, and since they move at 1 meter per second, they take at most 1 second to fall off.


Another similar type of problem involves imposing additional restrictions on what each object does. This sounds a bit confusing at a glace, but the following example from the IMO 2018 Shortlist explains it well.

Problem: Let $n$ be a given positive integer. Sisyphus performs a sequence of turns on a board consisting of $n + 1$ squares in a row, numbered $0$ to $n$ from left to right. Initially, $n$ stones are put into square $0$, and the other squares are empty. At every turn, Sisyphus chooses any nonempty square, say with $k$ stones, takes one of these stones and moves it to the right by at most $k$ squares (the stone should say within the board). Sisyphus' aim is to move all $n$ stones to square $n$.
Prove that Sisyphus cannot reach the aim in less than
\[ \left \lceil \frac{n}{1} \right \rceil + \left \lceil \frac{n}{2} \right \rceil + \left \lceil \frac{n}{3} \right \rceil + \dots + \left \lceil \frac{n}{n} \right \rceil \]turns.

The peculiar format of the lower bound suggests some approach based on indexing the stones between $1$ and $n$. After that, we can attempt to match the $\left \lceil \frac{n}{i} \right \rceil$ term with the index $i$, and try to come up with something that establishes the bound for each index. The solution should then arise.

Solution:

Label the stones with integers between $1$ and $n$. Then, suppose that each time we move a stone, we move the stone with the greatest label at its location.

Now, we can see that a stone with label $i$ can move at most $i$ squares at once. This gives the desired bound.

Here is one last example from the IMO 2011 shortlist, which is significantly harder than the previous two. In a sense, it's an extension of the ideas we established so far.

Problem: Let $m$ be a positive integer, and consider a $m\times m$ checkerboard consisting of unit squares. At the centre of some of these unit squares there is an ant. At time $0$, each ant starts moving with speed $1$ parallel to some edge of the checkerboard. When two ants moving in the opposite directions meet, they both turn $90^{\circ}$ clockwise and continue moving with speed $1$. When more than $2$ ants meet, or when two ants moving in perpendicular directions meet, the ants continue moving in the same direction as before they met. When an ant reaches one of the edges of the checkerboard, it falls off and will not re-appear.

Considering all possible starting positions, determine the latest possible moment at which the last ant falls off the checkerboard, or prove that such a moment does not necessarily exist.

Just like example 1, I suggest everyone to attempt this problem for a bit. However, do keep in mind that you are far less likely to solve it and probably will spend a lot of time even if you do.

Using a similar thought process to example 1, it's easy to eliminate the condition of a clockwise rotation by just supposing that each ant either only moves up and right, or only moves left and down. This also eliminates the possibility that some ants stay on the board forever, and gives a reasonable upper bound of $2n-1$. So we are done and only need to find a construction... or are we?

While doing the actual problem, I arrived at this point with a lot of suspicion that the answer should be lower. This is, in part, since the problem is poised as a candidate for an IMO problem 3/6, which should not succumb to such a simple idea. I found the lower bound $\frac{3n}{2}-1$ pretty simply by just having ants in the top-left and bottom-left corners that face each other, but could not construct anything better. Hence, I started to believe that the actual answer was just $\frac{3n}{2}-1$.

Spoiler: I was correct. I ended up finding a neat solution involving invariants, but the intended approach is far more brilliant, and I will present both of them.

Solution 1 (due to me): 

The answer is $\frac{3m}{2}-1$; the construction is as stated above.

The "clockwise" condition is irrelevant, so instead say that any ant starting with the directions +x or +y can only move in these two directions and vice versa. At the start, suppose that every ant moving towards the line $x=y$ receives a coin labeled with its distance from $x=y$ (an ant on the line counts as moving away from it). Note that the greatest possible label is $m-1$. Whenever an ant with a coin intersects an ant without a coin, the coin changes hands, and whenever an ant crosses $x=y$, any coin that it has disappears (while possibly intersecting another ant). It's easy to see that an ant holds a coin iff it's currently approaching $x=y$.

Notice that all coins always move at speed 1 towards $x=y$, so a coin disappears at the same time as its label. This means that after $m-1$ seconds, no coins are left and hence every ant is moving away from $x=y$. At that moment, consider an ant $a$, and assume WLOG it's currently moving towards +x. Its sum of coordinates is at least $m$, and since it's moving away from $x=y$, its x coordinate must be at least $\frac{m}{2}$. Therefore, it can move for at most $\frac{m}{2}$ seconds as desired.

Solution 2 (similar to official):

We will change the rules twice instead of just once.

Call an ant moving right or down positive, and call other ants negative. Note that a positive ant has sum of coordinates increasing and a negative ant has sum of coordinates decreasing. Consider an alternate set of rules in which instead of the two ants turning $90^\circ$ clockwise when they meet, the positive ant stays positive and the negative ant stays negative. So a positive ant has his sum of coordinates increase by one for every unit of time. All positive ants start with sum of coordinates at least one, so after time $t$ they all have sum of coordinates at least $t+1$. Similarly, all negative ants start with sum of coordinates at most $2m-1$, so at time $t$ they all have sum of coordinates at most $2m-1-t$. But the ants do not behave any differently between this new set of rules and the original, so this is also true for the original problem's rules.

We can similarly define an ant to be $x$-leaning if he is moving right or up, and $y$-leaning otherwise. By considering an alternate set of rules in which $x$-leaning ants stay $x$-leaning and vice versa, we have that $x$-leaning ants always have their $x$-coordinate minus their $y$-coordinate increasing by one each time unit, and similarly for $y$-leaning ants. After time $t$, all $x$-leaning ants on $(a,b)$ are such that $a - b \geq t - m - 1$. Similarly, all $y$-leaning ants on $(a,b)$ are such that $b - a \geq t - m - 1$. This is true for the original problem's rules as well.

Now consider the situation after time $\frac{3m}{2}-1$. We claim all the ants have fallen off. Suppose an ant $(a,b)$ is still on. If $\frac m2 \leq a+b \leq \frac{3m}{2}$, then the ant can neither be positive nor negative, which means he can't be moving at all, contradiction. If this inequality is not true, then either $a,b$ are both at most $\frac{m}{2}$ or $a,b$ are both at least $\frac{m}{2}$. Either way, $|a-b| \leq \frac{m}{2}$. But this implies that at this point in time the ant can be neither $x$-leaning or $y$-leaning, so he can't be moving at all either. As a result, there is nowhere on the board that can still have an ant, so $\frac{3m}{2} - 1$ is the last possible time that an ant can remain on the board.

Solutions that involve changing or adding rules are usually short and nice, but a difficulty arises in seeing when to apply this concept. Here are a few more practice problems that exercise it:


Problem (IMO 2000):  Let $ n \geq 2$ be a positive integer and $ \lambda$ a positive real number. Initially there are $ n$ fleas on a horizontal line, not all at the same point. We define a move as choosing two fleas at some points $ A$ and $ B$, with $ A$ to the left of $ B$, and letting the flea from $ A$ jump over the flea from $ B$ to the point $ C$ so that $ \frac {BC}{AB} = \lambda$.

Determine all values of $ \lambda$ such that, for any point $ M$ on the line and for any initial position of the $ n$ fleas, there exists a sequence of moves that will take them all to the position right of $ M$.


Problem (MathCamp 2022): Marvin is playing a solitaire game with marbles. There are $n$ bowls (for some positive integer $n$), and initially each bowl contains one marble. Each turn, Marvin may either

    1. remove a marble from a bowl, or
    2. choose a bowl A with at least one marble and a different bowl B with at least as many marbles as bowl A, and move one marble from bowl A to bowl B.

The game ends when there are no marbles left, but Marvin wants to make it last as long as possible. Prove that the game must end after at most $n(n+1)/2$ turns.


Thank you for reading! - Kelin