Q: In a class of 146 students, every student is friend with at least one classmate. Show that there
exist at least two classmates who have exactly the same number of classmate friends.
Can I use pigeon hole principle in this case?
If not, which principle I should try?
Attempt: Suppose each person has a different number of friends. Then $S_1$ (student 1) will have $1$ friend, $S_2$ will have two friends, …, $S_{146}$ will have $146$ friends. However, in a class of $146$ students one can have at most $145$ friends. Hence, contradiction. Should I continue like this?
Best Answer
Since there are $146$ students in the class, a student may have at most $145$ friends. If every student had a different number of friends, then the number of friends the students in the class have would have to assume each of the $146$ integer values from $0$ to $145$. However, this is impossible for two reasons. One is that the student with $145$ friends would have to be friends with the student with $0$ friends, which is a contradiction since friendship is a mutual relationship. The other reason is that we are told that each student is friends with at least one classmate. Thus, if we make a list of the number of friends each of the $146$ students in the class has, there are $146$ integers values ranging from $1$ to $145$, so at least two of those values must be the same by the Pigeonhole Principle. Therefore, there are at least two students in the class with the same number of friends.