A school has two classes $A$ and $B$ which have $m$ and $n$ students each. The students of the two classes sit in a circle. Each student is then given a number of candies equal to the number of consecutive students sitting to the left of him that are from his same class. After distributing the candies, the teacher decides to group the students such that in each group, all the students receive the same amount of candies, and any two students from two different groups should receive a different amount of candies. a) What is the maximum number of students that a group can have? b) Excluding the group where every student receives no candies, what is the maximum number of students that a group can have?
Problem
Source: Vietnam TST 2023 P1
Tags: combinatorics
13.04.2023 21:39
\begin{enumerate}[(a)] \item WLOG, assume $m \ge n$, the answer is $2n$. Construction: Alternating put $B$ and $A$ until $B$ runs out, then put the remaining $A$ in one block. There are exactly $2n$ students with 0 candy. Proof of bound: Let the set of student with 0 candy be $S_0$. Define $S_1$, $S_2$, \dots, similarly. It is easily seen that $|S_0| \ge |S_1| \ge |S_2| \ge \dots$. On the other hand, in class $B$ there are at most $n$ students with zero candies. In class $A$, there are at most $n$ students whose left immediete neighbour is from class $B$, meaning there are at most $n$ students with 0 candies. As such, $2n \ge |S_0| \ge |S_1| \ge \dots$. \item WLOG, assume $m \ge n$, the answer can be described: \begin{itemize} \item If $m > n$, the answer is $n$. \item If $m = n$ and $n$ is even, the answer is $n$. \item If $m = n$ and $n$ is odd, the answer is $n-1$. \end{itemize} Construction: Alternating 2 $B$'s and 2 $A$'s until $B$ runs out, then put all the remaining $A$'s together. This satisfies the number given above. Proof of bound: Like we've seen in part (a), we have $S_1 \ge S_2 \ge \dots $. We split the $B$'s into $t$ contiguous blocks. There are at most $\min(t, n-t)$ people in class $B$ with 1 candy. In class $A$, there are at most $\min(t, m-t)$ people with 1 candy. Indeed, when $m > n$ or $m=n$ and $n$ is even, there are at most $\min(t, n-t)+\min(t, m-t) \le n-t+t=n$ people with 1 candy. When $m=n$ and $n$ is odd, we see that the value is given by exactly $2\min(t, n-t)$, and the maximum of $\min(t, n-t)$ is $\lfloor \frac n2 \rfloor = \frac{n-1}{2}$, so there are at most $n-1$ people with $1$ candy. Thus, this value $\ge |S_1| \ge |S_2|\ge \dots$ is the desired maximum. \end{enumerate}