58th Ukrainian National Mathematical Olympiad

Note that the condition implies that each of the gentlemen has equal number of friends. Let $n$ denote the number of gentlemen in the club. Each of them has exactly $4$ enemies, therefore exactly $n-5$ friends.

Consider a single gentleman $A_1$. Let $B_1,B_2,B_3,B_4$ denote his enemies. Since each friend of $A_1$ is also an enemy of $B_1$, then $A_1$ has no more than three friends, since $B_1$ has exactly $4$ enemies and no more than that. Consider the following cases.

Case 1. $A_1$ has $3$ friends. Let us denote them by $A_2,A_3,A_4$. In this case, there are total $8$ gentlemen in the club, and this situation is possible when each two of gentlemen $A_1,A_2,A_3,A_4$ are friends, each two of gentlemen $B_1,B_2,B_3,B_4$ are also friends, and each pair $A_i$ and $B_j$ are enemies.

$A_2,A_3$ already have $4$ enemies, which means they must be friends with each other. Consider gentleman $B_1$. Without loss of generality, we can state that his friends are $B_2,B_3$. Analogous to the above, we show that $B_2,B_3$ are friends. Then, $B_4$ does not have any friends. Which makes this case impossible.

Case 2. $A_1$ has $2$ friends. Let us denote them by $A_2,A_3$. Then the club has the total of $7$ gentlemen. Notice that each of the friends of $A_1$ is the enemy of $B_j$. Then each of the gentlemen ...

Case 3. $A_1$ has $1$ friend. Then the total number of gentlemen in the club is $6$. This case is possible. For example, let the pairs $(A_1,A_2)$, $(B_1,B_2)$ and $(C_1,C_2)$ be pairs of friends. All the rest are enemies to each other. It is easy to see that this example satisfies the condition.

Case 4. $A_1$ has no friends. Then $5$ gentlemen, all of which are the enemies of one another, satisfy the condition of the problem.