XXXI Brazilian Math Olympiad

For each configuration that can be obtained, let $S$ be the sum of the squares of the coordinates of the pebbles. Each operation takes four pebbles at $(x,y)$ to one pebble at each of the points $(x-1,y)$, $(x+1,y)$, $(x,y-1)$, $(x,y+1)$, so each operation increases $S$ by $$(x-1{)}^2+y^2+(x+1{)}^2+y^2+x^2+(y-1{)}^2+x^2+(y+1{)}^2-4(x^2+y^2)=4.$$ It is easy to see that the baricenter $G$ of the pebbles doesn't change.

Let $G$ be the graph whose vertices are the pebbles and we connect two vertices if the distance between the corresponding pebbles is less than $M$, $M>2$ sufficiently large to make the graph connected. One can easily check that the graph remains connected after performing the operation: in fact, if the distance between two pebbles $a,b$ surpasses $M$, then one of the pebbles, say $a$, was moved; then one of the other three pebbles moved gets closer to $b$, and is at a distance at most $2$ from $a$, so there is still a path leading $a$ to $b$. This, added to the fact that $G$ is invariant, proves that the pebbles cannot go too far from $G$; indeed, all pebbles are contained in a disk with center $G$ and radius $2009M$.

Since $S$ always increases by $4$, the number of operations cannot be arbitrarily large, because if it isn't the case, $S$ would go to infinity, and one of the pebbles' coordinates would go to infinity as well, which is not possible. Hence the number of operations is always finite.

Now let's prove that the final configuration doesn't depend on the order of the operations. Suppose that it does and consider, of all possible configurations that can be obtained, one with $S$ maximum that can lead to more than one final configuration. This means that all configurations with higher values of $S$ can only lead to one final configuration. Then one can perform the operation at two distinct points $A$ and $B$, leading to configurations $A$ and $B$, respectively, that lead to different final configurations. Note that $A$ and $B$ have higher values of $S$, so each one leads to its only one final configuration, no matter what is the order of the following operations. But one can perform the operation at $B$ in $A$ and at $A$ in $B$, and these operations lead to the same configuration, which is a contradiction. So the final configuration doesn't depend on the order of the operations.