Problem 1220

SOLUTION. a) The only way to divide 7 students into two groups, each with a maximum of four members, is to have one group of three and one group of four. Each student in the group of four will have a friend in their group in any division, because it cannot happen that all their friends are in the group of three (there are at least four friends).

So, it is enough to divide the students so that each in the group of three has a friend in it. Therefore, we put any of the students in it and two of their friends.

b) Take any division of 8 students into two groups of four (groups with a different number of students are not considered). If this division does not meet the teacher's intention, we have a student $X$ who is badly placed - all his four friends $A, B, C, D$ are in the other group. We will show that we can swap $X$ and one of the students $A, B, C, D$ so that the total number of badly placed students in the newly formed groups decreases compared to the original state.

After any of the four swaps under consideration, $X$ will no longer be badly placed and all three students who end up in the group with him will be well placed, as they are his friends. The students $K, L, M$, who were in the group with $X$ before the swap, can only be badly placed after the swap if they were already badly placed before (since $X$ is not a friend of any of them). Since student $K$ has four friends and is not a friend of $X$, he must have at least one friend $Y$ in the group containing students $A, B, C, D$. This student $Y$ is suitable for the intended swap with student $X$, as after it, he will also have a friend in his new group - namely student $K$.

We have thus shown that by swapping students $X$ and $Y$, the number of badly placed students decreases. We get some new division; if there is at least one badly placed student in it, we can repeat the previous procedure and again reduce the number of badly placed students. After at most eight steps, we will get a division where there are no badly placed students.

ANOTHER SOLUTION to part b). Consider all possible divisions of eight students into two groups of four. Divisions where someone does not have any friends in their group will be called bad, the rest will be good.

How many bad divisions are there? If a student $X$ has at least five friends, at least one of them must be in his group. If a student $X$ has only four friends and they are all in the other group, we have only one division with this property. Therefore, for a given student $X$, there is at most one division that is bad. We can take one of 8 different students as $X$, so there are at most 8 bad divisions (some may be counted multiple times). Meanwhile, there are $\left(\begin{array}{l}7 \\ 3\end{array}\right)=35$ divisions in total, so at least 27 of them are good.

## GUIDING AND ADDITIONAL PROBLEMS:

N1. In a certain class, every student has at least one friend. Show that we can divide the students into two groups so that each has at least one friend in the other group. [This problem can be approached in several instructive ways, see the model solution to problem 5 in the 3rd series of the winter part of the correspondence mathematical seminar (KMS), 2005/6 academic year, http://kms.sk/archiv.]

N2. Each of six students in a certain class has at least three friends among the other five. Friendship is mutual. Show that we can divide these students into two (non-empty) groups so that each student has at least one friend in their group. Could we do this even if each student had exactly two friends? [If we divide the students in any way into a pair and a quartet, then each student in the quartet has at least one friend in it, as out of their at least three friends, at most two are in the other group. It is enough to take a pair of friends and put the rest in the other group. If each has exactly two friends, we can also divide the students: take a student $A$ and his two friends $B$ and $C$ and put all of them in the first group. The remaining three students $D, E, F$ will form the second group. If a student from the second group, say $D$, had both $B$ and $C$ as friends, students $E$ and $F$ would have at most one friend each. Therefore, $D$ has at most one of $B$ and $C$ as a friend, and since he cannot be friends with $A$ (who already has two friends), he must have at least one of $E$ and $F$ as a friend. The same applies to students $E$ and $F$. We can say even more about the situation with six students, each of whom has exactly two friends. If we represent the students as points and the friendship relationship by connecting the corresponding points, we can get only two different pictures: two triangles, or a hexagon (with the points suitably placed in the plane).]

D1. In a group of $n$ people ($n \geqq 4$), some know each other. The relationship "know each other" is mutual: if person $A$ knows person $B$, then $B$ also knows $A$ and they are called a pair of acquaintances.

a) Prove that if among any four people there are at least four pairs of acquaintances, then any two people who do not know each other have a common acquaintance.

b) Determine for which $n \geqq 4$ there exists a group of people in which there are at least three pairs of acquaintances among any four people and at the same time some two people neither know each other nor have a common acquaintance.

c) Decide whether in a group of six people there can be exactly three pairs of acquaintances and exactly three pairs of strangers in every quartet. [C-57-I-5]

D2. A certain ruler invited 28 knights to celebrate his birthday. Each knight had exactly three enemies among the others.

a) Show that the ruler can seat the knights at two tables so that each knight sits at the same table with at most one enemy.

b) Show that in the case of any such seating, there are at most 16 knights at each table.

(Enmity is a mutual relationship: if $A$ is an enemy of $B$, then $B$ is also an enemy of $A$.) $[51-\mathrm{C}-\mathrm{I}-6]$