Given is a group in which everyone has exactly $d$ friends and every two strangers have exactly one common friend. Prove that there are at most $d^2 + 1$ people in this group.
Problem
Source: Czech-Polish-Slovak Match Junior 2019, individual p5 CPSJ
Tags: combinatorics
20.01.2020 23:13
Let $n$ be the total number of people. Let set $S$ be the ordered triples of distinct people $(A,B,C)$ such that $A$ knows $B$, $B$ knows $C$, but $C$ does not know $A$. We count the size of $S$ in two ways. First note that for each $A$, there are $n-d-1$ possibilities for $C$, each of which has exactly on $B$ that completes the triple (By the condition of the problem). Thus $|S| = n(n-d-1)$. Now we count based on first choosing $B$. We choose $A$ and $C$ out of the people $B$ knows, so for each $B$ there are $d \cdot (d-1)$ options for $A$ and $C$ that $B$ knows. (Note that if $A$ and $C$ know each other, this is not a triple in $S$, so instead of an equality this is an inequality). Thus we get $|S| \leq nd(d-1)$ Combining these we get: $$n(n-d-1)\leq nd(d-1) \implies n-d-1\leq d^2-d \implies n\leq d^2+1$$as desired.
20.01.2020 23:24
Look from the perspective of a person $p$. This person has $d$ friends. Each of these friends has $d-1$ other friends beside $p$, so there are at most $d(d-1)$ friends of friends. Since everyone must either be a friend or $p$ or have a friend in common with $p$, there are not more people. The total amount of people is therefore bounded by $1 + d + d(d-1) = d^2+1$.
20.01.2020 23:47
This is generalized by a small lemma in the study of strongly regular graphs. It can be proved more generally that if $G$ is composed of $v$ vertices with degree $k$ such that $2$ adjacent vertices share $\lambda$ neighbors and $2$ non-adjacent vertices share $\mu$ neighbors, then $(v-k-1)\mu = k(k-\lambda-1).$