4
$\begingroup$

The problem: There is a class. In each group of three students in the class there is a pair of friends and a pair of "enemies". Find the maximum number of students in the class.

I tried to play with combinatorics, to find numbers of pairs and triplets. Also there was an idea to assign 0 (enemies) or 1 (friends) to each pair and try to limit sums of pairs and triplets using this measure. Didn't work. Have anyone an idea how to solve it?

$\endgroup$
1
$\begingroup$

We claim that in a class of $6$ students, one can always find $3$ people who are either pairwise friends of pairwise enemies.

Let $v_1, \ldots, v_6$ be all the people in the class. Out of the five people $v_2, \ldots, v_6$, at least $3$ of them have the same feelings towards $v_1$, that is, either all three are enemies or all three are friends of $v_1$.

Let us say, without loss of generality, that $v_2, v_3$ and $v_4$ have the same feeling towards $v_1$, and assume, again without loss of generality, that this feeling is that of friendship.

Note that if $v_2$ is friends with $v_3$ then $v_1, v_2$ and $v_3$ are three people who are pairwise friends and we are done.

So we may assume that $v_2$ and $v_3$ are enemies. Similarly, we may assume that $v_2$ and $v_4$ are enemies, and $v_3$ and $v_4$ are enemies.

But then $v_2, v_3$ and $v_4$ are three people who are pairwise enemies and again we are done.

So we see that as soon as the class size reaches $6$, the condition required in the question cannot be satisfied. So there can be atmost $5$ students in such a class. One can easily construct an example by hand where a class of size five satisfies the required condition so the maximum possible class size is $5$.

In the above discussion, we have implicitly assumed that friendship and enmity are mutual between any two people, and also that given two people, they are either friends or enemies but not both.

$\endgroup$
1
$\begingroup$

Model the group as a complete graph, where every line between students is either blue (friend) or red (enemy).

The Ramsey number $R(3,3)$ equals 6. This already gives an upper bound, if you think about it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.