I am having trouble with the following combinatorics/graph theory problem:
A mathematical society has three divisions (Pure, Applied, and Statistics), and exactly $n$ mathematicians in each division. Every mathematician has at least $n+1$ friends outside of their division. Prove there exist three mathematicians, one in each division, who are all friends.
This was a problem after the chapter about the Extreme Value Principle, which involves using the fact that every finite set of numbers has a minimum and maximum. Of course, there are lots of potential ways to apply this ("consider the mathematician with the most friends...", or "consider the longest chain of mathematicians, each friends with the next..."), but all the ways I've tried have been fruitless.
There is some sort of clever insight needed to solve this problem that I am missing. I would appreciate any hints in the right direction.
Denote the divisions by $D_1,D_2,D_3$. Consider the mathematician $v\in D_1$ with the greatest difference between the number of friends in each division. Call this difference $k$. Denote the friends of $v$ in $D_2$ by $A$, and his friends in $D_3$ by $B$. WLOG let $|A|\geq|B|$. Then $|A| = \frac{n+1+k}{2}$ and $|B| = \frac{n+1-k}{2}$.
Let $u$ be in $B$. Denote the friends of $u$ in $D_2$ by $C$. By the maximality of $k$, the number of friends of $u$ in either division must be between $|B|$ and $|A|$ since the total number of friends is a constant $n+1$. In particular, $|B|\leq|C|\leq|A|$, so $|C| + |A| \geq n+1$. This means that $|A\cap C|\geq 1$. Let $w$ be in $A\cap C$, then $u, v, w$ is the required group of friends.