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!
Handshake/pigeonhole principle problem
combinatorial-designscombinatoricsgraph theory
Best Answer
For reference, the two complicated rules are
For every pair of people who shook hands, the is exactly $1$ person who shook hands with both of them.
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$.