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.
Rearrange the integers from $1$ to $4n$ into
$$\begin{equation}\begin{aligned}
\{& (1,j+1), (2, j + 2), (3, j + 3), \, \ldots \, , (j, 2j), \\
& (2j + 1, 3j + 1), (2j + 2, 3j + 2), \, \ldots \, , (3j, 4j), \\
& \vdots \\
& (4n - 2j + 1, 4n - j + 1), (4n - 2j + 2, 4n - j + 2), \, \ldots \, , (4n - j, 4n) \}
\end{aligned}\end{equation}\tag{1}\label{eq1A}$$
Note each member of the set above is a pair of integers with a difference of $j$. Also, since $j \mid 2n \implies 2j \mid 4n$, all of the integers from $1$ to $4n$ are in this set exactly once each. Finally, this gives that the number of elements of the set is the $4n$ integers divided by the $2$ integers in each pair, i.e., $\frac{4n}{2} = 2n$. Alternatively, you also can get the number of elements by multiplying the number of columns times the number of rows, i.e.,
$$j \times \left(\frac{4n-2j}{2j} + 1 \right) = j \times \left(\frac{2n}j - 1 + 1\right) = 2n \tag{2}\label{eq2A}$$
Thus, by the Pigeonhole principle, choosing $2n + 1$ integers between $1$ and $4n$ means that both of the integers from at least one of the element pairs in \eqref{eq1A} must be chosen, with these $2$ integers therefore having a difference of $j$.
Best Answer
The pigeonhole principle is basically a counting argument that says if you have n items to put into m pigeonholes with n > m, at least on pigeonhole must contains more than one item.
In this particular case, there are 9 students (items) and 2 pigeonholes (genders), so when you have assigned gender to 8 students, you either already have a group (pigeonhole) with 5 students of the same gender, or you have two groups, each with four students. Therefore, regardless of the gender of the 9th student, one of the groups must end up with 5.
Similarly, after you've assigned gender to 6 students, either there were already 3 males, or there were 0, 1 or 2 males. You still have 3 more students, so if there were 0 males, there must have been 6 females, and either the 3 remains students are all males (in which case, there will be 3 males) or one of the is a female (in which case, there will be at least 7 females). The argument for 1 or 2 males out of the 6 is similar.