Handshake/pigeonhole principle problem

combinatorial-designscombinatoricsgraph theory

There a number of people in a party. Each person shakes hands with exactly 20 people. For each pair of people that shakes hands with each other, there is exactly 1 other person who shakes hands with both of them; while for each pair of people that don’t shake hands with each other, there are exactly 6 other people who shake hands with both of them. I am tasked to find the total number of people in the room. I am very confused as to how to invoke 3rd condition, could someone guide me in this respect? Thank you!

Best Answer

For reference, the two complicated rules are

  1. For every pair of people who shook hands, the is exactly $1$ person who shook hands with both of them.

  2. For every pair of people who did no shake hands, there are exactly $6$ people who shook hands with both of them.

Let $n$ be the number of people. There are $20n/2=10n$ handshakes.

Call a triple of people $\{a,b,c\}$ a "two-chain" if exactly two pairs of them shook hands. Let's count the number of two-chains in two different ways:

  • Let $N$ be the number of pairs of people who did not shake hands. Per rule $(2)$, there are $6N$ two-chains.

  • Let $H$ be the number of handshakes. For each handshake $a\leftrightarrow b$, by rule $(1)$, there is another person $c$ which shook both their hands. Let $A$ be the set of 18 other people $a$ shook hands with, besides $b$ and $c$. Same for $B$. Per rule $(1)$ again, no one in $A$ shook hands with $b$ (because only $c$ shook hands with both $a$ and $b$), so for every person $a'\in A$, we have $\{a,a',b\}$ is a two-chain. Similarly for $\{a,b,b'\}$ for $b'\in B$. This leads to $18+18=36$ two-chains per handshake. However, this double-counts the number of two chains since each two-chain has two handshakes, so the number is actually $36H/2=18H$.

This shows that $6N=18H$, or $N=3H$. But we also must have $N+H=\binom{n}2$, the total number of pairs of people. It follows that $$4H=\binom{n}2.$$ But we already had that $H=10n$. Substituting this into the above, you get $n=81$.

Related Question