Gazeta Matematica 11/2015, Problem E:14911

Problem:
In a school, each student knows exactly $2n+1$ other students, where $n \in \mathbb{N}^*$.
Prove that the number of students in the school is even. (Suppose that "`knowing"' is a symmetrical relation).

Proposed by Alessandro Ventullo, Milan, Italy

Solution:

Suppose that two students know each other if and only if they shake their hands. Let $N$ be the total number of the handshakings and let $m$ be the total number of students. Since each student shakes his hand with $2n+1$ other students, there are $m(2n+1)$ handshakings. Since in each handshake are involved two students, we have counted each handshaking twice (one time when student $A$ shakes his hand with student $B$ and one time when student $B$ shakes his hand with student $A$). Therefore, the total number of handshakings is $N=\dfrac{m(2n+1)}{2}$. Since $N$ is a natural number, then $m$ must be even.