* Exercise 6.3. There are n people who can shake hands with one another (where n

Question

* Exercise 6.3. There are n people who can shake hands with one another (where n 1). Use pigeonhole principle to show that there is same number of always a pair of people who will shake hands with the people Hint. Pigeonhole principle does not immediately apply to this problem (1) There is no person who shakes hands with everyone else (all (2) There is a person who shakes hands with everyone else (hand- Solve the problem for two cases handshake numbers are strictly less than n - 1). Easy case shake number is n -1). What can you say about handshake numbers ror everyone else!

Explanation / Answer

(a) If no person shakes hands with everyone else , Then the possibility of handshakes for each person is 0,1,…,n-2. As there are n-1 persons who shake hands with each other and one person can shake hands with n-2 remaining people.

(b) There is a person who shakes hand with everyone else , therefore the possibility of handshakes of each person are 0,1,....,n-1. But if there is a perosn with n-1 hand shakes , there cannot be a person with 0 handshakes (as two person are required in a handshake). So the handshake numbers are 1,2,.....,(n-1)

So in cases(a) and (b) there are two sets

Sa = {0,1,2,... n-2} => |Sa| = n-1

and  

Sb = {1,2,3....n-1} => |Sb| = n-1

In both cases we have (n-1) possibilities(pigeonholes) and n persons (pigeons) , therefore using pigeonhole principle , we can say that at least two persons must have done the same number of handshakes

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.