Show that in a party of $n$ people, there are two people having identical number of friends.
I am a beginner at Pigeonhole Principle problems and have produced a solution to this intermediate level question. I am excited about it and I want my solution to be cross-checked and if anything is going wrong, please point it out.
So here it goes:
Let us consider an $n$ by $n$ symmetric matrix $A$ such that $a_{ij}=1$ if $i$-th and $j$-th persons are friends, otherwise $0$.
Please understand that I have assumed that friendship is mutual in the ordinary sense and also, $a_{ii}=1$ for all $i$. The matrix visualization is not necessary, but it just helped me in my thinking process.
So all we need to do is count the number of $1$'s in a particular row as this will give the number of friends of that particular person to whom that row corresponds. For example, the total number of $1$'s in row $3$ will give the total number of friends the third person has, after we have arbitrarily chosen a first person and begun counting.
So it boils down to showing that there will be two rows with same number of $1$'s. First consider that no person is friend only with himself, and no person has everyone a friend i.e. no row in the matrix has only one $1$ and no row has all $n$ entries $1$. Then the sum of $1$'s in a row can be maximum $n-1$ and minimum $2$, giving a total of $n-2$ possible sums, but there are $n$ rows. So, two rows must have the same sum of $1$'s, and those two persons have the same number of friends.
Now consider the case where one person, say person $1$ is friend with no one except himself. That means $a_{11}=1$ and $a_{1j}=0$ for $j=2,3,...,n$. We claim that in this case, the sum of $1$'s in any row other than the first row, has a minimum value of $2$ and a maximum of $n-1$, which is easy to check. The minimum is not a problem, but in case questions arise regarding the maximum, it is clear that the maximum is not $n$ because that would imply there exists a person with $n$ friends, contradicting the fact that the first person is friend only with himself. So there are $n-1$ rows and $n-2$ possible sums, for which two rows have the same sum.
The case where one person is friends with all others is similar.
We have exhausted all the three cases and thus we are done.
Clearly there is a minimum value of $n$ for which this statement holds, and equally obviously it's not $n=1.$ The statement should be something of the form, "in a party of $n$ people, where $n$ is at least ..., ... ."
I would strongly recommend being much clearer about the fact that you are going to examine three separate cases, prior to starting to describe the first case. Otherwise it can appear that you're making unjustified assumptions, at least until we start reading the other cases and see that you weren't actually supposing that there could not be someone who was friends with nobody else or with everyone.
Edit: I initially thought this was an inductive proof, but on closer examination, I do not think it is. I was misled by the fact that two cases of the proof seem to be eliminating one of the members of the party. The proof can be simplified (as already explained), which would also help to avoid that potential confusion.
One could do an inductive proof, but that's another matter.