MODBasic Difficult

Problem - 2088
$N$ delegates attend a round-table meeting, where $N$ is an even number. After a break, these delegates randomly pick a seat to sit down again to continue the meeting. Prove that there must exist two delegates so that the number of people sitting between them is the same before and after the break.

Fix a seat, and then label these delegates from $0$ to $N-1$ clockwise based on their seats. After the break, label these delegates' seat as $a_0$, $a_1$, $\cdots$, $a_{n-1}$.

Now, let's consider $b_i = (a_i - i) \pmod{n}$, where $i=0, 1, \cdots, N-1$.

If there exist $m$ and $k$, such that $b_k = a_m$, then $a_k - a_m = k - m$. This means the intervals between the $k^{th}$ and the $m^{th}$ delegates keeps the same.

Otherwise, if all $b_i$'s are different, they must take distinct values from $\{0$, $1$, $2$, $\cdots$, $N-1\}$. However this is impossible because, on one hand, $\displaystyle\sum_{i=0}^{N-1} b_i = \frac{N(N-1)}{2} \equiv \frac{N}{2} \pmod{N}$. On the other hand, the result should be $0$ by definition because $\displaystyle\sum_{i=0}^{N-1}b_i = \sum_{i=0}^{N-1}(a_i - i) = 0$.

report an error