Waste less time on Facebook — follow Brilliant.

Elementary Techniques used in the IMO (International Mathematical Olympiad) - Invariants

For the sake of my reader, here are all the previous posts:

So this is the \( 8\)th and last post with the practice questions specially selected from the big pool of IMO problems for my reader. As such, it is advisable for the reader not to google for the solutions (which are readily available online) for reason of integrity and the fact that this is just a tiny test to see how well you have mastered the skills of finding an invariance. So do \( \large \text{post your solutions in the comments} \)!

But firstly, the solution to the problem left to the reader in the previous post:

Consider a graph with \( mn \) vertices representing the markers. (This is motivated by considering adjacency graphs and the like) Intuitively, connect two vertices with an edge iff the markers are adjacent on the board. And as was mentioned in the post, label \( -1 \) to each edge in the graph and also to each of the vertices which represent white markers. Now, we will also assign \( 1 \) to each of the vertices which represent black markers. I leave it to the reader to verify that the product of all the weights assigned (both vertices and edges included) is constant which we will denote as \( \mathfrak{C} \). Hint: Consider cases if the vertex representing the about-to-be-removed black marker is isolated and otherwise (if otherwise we can see why the edges also play an important role - they flip the signs).

Let us see what happens when we remove a marker. We remove the vertex representing it and also all the edges emanating from this vertex. Consider at the beginning of the procedure, it can be seen that there are \( (mn-1) + [m(n-1) + n(m-1)] \) -1s on edges and vertices. The sum \( 3mn-m-n-1\) is odd, so \( \mathfrak{C} \) is \( -1 \). Let us see why this leads to a contradiction. We would like a step which \( \mathfrak{C} = 1 \), hmm, intuitively it would be generated if there were only 1 black marker left. But obviously we would need to reach such a state when we are removing the last marker. Therefore, we reach our desired contradiction. □

\( \LARGE \text{Problem set} \)

  1. Five identical empty buckets of \( 2 \)-liter capacity stand at the vertices of a regular pentagon. Next to the pentagon (this is in math world), there is a huge river of melted cheese. Jerry followed the smell of the cheese and entered math world. However, he forgot that Tom was following him secretly. Jerry and Tom then play the following game with Jerry trying to get as much cheese as possible: At the beginning of every round, Jerry takes one liter of cheese from the cheese river and distributes it randomly over the five buckets. Then Tom chooses a pair of neighbouring buckets, empties them to the river and puts them back. Then the next round begins. Obviously, Jerry's goal would be to make one of the bucket overflow. Tom's goal is to prevent this. Can Jerry ensure that a bucket would overflow?

  2. Let \( S \) be a finite set of at least two points in the plane. Assume that no three points of \(\mathcal S \) are collinear. A windmill is a process that starts with a line \( \ell \) going through a single point \( P \in \mathcal S \) The line rotates clockwise about the pivot \( P \) until the first time that the line meets some other point belonging to \( \mathcal S \). This point, \( Q \), takes over as the new pivot, and the line now rotates clockwise about \( Q \), until it next meets a point of \( \mathcal S \). This process continues indefinitely. Show that we can choose a point \( P \) in \( \mathcal S \) and a line \( \ell \) going through \( P \) such that the resulting windmill uses each point of \( \mathcal S \) as a pivot infinitely many times.

  3. We write six nonnegative integers at the vertices of a regular hexagon with a sum of \( 2013^{2013} \). Anqi is allowed to make moves of the following form: she will pick a certain vertex and replace that number with the absolute value of the difference between the numbers written at the two adjacent vertices. Prove that Anqi can make some moves, after which all the six vertices are \( 0 \).

I still think that it is important for my readers to understand the motivation behind solving such problems, so I have included a Hints section. Please only click on the link if you have tried really hard and is desperate to stay on the right track. Also, do follow the rules as stated on the Hints page. Thank you.

A \( \Large \text{big thank you} \) to all my readers for following me through the huge and fantastic world of combinatorics (in particular, the invariance principle) and I hope you have learnt something :)

Note by Anqi Li
2 years, 10 months ago

No vote yet
1 vote


Sort by:

Top Newest

Thanks for combining the posts at the start, as it makes them easier to find :)

The hints post is a great idea, since these problems do get into the hard range. Calvin Lin Staff · 2 years, 10 months ago

Log in to reply

  1. Not really invariance, but I think this works. I spent a while proving things like that Tom can ensure the total amount of cheese is less than \(1.5\) after he empties two buckets. When I tried to finish the proof, I found that I didn't actually need that lemma, and did the following:

We claim that Jerry cannot cause a bucket to overflow.

Let \(b_0\), \(b_1\), \(b_2\), \(b_3\), and \(b_4\) denote the buckets and the amount of cheese in each of the five buckets, depending on context, such that going around the pentagon, the buckets are in numerical order. Let a pair be two buckets \(b_i\) and \(b_{i+2}\) such that \(b_i+b_{i+2}>1\), where indices are taken modulo 5. A pair is said to be broken if Tom empties one or more of the buckets in a pair.

Lemma: For Jerry to cause a bucket to overflow, there must have been an unbroken pair two rounds earlier, before Jerry adds a liter.

Proof: WLOG, \(b_0\) overflows. It must have \(b_0>1\) before Jerry adds a liter, and he can add the entire liter to this bucket. However, Tom knows this and he would empty this bucket. Then, another nonadjacent bucket, WLOG this is \(b_2\), must have more than one liter of cheese. Two rounds previous, it must have been true that \(b_0+b_2>1\) before Jerry added a liter. \(\square\)

Tom knows this, and he would break the unbroken pair the round before. If there are multiple pairs, he might not be able to break all of them, and Jerry can cause one bucket to overflow.

Now, consider all the possible arrangements such that there are multiple pairs. If there are three buckets involved in the pairs, two must be adjacent, and Tom can break all pairs. If there are four buckets involved in the pairs, all four must be adjacent, and Tom can empty two other than the center two to break all pairs. Then, the only possible arrangement such that Jerry can keep an unbroken pair and cause a bucket to overflow is when all buckets are part of a pair after Jerry adds a liter, and every possible pair is a pair.

The previous round, before Jerry adds a liter, two buckets must be empty, and there must be no pair among the other three. WLOG, \(b_3=b_4=0\). Then, Jerry must add cheese such that \(b_3+b_0>1\) and \(b_2+b_4>1\). Adding, \(b_0+b_2+b_3+b_4>2\). However, since there was no pair, \(b_0+b_2\le 1\), and so \(b_3+b_4>1\), a contradiction, since Jerry only can add one liter. Hence, we conclude that Jerry cannot cause a bucket to overflow. \(\blacksquare\) Daniel Chiu · 2 years, 9 months ago

Log in to reply

@Daniel Chiu I have a three-four liner solution. It's basically almost the same idea as yours, but much streamlined. See whether you can find it. :) Anqi Li · 2 years, 9 months ago

Log in to reply

@Anqi Li Nope, have nothing! Daniel Chiu · 2 years, 9 months ago

Log in to reply

Some work on #3:

Replacing the maximum number (choosing optimally) will always decrease the sum of all 6 numbers UNLESS there are 2 0's opposite each other and the other four numbers are the same. Now I just need to show that that position can be prevented from occurring. Daniel Chiu · 2 years, 9 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...