GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 11

Question

In an academy $10$ people are there and each one of them has an adversary and no one has more than one adversary. During a meeting all $10$ of them shook hands with everyone else except their adversary. The number of handshakes that took place is ________

Comments

yes.

---

So, how the answer is 40 ?

---

@Nihal Singh here every person wont handshake with himself and adversery,so every person is handshaking with exactly 8 persons,total degree=10*8=80,no.of handshakes=80/2=40

Answer 1

$\binom{10}{2} - \frac{10}{2} = 45 - 5 = 40$

Normally we would have 45 handshakes, but as each person have exactly one adversary, we remove exactly n/2 handshakes from that.

So 40 is correct.

Answer 2

We can form a graph with $10$ vertices each representing a person. Since each one has exactly one adversary, it forms a $1-1$ correspondence among the $10$ people and excluding the adversaries we can draw $8$ outgoing edges for each of the $10$ vertices representing a given handshake. This will mean a total degree of $10 \times 8 = 80$ and corresponds to $80/2 = 40$ edges which represents $40$ distinct handshakes.