In a committee there are $n$ members. Each pair of members are either friends or enemies. Each committee member has exactly three enemies. It is also known that for each committee member, an enemy of his friend is automatically his own enemy. Find all possible value(s) of $n$
Problem
Source: HKTST1 2017 P2
Tags: combinatorics
ABCDE
22.08.2016 08:55
Note that among any three people there cannot be exactly one pair of enemies. Also, there cannot be 4-cliques of friends as they must have at least one common enemy who would have at least four enemies. Hence, in any group of four there must be at least two pairs of enemies. Furthermore, there cannot be exactly two by looking at four people A, B, C and D; if AB and AC are enemy pairs then ABD violates the condition and if AB and CD are enemy pairs then ABC violates the condition. If there are three pairs of enemies then they must be of the form AB AC AD or AB BC AC and if there are four pairs of enemies then they must be AC AD BC BD by similar casework. Any groups of four with five or six enemies is fine. Now we claim that the answer is $n=4,5,6$. Clearly $n<4$ is not possible since no one can have three enemies. The construction for $n=4$ is every pair is an enemy pair, the construction for $n=5$ is AB AC AD AE BC BD BE are enemy pairs, and the construction for $n=6$ is a $K_{3,3}$ enemy graph. For $n>6$, note that no four people can form an enemy clique or even have five enemy pairs because two of the people will have three enemies already including each other and thus will have everyone else as a common friend, contradiction. Considering person A and his three enemies DEF, DEF must form a friend clique. But then any other enemies of DEF must be common to all three members, so we have friend triangles ABC and DEF and a enemy $K_{3,3}$ between them. Any other person must be A's friend, so must have D as an enemy, forcing D to have more than three enemies, a contradiction.
ethical_man
28.08.2016 08:52
There are $\frac{3n}{2}$ enemy pairs, so $n$ must be even.
If $n > 6$, then let our members be named $a_1, a_2, ... a_n$. Suppose w.l.o.g. that $a_1$ is enemies with $a_2, a_3, a_4$. Then $a_2$ must be enemies with $a_5, ..., a_n$, absurd. So $n \leq 6$.
For $n = 4$, every pair of members can be enemies. For $n = 6$, take the bipartite graph $K_{3,3}$. The solution is $\boxed{n=4,6}$.
jeff10
07.09.2016 06:26
$n=4$ can just be a totally enemy graph.
Like mentioned in previous solutions, the sum of the degrees of the vertices is $3n$, and each lab contributes $2$ to that sum. Hence, $n$ must be even.
Assume $n > 4$. Hence, each member has at least $2$ friends.
Lemma: If only vertices between friends are connected, we must be able to partition it into complete graphs.
Proof: The given conditions are basically equivalent to the condition that friends have the same enemies. Hence, they must have the same friends. Since this needs to work for all sets of friends, a connected web of friends must all be a friend group together. (This is a really rusty proof, but you get the idea.)
Since each member has $3$ enemies, we can't just have everyone be friends.
If $n > 6$, then each member has $n-4$ friends, so each vertex must be a part of a $K_{n-3}$. However, since $n-3$ is greater than half of $n$, each member must be a part of a complete graph that consists of more than half the members. However, we can only form at most one $K_{n-3}$, so only $n-3$ members can be in a $K_{n-3}$. Hence $n > 6$ won't work.
If $n=6$, then we split them into a $K_3$ and a $K_3$.
In conclusion, our solutions are $\boxed{n=4, 6}$.
Kezer
24.09.2016 23:51
Obviously, this is just a graph theory problem. Everyone has exactly $n-4$ friends, that makes $\tfrac{n-4}{2}$ friendship edges. Thus $n$ is even, as for odd $n$ that fraction is not an integer. Now, it is easy to see that $K_4$ and $K_{3,3}$ are both solutions. For $n>6$ fix a vertex $V$. It has three enemies $E_1,E_2,E_3$ and $n-4$ friends $F_1,F_2,\dots,F_{n-4}$. But then $E_1$ is also an enemy of $F_1,F_2,\dots,F_{n-4}$. Thus $E_1$ has at least $n-3>3$ enemies. Contradiction. Obviously $n \geq 4$. Therefore $n=4$ and $n=6$ are the only solutions.
liekkas
07.05.2017 11:09
ABCDE wrote: Note that among any three people there cannot be exactly one pair of enemies. Also, there cannot be 4-cliques of friends as they must have at least one common enemy who would have at least four enemies. Hence, in any group of four there must be at least two pairs of enemies. Furthermore, there cannot be exactly two by looking at four people A, B, C and D; if AB and AC are enemy pairs then ABD violates the condition and if AB and CD are enemy pairs then ABC violates the condition. If there are three pairs of enemies then they must be of the form AB AC AD or AB BC AC and if there are four pairs of enemies then they must be AC AD BC BD by similar casework. Any groups of four with five or six enemies is fine. Now we claim that the answer is $n=4,5,6$. Clearly $n<4$ is not possible since no one can have three enemies. The construction for $n=4$ is every pair is an enemy pair, the construction for $n=5$ is AB AC AD AE BC BD BE are enemy pairs, and the construction for $n=6$ is a $K_{3,3}$ enemy graph. For $n>6$, note that no four people can form an enemy clique or even have five enemy pairs because two of the people will have three enemies already including each other and thus will have everyone else as a common friend, contradiction. Considering person A and his three enemies DEF, DEF must form a friend clique. But then any other enemies of DEF must be common to all three members, so we have friend triangles ABC and DEF and a enemy $K_{3,3}$ between them. Any other person must be A's friend, so must have D as an enemy, forcing D to have more than three enemies, a contradiction. n=5 is contradiction. See “Each committee member has exactly three enemies”.