59th Ukrainian National Mathematical Olympiad

For $k=1$ everything it is obvious. All friends are divided into pairs. In order to be able to split everyone properly, each pair must fall into one subgroup. But each subgroup must have the same number of people. Therefore, if there is an even number of such pairs, that is $n=2m$, it can be done by adding exactly $m$ pairs to each of the subgroups. If $n=2m-1$, then for any division of all people into two equal parts at least in one of the couples people will fall into different subgroups, and therefore they will not have the same friend in their subgroup.

Now, let $k\ge 2$ and, for example, there is a division in which it is impossible to properly divide the group into two subgroups. Let's consider an arbitrary splitting into two subgroups of $n$ people. We denote people with points that are broken up by a vertical line into two subgroups - the left (L) and the right (R).

Draw the line segments between all pairs of acquaintances. The segments between people who fall into one subgroup with such a division will be called important. Now among all possible division, choose the one in which the number of important segments is maximal. We call such a division (or any of these, if there may be several) maximal. Presumably it is impossible to divide the group into two subgroups as needed. Therefore, for a maximal division there exists, for example, in the left subgroup, some person $X$ whose all his/her $k$ friends $A_1,\dots ,A_k$ are in the right subgroup. Consider two cases.

Suppose there are two people $B\in L$ and $C\in R$, that are friends with each other. Clearly, according to the rules the line segment between them is not important. Suppose $C$ has $l\ge 1$ friends in the left side, and $k-l$ friends in the right side. Then let's swap people $X$ and $C$ in subgroups. Let's count how much the number of important segments has changed. The left subgroup has $l$ segments more, and the right side $-k-(k-l)=l$ more. Thus their number increased, and therefore we got a contradiction with the assumption that this is the maximum division.

By the hypothesis for the maximal division we have that there is a person $X\in L$ with all his/her friends are in the right subgroup. At the same time, all other people have friends only in their subgroup.

Consider the case $k=2$. Then all people divide into chains of 3 or more people. Let's denote them as follows: $B_1{B}_2{B}_3\dots B_j,j\ge 3$. The first $B_1$ and the last $B_j$ as well as $B_t$ and $B_{t+1}$ are acquaintances.

Case 1. Suppose a chain with element $X$ has 3 elements, that is $X{X}_2{X}_3$, then all these three elements have to fall into the same subgroup. Let's move them to the left subgroup. If there is at least one chain of 4 or more people $B_1{B}_2{B}_3\dots B_j$ in the left subgroup, $j\ge 4$, then it's enough to move $B_1$ and $B_2$ to the right subgroup the required distribution is done. It is impossible to do it this way, if only all chains in the left side consist of 3 elements. Thus the right subgroup has element $X$ and a few chains of 3 elements. Hence the right subgroup has elements $X_2,X_3$ and at least one chain that does not consist of 3 elements. If there is exactly one cycle of 5 elements with the other cycles of 3 elements, then the required distribution does not exist. Clearly, all elements of cycles of 3 elements have to be in one subgroup. Then the cycle of 5 elements can be divided in two parts $3+2$ and two equal groups does not exist. Hence for $n=2+6m,m\ge 2$ the needed distribution may not exist. Show, that for all other cases the distribution does exists. If there is at least 1 cycle $B_1{B}_2{B}_3\dots B_j$, $j=4$ or $j\ge 6$, which has exactly 4 or more then 5 elements, then we do the following rearrangements: $X$ and some cycle of 3 elements must be moved to the right subgroup, and $B_1{B}_2{B}_3{B}_4$ -- left one.

If there is at least two cycles of exactly 5 elements $B_1{B}_2{B}_3{B}_4{B}_5$ and $C_1{C}_2{C}_3{C}_4{C}_5$, then we move elements $X_2,X_3,B_1,B_2$ and $C_1,C_2$, from left to right, and two cycles of length 3 - from right to left.

Case 2. Let chain with the element $X$ has 5 elements $X{X}_2{X}_3{X}_4{X}_5$. If all other chains have 3 elements each, the distribution may not exist. An example is similar to the one given above for $n=2+6m$, but now $m\in \mathbb{N}$. For $n=8$ we have two cycles of 3 and 5 elements, which, obviously, cannot be divided into two equal subgroups as needed. Let's show that for all other cases distribution is possible. That is, there are cycles not only of 3 elements. If there is a cycle of 4 elements in the left subgroup, move it to the right side, and $X_2,X_3,X_4,X_5$ - to the left side. If there is a cycle of at least 5 elements $B_1{B}_2{B}_3...$, do the following displacement: $B_1,B_2,B_3$ у праву, $X_2,X_3$ у ліву. Thus the left subgroup has only 3 - element cycles. If the right subgroup has a cycle of at least 4 elements $B_1{B}_2{B}_3...$, then move $B_1,B_2$ and $X$ to the left subgroup, and the cycle 3 elements to the right side.

Case 3. Let chain with the element $X$ has 4 elements $X{X}_2{X}_3{X}_4$. If in the left side there are cycles of 3 elements $B_1{B}_2{B}_3$ or at least 5 elements $B_1{B}_2{B}_3...$, then move $X_2,X_3,X_4$ to the left side, and $B_1,B_2,B_3$ - to the right side. The only possibility left is when there are only cycles of 4 elements in the left side. Suppose one of them consists of elements $C_1{C}_2{C}_3{C}_4$. Then the left side cannot have all cycles of 4 elements each. If in the right subgroup there is a cycle of 3 elements $B_1{B}_2{B}_3$ or of at least 5 elements $B_1{B}_2{B}_3...$, then move $C_1,C_2$ and $X$ to the right subgroup, and $B_1,B_2,B_3$ to the left subgroup.

Case 4. Let chain with the element $X$ has at least 6 elements $X{X}_2{X}_3{X}_4...$. If in the left subgroup each cycle has 3 elements $B_1{B}_2{B}_3$, move $B_1,B_2,B_3$ to the right side, and $X_2,X_3,X_4$ - to the left side. If there is a cycle of at least 4 elements $B_1{B}_2{B}_3{B}_4...$, move $B_1,B_2$ to the right side, and $X_2,X_3$ - to the left side.

Consider the case when $k\ge 3$. Then all people are divided into connected components, which have no less than 4 elements each and the degree of each vertex of a component is $k\ge 3$, moreover element $X$ is connected to elements $X_2{X}_3{X}_4...$. If the left side has a connected component of at least 5 elements $B_1{B}_2{B}_3...$, it's enough to move $X_2,X_3,X_4$ to the left side, and $B_1,B_2,B_3$ - to the right side, if the whole connected component consists of 4 elements $X{X}_2{X}_3{X}_4$, otherwise move $X_2,X_3$ to the left side, and $B_1,B_2$ - to the right side. Otherwise, each connected component in the left side has exactly 4 elements. Clearly, that under such conditions the only possibility is $k=3$. Then the right side cannot have connected components of 4 elements. Then since there is a component in the right subgroup, that has at least 5 elements $B_1{B}_2{B}_3...$, move $B_1,B_2,B_3$ to the left side, $X$ and $C_1,C_2$ to the right side, where $C_1,C_2$ - two elements of one connected component.