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

### Like this:

Like Loading...

*Related*

Tags: math, theorem

This entry was posted on June 3, 2008 at 6:14 pm and is filed under math, theorem. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply