Let $n$ and $k$ be integers such that $n \geqslant 3$. Théo is organizing the class representative elections for his class of $n$ students: each student must vote for one of their classmates (everyone is a candidate), and no one votes for themselves. Then Théo divides the students into groups so that, if a student is in a group, the student they voted for is not in the same group.
For which values of $k$ is Théo sure to be able to divide the students into at most $k$ groups, regardless of how the students vote?
First, if we have three students (let's say Anna, Martin, and Vincent) such that Anna voted for Martin, Martin voted for Vincent, and Vincent voted for Anna, it is clear that Théo will need at least three groups.
Conversely, let's prove by induction on \( n \) that Théo can manage with only three groups, even if some students vote blank.
The base case is clear for \( n=3 \). So, we assume \( n \geqslant 4 \). Since there were at most \( n \) votes, there is at least one student who received at most one vote: we call this student Donald. By forgetting Donald and fraudulently "forgetting" the vote he might have received, replacing it with a blank vote, Théo can distribute the remaining \( n-1 \) students into at most three groups.
Then Théo brings Donald back into the class: among the three groups, there is at least one that does not contain the person for whom Donald might have voted, nor the potential voter of Donald. Théo then places Donald in this group, which concludes the induction.
In summary, the integers sought are the integers \( k \geqslant 3 \).
Comment from the graders: Many students understood that certain cases forced Théo to choose \( k \geqslant 3 \). It was then necessary, for all \( n \), to provide an example of a vote for which 3 groups were necessary.
Subsequently, numerous strategies for distributing the students into 3 groups were proposed, but few were correct. In such a case, trying to prove that the distribution works is always useful: either the distribution is correct, and proving it is necessary to get all the points; or it is not, and failing to prove it often helps to understand why the strategy fails. It is also important not to hesitate to test the distribution given for certain votes: this often easily reveals the problems.
Finally, some students transformed the problem into a graph coloring problem, then claimed that if one could color any subset of 4 vertices of the graph without having two adjacent vertices of the same color, one could color the entire graph without having two adjacent vertices of the same color. This statement is actually invalid, as illustrated by the counterexample below. To avoid such disappointments, we encourage students to provide a proper proof of the different elements they state.
![](https://cdn.mathpix.com/cropped/2024_12_06_4afcafb56238ecaa080eg-05.jpg?height=441&width=426&top_left_y=2141&top_left_x=815)