In a group of $n$ persons, (i) each person is acquainted to exactly $k$ others, (ii) any two acquainted persons have exactly $l$ common acquaintances, (iii) any two non-acquainted persons have exactly $m$ common acquaintances. Prove that $m(n-k -1) = k(k -l -1)$.
Problem
Source: Romania IMO TST 1990 p11
Tags: combinatorics
20.01.2021 03:49
Take a graph $G=(V,E)$ where each $i\in V$ is a person and $(i,j)\in E$ iff persons $i$ and $j$ know each other. Fix an $i\in V$. We prove the given inequality using a double counting argument. More concretely, we prove both sides of expression is the number of ``$V-$shaped" objects with one of its floating ends being $i$. Let $i-j-k$ forms the $V$, with $j$ being connected to both $i$ and $k$. Having fixed $i$, $k$ can be chosen in $n-k-1$ different ways: observe that $k$ is non-friend with $i$, and among $n$ people, precisely $n-1-k$ of them are his non-friends. Having fixed $i$ and $k$, they now have exactly $m$ common acquaintances, yielding $m(n-k-1)$. Now, we again fix $i$. Then choose $j$ in $k$ different ways. Having fixed $j$, observe now that among $j$'s friends (where the are $k-1$ of them, excluding $i$), $\ell$ are common, hence they cannot be chosen. This leaves us with $k-\ell-1$ choices. Hence the total is $k(k-\ell-1)$. Comparing these expressions, we immediately recover the desired result.