Question

There are n people who can shake hands with one another (where n > 1). Use pigeonhole principle to show that there is always a pair of people who will shake hands with the same number of people.

Hint. Pigeonhole principle does not immediately apply to this problem. Solve the problem for two cases:

(1) There is no person who shakes hands with everyone else (all handshake numbers are strictly less than n − 1). Easy case.

(2) There is a person who shakes hands with everyone else (hand- shake number is n − 1). What can you say about handshake numbers for everyone else?

Answer 1

Pigeonhole principle: It States that if 'n' items are put into 'm' containers with n>m , then at least one container must contain more than one item.

From the above question we can consider as below.

Holes or 'm' correspondant to number of hands shaken = m

Each person can shake hand with any body from 0 to n-1 other people, so possible holes is n-1

So as per the question these are the below two cases will exist

case 1: If there is person who does not shake hand with anyone. Then any person can shake hand with atmost n-2 people. so everyone shake hand from 0 to n-2 people. So there are n-1 positions and n people and therefore there will apply pigeonhole principle and there is a pair of people whoke shake hands with same no of people.

Case 2: If every one shake hand with atleast one, then there is atleast one person who has shaked hand fom 1 to n.-1 again by pigenhole principal, there is one place less so two persons are in the same no. shake hands.