4. There are $n>2$ students sitting at a round table. Initially each student has exactly one candy. At each step, each student chooses one of the following operations:

(i) Pass one candy to the student on their left or the student on their right.

(ii) Divide all their candies into two, possibly empty, sets and pass one set to the student on their left and the other to the student on their right.

At each step the students perform their chosen operations simultaneously. An arrangement of candies is legal if it can be obtained in a finite number of steps. Find the number of legal arrangements.

(Two arrangements are different if there is a student who has different numbers of candies in each one.)

(Cyprus)

Time allowed: 270 minutes.

Each problem is worth 10 points.
4. We start by noting that the number of all arrangements is $\binom{2 n-1}{n}$.

Lemma. In two steps, any student can pass a candy (assuming he has one) to the student sitting two places to the left or right, so that the numbers of candies at other students do not change.

Proof. Consider three adjacent students $A, B$ and $C$ left-to-right, with $A$ having at least one candy. Let all students perform operations of type (ii). Then each candy arbitrarily moves one place left or right. Thus, in the first step all candies can be moved right, and in the second step all candies can be moved back left, except for one at student $B$ who will pass it right to $C$. In this way, one of the $A$ 's candies is now at $C$. The other direction is analogous.

Assume $n$ is odd. Since the distance between any two students is either clockwise or counterclockwise even, each student can repeatedly use the Lemma to send a candy to any other student in an even number of steps. Thus all arrangements are legal.

Now assume $n$ is even. After every step, the students on even positions have at least one candy in total, and so do those on odd positions. Thus the $2(\underset{n}{3 n / 2-1})$ arrangements in which all candies are on odd positions or all on even ones are illegal. It remains to show that all other arrangements are legal.

By the Lemma, it suffices to show that, for each $a=1,2, \ldots, n-1$, we can obtain at least one arrangement with exactly $a$ candies on even positions. We start by using the Lemma to send all candies to two adjacent students $A$ and $B$, with $A$ on an even position. Suppose w.l.o.g. that, at this point, $A$ has $a^{\prime}>a$ candies. In the first step, $A$ passes a candy to $B$, and $B$ passes a candy to his other neighbor $C$. In the second step, $A$ and $B$ exchange a candy, whereas $C$ gives his candy back to $B$. Now $A$ has $a^{\prime}-1$ candy, and $B$ has the remaining $n-a^{\prime}+1$. Repeating this procedure $a^{\prime}-a$ times we reach a desired arrangement.

Therefore, the number of legal arrangements is $\binom{2 n-1}{n}$ for $2 \nmid n$, and $\binom{2 n-1}{n}-$ $2\left(\begin{array}{l}3 n / 2-1\end{array}\right)$ for $2 \mid n$.

Mathematical Society of Serbia

welcomes you

to the

# 35-th Balkan Mathematical Olympiad 

to be held

in Serbia in May 2018

(the exact location and dates to be announced)

## Mathematical Society of Serbia

![](https://cdn.mathpix.com/cropped/2024_06_04_31a83bcaa45a5783e6aeg-23.jpg?height=194&width=299&top_left_y=442&top_left_x=720)

Serbian mathematical competitions were supported by
![](https://cdn.mathpix.com/cropped/2024_06_04_31a83bcaa45a5783e6aeg-23.jpg?height=186&width=1018&top_left_y=855&top_left_x=362)