Suppose that $n$ persons meet in a meeting, and that each of the persons is acquainted to exactly $8$ others. Any two acquainted persons have exactly $4$ common acquaintances, and any two non-acquainted persons have exactly $2$ common acquaintances. Find all possible values of $n$.
Problem
Source: 4-th Taiwanese Mathematical Olympiad 1995
Tags: combinatorics proposed, combinatorics
16.01.2007 19:13
Pick any person, $x$. $x$ has 8 acquaintances, $x_{1}, \ldots, x_{8}$, and he has $n-9$ non-acquaintances, $y_{1}, \ldots, y_{n-9}$. $x_{i}$ and $x$ know each other, so $x_{i}$ knows exactly 4 of the $x_{j}$. Since $x_{i}$ knows 8 people, $x_{i}$ knows exactly 3 of the $y_{i}$. Thus, there are 24 pairs, $(x_{i}, y_{j})$ such that $x_{i}$ knows $y_{j}$. $y_{i}$ and $x$ are not acquainted, so $y_{i}$ is acquainted with 2 of $x$'s acquaintances. Thus $y_{i}$ knows 2 of the $x_{j}$. Thus there are $2(n-9)$ pairs, $(y_{i}, x_{j})$ such that $y_{i}$ knows $x_{j}$. Obviously, however, we have counted the same quantity in two different ways. Thus $24 = 2(n-9)$ so $n = 21$ is the only possibility. We need to establish that it is realizable. I'm sure there's some clever construction, but I don't see it right now. The most general version of this question is: For which $n$ is it possible that there exists a graph with $n$ vertices such that each vertex has degree $a$, given any edge $\{x, y\}$ there are $b$ vertices joined to both $x$ and $y$, and given a non-edge $\{x, y\}$ there are $c$ vertices joined to both $x$ and $y$. The same analysis as above gives that $n = \frac{a(a-b-1)}{c}+a+1$, so that expression must be an integer. However, there are more limitations. For example, $a$ and $b$ cannot both be odd, because the subgraph induced by the neighbors of any fixed vertex form a $b$-regular graph on $a$ vertices. Similarly, $n-a-1$ and $a-c$ cannot both be odd because the non-neighbors of any vertex form an $(a-c)$-regular graph on $n-a-1$ vertices.
22.05.2014 08:35
Supose $x_1$ and $x_2$ are not acquainted, so $x_1$ has 4 acquaintances in {$x_3,...,x_8$}, $x_2$ too => $x_1$ and $x_2$ have 2 or more than 2 common acquaintances in {$x_3,...,x_8$} Thus $x_1$ and $x_2$ have more than 2 common acquaintances. Hence not exist n