3
$\begingroup$

In the company, each employee has at least 50 acquaintances. It turned out that there are two employees who are familiar only through 9 handshakes (i.e. the shortest way of communication consists of 8 intermediate people). Prove that at least 200 employees work in this company.

My attempts of solution are straightforward. Consider a graph in which the vertices are people, and the edge denotes the familiarity of people. Each vertex has 50 edges and there are 2 vertices whose shortest distance is 9. We enumerate the path. Note that the vertices connected to the first vertex can not coincide with the vertices connected to a 5 or 6 vertex. Similarly, vertices connected to 5 or 6 vertices can not intersect with vertices connected to 10 vertex. Otherwise, the graph would have a path shorter than 9. Thus there are at least 150 vertices in the graph. However, I do not know how to prove about 200 vertices.

Thank you for any help or ideas!

$\endgroup$
3
$\begingroup$

Consider one of the employees at the end of the $9$-long handshake chain, $a$. His acquaintances form a set, $D_a(1)$, of at least $50$ people. Their acquaintances who are not in $D_a(1)$ form a set, $D_a(2)$, which might be small but of course is not empty. The next group of acquaintances is $D_a(3)$ know someone in $D_a(2)$ but no-one in $D_a(1)$, and thus continue with these sets, all non-empty, until we reach $D_a(9)$, of which the other employee in the opening premise, $b$, is a member.

Each member of $D_a(3)$ knows $50$ people who are in either $D_a(2),D_a(3)$ or $D_a(4)$. Each member of $D_a(6)$ knows $50$ people who are in either $D_a(5),D_a(6)$ or $D_a(7)$. And each member $D_a(9)$ knows $50$ people who are in $D_a(8),D_a(9)$ or the potentially-empty $D_a(10)$.

These non-overlapping groups of at least $50$ people each, together with $a$ and $a$'s $50+$ acquaintances $D_a(1)$, give at least $201$ people in total.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.