This is a problem from the $2005$ All-Russian Olympiad. Problem is as follows:
$100$ people from $25$ countries, four from each country, sit in a circle. Prove that one may partition them onto $4$ groups in such way that no two countrymen, nor two neighboring people in the circle, are in the same group.
My approach was to try and find an algorithm that can monotonically reduce the number of bad states. However, I haven't been able to figure out a way to do this for every possibility. Does anyone have any hints on how to approach this problem?
I've tried to start with an arbitrary partition where each partition only has 1 person from each country, and preserve that with each move.
I also claim that there is always a country for which not all of its representatives' neighbors are in a single partition. Proof idea: Suppose not. WLOG, say that country $1$ has all of its representatives' neighbors in the first partition. So if $1_i$ is the representative from country $1$ in partition $i$, we have $1_1$ and its neighbor, WLOG from country $2$, is also in group $1$. So we have $1_1, 2_1$. Then $2_1$'s other neighbor must also be in partition $1$ or we are done. Continuing in this way, we find that all the representatives are in partition $1$, contradiction.
Using this, I try to decrease the number of "bad" pairs (i.e. neighbors or same country) in each partition monotonically. However, I haven't been able to figure out how to do so.
In particular I'm stuck on cases like the following: country $1$ has its representatives in partitions $1-4$ s/t the neighbors of $1_2,1_3,1_4$ are all in the first partition. $1_1$'s neighbors are in partition $1$ and another partition, say $2$. Trying to swap the placements of country $1$ representatives seems to only increase number of "bad" pairs, and trying to swap the neighbors may also increase the number of bad pairs.
Is there an observation that I'm missing here, or is this approach not the right way to go about it?