2
$\begingroup$

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!

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

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

$\endgroup$
-2
$\begingroup$

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.

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

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.