# Handshake/pigeonhole principle problem?

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!

• What's your question? Invoke the third condition to do what? – Mees de Vries Jul 3 '18 at 15:10
• What are you trying to do? Find the number of people? – fleablood Jul 3 '18 at 15:12
• Yes that’s right, sorry for not making it clear! – user107224 Jul 3 '18 at 15:40

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$.

I'm pretty sure its 90. So I shake 20 peoples hands. And for each set of handshakes means that there is 1 not shook. Meaning 20*.5=10. 20+10=30. But there are 6 extra people whom I don't shake hands with. Meaning 6*10=60. QED 30+60=90.

• Hello, I was told the answer was 81! – user107224 Jul 3 '18 at 17:23