Skip to main content

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.


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.


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


  1. Supercool blog and although for IMOSL 2011 problem there is another super cool solution too, although u have more experience so u know more, orzmax 🛐


Post a Comment

Popular posts from this blog

EGMO solutions, motivations and reviews ft. Atul, Pranjal and Abhay

The  European Girls' Mathematical Olympiad a.k.a EGMO 2022 just ended. Congrats to Jessica Wan from USA, Taisiia Korotchenko, and Galiia Sharafetdinova for the perfect scores! Moreover, the Indian girls brought home 4 bronze medals! By far, this is the best result the EGMO India Team has ever achieved! To celebrate the brilliant result, here's a compilation of EGMO 2022 solutions and motivations written by my and everyone's favorite IMOTCer Atul ! And along with that, we also have reviews of each problem written by everyone's favorite senior, Pranjal !  These solutions were actually found by Atul, Pranjal,  and Abhay  during the 3-hour live solve. In the live solve, they solved all the 6 problems in 3 hours 😍!!! Okie Dokie, I think we should get started with the problems! Enjoy! Problem 1:  Let $ABC$ be an acute-angled triangle in which $BC<AB$ and $BC<CA$. Let point $P$ lie on segment $AB$ and point $Q$ lie on segment $AC$ such that $P \neq B$, $Q \neq C$ and

Kőnig-Egerváry theorem

Graph theory has been my most favourite thing to learn in maths and and in this blog i hope to spread the knowledge about Kőnig's theorem. It is advised that the readers are aware about basic graph theory terminologies including bipartite graphs. Before going on to the theorem i would like to go on about matchings and vertex cover which we are going to use in the theorem  Matchings A matching $M$ of a graph $G$ is a subset of the edges of a graph in which no two edge share a common vertex (non adjacent edges). For example :- The Matching $M$ over here is edge $\{ 3 - 5 , 1-2 , \}$ or $\{ 1 - 2 , 4 - 3 \}$ etc .  Maximum Matching is a matching that contains the largest possible number of edges for instance in the above example the maximum matching is 2 edges as there cannot be a subset of non adjacent edges having greater than 2 edges (Readers are advised to try so they can convince themselves) A Perfect Matching  is a matching that matches all vertices of the graph or in other sen

Algorithms, or Mathematics?!

Hi everyone! In my last blog, I spoke about a couple of very interesting algorithmic techniques and how they can be used to solve a variety of very interesting problems. This blog however, is going to be completely different.   When we’re young we begin by learning the steps to add – we’re given the rules and we must learn to repeat them – no questions asked. Why does carry forward work the way it does? Well, no questions asked. To some extent, it is important to know how exactly to do a certain set of things while first learning maths. We may not be able to get anywhere in a subject if we’re unable to learn a few basic rules and know how to use them. However, after a certain point it is important to bring in the spirit of mathematical thinking within each student too – something missing in almost every form of school math education. Mathematical miseducation is so common, we wouldn’t even see it. We practically expect a math class to look like repetition and memorisation of disjointed