
Problem 3. Find the least positive integer $n$ such that there exists a group of $n$ people such that:

1. There is no group of four every two of which are friends;
2. For any choice of $k \geq 1$ people among which there are no friends there exists a group of three among the remaining $n-k$ every two of which are friends.


Solution: Consider a group of 7 people $A_{1}, A_{2}, \ldots, A_{7}$, such that $A_{i}, i=1,2 \ldots, 7$ is not friend only with $A_{i+1}$ and $A_{i-1}$ (we set that $A_{8}=A_{1}$ and $A_{0}=A_{7}$ ). It is easily seen that there are no four every two of which are friends. Also, for any choice of $k \geq 1$ people (in this case $k$ is 1 or 2 ) every two of which are not friends there exists a group of three among remaining $7-k$ people every two of which are friends. Therefore $k \leq 7$.

We prove that for any group of 6 which satisfy the condition 1 ) it is possible to choose a group of $k \geq 1$ every two of which are not friends such that among remaining $6-k$ a group of three every two of which are friends does not exist.

Denote the people by $A_{1}, A_{2}, \ldots A_{6}$. If some of them is friend with the other 5 (wlog suppose this is $A_{1}$ ) it is clear that there are no three among $A_{2}, A_{3}, \ldots A_{5}$ every two of which are friends. Therefore the choice of $A_{1}$ solves the problem.

Suppose one of then is friend with exactly four others (wlog assume $A_{1}$ is friend with $A_{2}, A_{3}, A_{4}$ and $A_{5}$ ) Then the choice of $A_{1}$ and $A_{6}$ solves the problem.

Therefore each person has $0,1,2$ or 3 friends. It is obviuos that there exists a group of three any two of which are friends (otherwise the problem is trivial). Assume that the group $A_{1}, A_{2}$ and $A_{3}$ has this property. Wlog $A_{1}$ and $A_{4}$ are not friends. Therefore among $A_{2}, A_{3}, A_{5}$ and $A_{6}$ there is a group of three any two of which are
friends. If this is $A_{5}$ and $A_{6}$ together with one of $A_{2}$ or $A_{3}$ then there exists a person who is friend with at least four others, a contradiction. Therefore wlog suppose that this group is $A_{2}, A_{3}$ and $A_{5}$. Since $A_{1}$ and $A_{5}$ are not friends and since among the others there is a group of three friends we obtain that either $A_{2}$ or $A_{3}$ has at least four friends which is a contradiction.

Therefore $k=7$.
