Handshakes in a party

This is yet another easy problem.
Problem : Prove that in any party there will be at least two persons who have shaken hands with equal number of people.

Solution : Let us say there are n persons attending the party. Obviously, this problem makes sense only when n \geq 2. If no two person have shaken hands with equal number of people then there handshake count must differ at least by 1. So the possible choices for hand shake count would be 0,1,…,n-1. There are exactly n choices and n people. But the catch is that if there exist a person with n-1 handshake count, there can’t be a person with 0 handshake count. Thus reducing the possible choices to n-1. Now, due to pigeon hole principle, we have that at least two person will have the same number of handshake count.

–Saurabh Joshi

Advertisements

Tags: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: