SAUDI ARABIAN MATHEMATICAL COMPETITIONS

We will prove the statement by induction on the maximum number of members in clubs $A,B,C$.

For $n=1$, each club has exactly one member and the statement is obviously true.

Suppose that when the maximum numbers in three clubs is $n\ge 1$, then one of three above conditions holds. Assume that $a\in A$ is friend of all members in $B$. Consider a new member $x$ to make the maximum number of members increased by 1. It is easy to see that if $x\in A$ or $x\in C$, then the conditions are still true (since the members in $B$ remains unchanged).

If $x\in B$, denote $B=\{b_1,b_2,\dots ,b_n,b_{n+1}\}$ with $b_{n+1}\equiv x$. In case $(a,x)$ are friend, the condition 1) is true and we are done. So we may assume that $(a,x)$ are not friend. Partition $C$ into two subsets, $C_1$ has members that are friend of $a$, and $C_2$ has members that are not friend of $a$. Take $c_1\in C_1$ and $c_2\in C_2$ (if any).

For $1\le k\le n$, consider $(a,b_k,c_1)$, we have $(a,b_k)$ are friend (since before adding $x$, member $a$ is friend of all members of $B$) and $(a,c_1)$ are friend so $(b_k,c_1)$ are not friend (by the given condition).

Consider $(a,x,c_2)$, we have $(x,c_2)$ are friend (since $(a,x),(a,c_2)$ are not friend).

- If $x$ is friend of all members in $C_1$ then $x$ is friend of all members in $C=C_1\cup C_2$ and condition 2) is true. - Otherwise, $\exists c_1\in C$ such that $c_1$ is not friend of $x$, also is not friend of all members in $B$. If $\exists a^{\prime }\in A$ such that $(a^{\prime },c_1)$ are not friend, then consider $(a^{\prime },b_k,c_1)$ with $1\le k\le n+1$ then $a^{\prime }$ is friend of all $b_k$, condition 1) is true. Otherwise, $c_1$ are friend of all members in $A$ and condition 3) is true.

Hence, in all cases, the condition is always true.