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

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

• Post 1

• Post 2

• Post 3

• Post 4

• Post 5

• Post 6

• Post 7

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 :)