Partition 100 people, 4 from each country into 4 groups with conditions

Question

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?

Answer 1

Here's a two-step procedure partially borrowed from this question to find a partition. (Actually, maybe it is easier to read the other way around: my explanation here feels better than the one I posted there, so people confused about my answer to that question should read this answer instead.)

Number the people around the circle $1, 2, \dots, 100$.

Step 1: let's say that each country has two men and two women representing it. Obviously it is out of our hands where the men and women will sit.

Step 2: we give everyone a color that is either Red or Blue. We will make sure that from each country, the two men get different colors, and the two women get different colors. We will also make sure that any two people numbered $2k-1$ and $2k$ for some $k$ get different colors.

Graph-theoretically, this step just means two-coloring the union of even cycles, which can always be done. Each person has two constraints: they must be different from one of the people next to them, and they must be different from the person of their country of the same gender. So the graph of constraints is $2$-regular - a union of cycles. The cycles are all even because the constraints alternate between two different types, so each cycle has an even number of edges.

Step 3: we give everyone a shade that is either Light or Dark. We will make sure that from each country, the two Reds get different shades, and the two Blues get different shades. We will also make sure that any two people numbered $2k$ and $2k+1$ for some $k$ (or numbered $100$ and $1$) get different colors.

Graph-theoretically, this problem is identical to Step 2.

Now, the partition into four groups of $25$ is as follows: the Light Red, Dark Red, Light Blue, and Dark Blue groups. By the constraints we enforced in Step 2 and Step 3, each country has one of each color, and any two people sitting next to each other disagree either in color or in shade.

Answer 2

Ah yes, this is such a "russian" problem, if you know what I mean.

---

$\text{Partial Solution}$

Anyway, the solution is based on induction. Suppose that if we place $4n$ people at a table from $n$ countries, $4$ people from each country, we can separate them in $4$ groups such that no $2$ people from the same country are in the same group and no $2$ people sitting next to each other are from the same group.

Now, lets consider $4n+4$ people on our circle. There are $2$ cases:

---

$\text{Case 1:}$

There are $2$ people from the same country that are sitting next to each other. Suppose that country is $c_i$. Take all $4$ people from country $c_i$ and ignore them. For the other $4n$ people on the circle, distribute them in $4$ groups such that the conditions are satisfied (this can be done, from the induction hypothesis).

If we prove that the $4$ people from country $c_i$ can be distributed to the $4$ groups such that the conditions in the statement still hold, then the induction is complete. Here are the $3$ possible cases of the positions of the people from country $c_i$ on the circle (here, the $X_i$s represent people from other countries and $A_i$s people from country $c_i$)

$(X_1-A_1-A_2-X_2)$, $(X_3-A_3-X_4)$, $(X_5-A_4-X_6)$

$(X_1-A_1-A_2-A_3-X_2)$, $(X_3-A_4-X_5)$

$(X_1-A_1-A_2-A_3-A_4-X_2)$

Notice that because we "ignored" the $A_i$s when distributing the $4n$ people to the $4$ groups, in each of the cases above $X_1$ and $X_2$ are in different groups; $X_3$ and $X_4$ are in different groups and $X_5$ and $X_6$ are from different groups.

It is easy to observe that, no matter the groups the $X_i$s are from, in each of the above cases the $A_i$s can be distributed in groups to still satisfy the conditions. Example: (instead of $X_i$s I just put $1$, $2$, $3$ or $4$ for the group they are in)

$(1-A_1-A_2-2)$, $(1-A_3-3)$, $(3-A_4-4)$. Take $A_3=2$, $A_4=1$, $A_1=3$, $A_2=4$ (I will not prove all the above cases, but it doesn't take much and it simply is case-work)

So in this case, the induction holds.

---

$\text{Case 2:}$

There aren't $2$ people from the same country which sit next to each other. In this case we do not need induction, we will just prove that if we have $4n$ people on the circle such that there aren't $2$ people from the same country which sit next to each other we can distribute them to the $4$ groups like it was specified in the statement.

However, I haven't yet found what the algorithm is in this case. I will come back when I find it.

Answer 3

This questions seems to be very similar to graph theory problems and as @MisraLavrov has showen, its solvable with methods from graph theory. One example of those methods is the concept of vertex-coloring, where adjacent (by an edge connected) vertices have to be colored different. In the following, I will explain how to translate your problem to graph theory and how to solve it there.

---

Graph
Let $G=(V,E)$ be a Graph with 100 vertices (= people).
Group problem
In graph theory you can reduce sorting people in groups to finding vertex-colorings. That means, in a proper coloring each vertex represents a person and the colour its group. Here only 4 different colours are allowed.
Neighbour problem
Algorithm
Now we build a graph-circle out of $G$ by connecting each vertex to exactly two others. Therefore you start at a vertex, connect it to an unconnected and repeat this. If you get to the last unconnected vertex, just connect it to the first.
Explanation
The edges solve the neighbour problem, because in vertex-colorings adjacent vertices have to be colored different.
Countryman problem
Algorithm
To complete the graph, you make always an edge between vertices (people) from the same country. Explanation
The edges between people from the same country prevents them for getting colored identically.
Solving the group problem
When the graph is finished, you start coloring. Therefore are many different ways and algorithms known and easily found in the internet (for example [1]). Although vertex-coloring is NP-complete, this kind of graph can be colored faster.

Internet research
[1] https://www.researchgate.net/publication/292100744_Graph_coloring_algorithms

---

I hope this helps and gives an insight to translating general mathematical problems into graph theory problems.