Show that if n people attend a party and some shake hands with others (but not with themselves), then at the end, there are at least two people who have shaken hands with the same number of people.


  1. If there are N persons and N-1 options for the number of people with whom every person can shake hands, at least two people have shaken hands with an equal number of people.

    What is pigeon hole principle?

    A pigeon hole principle would be a counting argument that states “if you have n items to place into m n boxes, then there are at least two items in a single boxes.”
    Now, according to the question;
    There are N persons at a party, some of whom have shaken hands and others who have not. When two people shake hands, it counts to both of them shaking hands with one person.
    As a result, it is impossible to tell who initiated the greeting. Then there’s the following proposal:
    It is said that at least two individuals have shaken hands the same amount of individuals.
    Although you can shake hands to yourself, an individual can shake hands had between 0 and N-1 persons. That is N different options. If a person had shaken hands to everyone else, then no one has not touched hands with anyone. And the opposite is true.
    As a result, the possibilities 0 and N-1 are mutually exclusive. So we’re down to N-1 people with whom each individual can shake hands.
    To know more about the pigeon hole principle, here


Leave a Comment