55th IMO Team Selection Test

Let $A=\{a_1,a_2,\dots ,a_k\}$ and $B=\{b_1,b_2,\dots ,b_k\}$ be the two friendly groups. For arbitrary group $C$ from $A$ denote by $S_C$ the group of all people from $B$ each of which is an enemy of at least one person from $C$. If $|C|>|S_C|$ then $C\cup (B\setminus S_C)$ is a friendly group having more than $k$ members, a contradiction.

Therefore the sets $S_{\{a_i\}}$ satisfy the Hall's condition for system of distinct representatives. Hence, we may assume that $a_i$ and $b_i$ are enemies for all $i=1,2,\dots ,k$.

This means that every friendly group of $k$ members include one person from every pair $(a_i,b_i)$ for $i=1,2,\dots ,k$.

Suppose the enemies of $a_1$ are $b_1,\dots ,b_t$. For a friendly group $S$ such that $a_1\in S$ we have $b_1,\dots ,b_t\notin S$. Hence, $a_2,\dots ,a_t\in S$. From every of the remaining $k-t$ pairs $(a_j,b_j)$, $j>t$ we have to choose one of $a_j$ and $b_j$ to be an element of $S$. Therefore there are at most $2^{k-t}$ such group.

For a friendly group $S$ with $k$ members such that $a_1\notin S$ we have $b_1\in S$. Since from each of the remaining $k-1$ pairs $(a_j,b_j)$, $j>1$ we have to choose one of $a_j$ and $b_j$ to be an element of $S$ we find that there are at most $2^{k-1}$ such groups.

Therefore, the total number of friendly groups of $k$ members is at most $2^{k-1}+2^{k-t}$.