Problem 1043

Answer. The minimum possible value of $n$ is $7$.

To construct an example for $n=7$, simply label all people from $1$ to $n$, and let the people numbered $i$, $i+1$, $i+2$ (mod $n$) be mutually hostile. It is easy to check that this group of people satisfies the conditions of the problem. Hence it suffices to prove that $n=4, 5, 6$ are all impossible.

(i) $n=4$: Let these four people be $A$ through $D$. By (a), there must exist two people $AB$ who are not hostile to each other; but by (b), considering $m=1$ and removing $D$, then $ABC$ must be pairwise hostile to each other, a contradiction.

(ii) $n=5$: Let these five people be $A$ through $E$, and without loss of generality assume that $A$ is the person with the most hostilities. Let $d$ be the number of people $A$ is hostile to.

a. $d=4$: Note that after removing $A$, (b) guarantees that among $BCDE$ there exist three people $BCD$ who are mutually hostile, but this means $ABCD$ are mutually hostile, contradicting (a).

b. $d=3$: Suppose $A$ is hostile to $BCD$. By (a), there must exist $BC$ who are not hostile to each other. But by (b), when we remove $AE$, $BCD$ must be pairwise hostile to each other, giving a contradiction.

c. $d \le 2$: Suppose $A$ is not hostile to $DE$. By (b), when we remove $AE$, $BCD$ must be mutually hostile; similarly, when we remove $AD$, $BCE$ must be mutually hostile. But this means $B$ is hostile to at least $3$ people ($CDE$), contradicting the assumption that $A$ is the person with the most hostilities.

(iii) $n=6$: Let these six people be $A$ through $F$, and without loss of generality assume that $A$ is the person with the most hostilities. Let $d$ be the number of people $A$ is hostile to.

a. $d \ge 4$: A contradiction is obtained by a method similar to case (a) for $n=5$.

b. $d=3$: Suppose $A$ is hostile to $BCD$. By (a), there must exist $BC$ who are not hostile to each other. But by (b), when we remove $BC$, there must exist three people among $ADEF$ who are mutually hostile, and this must be $DEF$. But this means $D$ is hostile to at least $3$ people ($AEF$); based on the assumption that $A$ is the person with the most hostilities, we know that $D$ must not be hostile to $BC$. But this means we can remove $BCD$ by (b), obtaining that $AEF$ must be mutually hostile. This contradicts the original assumption that $A$ is only hostile to $BCD$.

c. $d \le 2$: A contradiction is obtained by a method similar to case (c) for $n=5$.