Show that at a party of 20 people, there are at least 2 people who havethe same number of friends present at the party. Assume (however unrealistically) that friendship is symmetric and anti-reflexive. Hint:Carefully use the pigeonholeprinciple.

See explanation below

Step-by-step explanation:

The ping hole principle says this : " At a party of N people, some pair of people are friends with the same number of people at the party."

And by properties we need to assume that this relation is symmetric and antireflexive.

We can proof this considering two possible cases listed below:

a) If we assume that a person in the party let's say A, and this person knows every person at the party. So then he needs to know n-1 = 19 people with n = 20 on this case. And every person at the party will know A. So then the possible number of people that a person can know is {1,2, ..., n-1 = 19}

b) We can assume another person let's say B who doesn't know any person at the party, so this person can't know person A and on this case the maximum number of people that a person can know is {0,1,2, ..., n-2=18}

For both cases analyzed above we have two sets with cardinality n-1. We have then that if we have n people at the party there are n-1 possibilities for the number of people that a person can know, but needs to be at least two people who knows the same number of people and the reason is because these people have the same number of friends present at the party (2).