AoPS - Problem

Source: KJMO 2023 P5

Tags: combinatorics

pokmui9909

04.11.2023 14:01

For a positive integer $n(\geq 5)$, there are $n$ white stones and $n$ black stones (total $2n$ stones) lined up in a row. The first $n$ stones from the left are white, and the next $n$ stones are black. $$\underbrace{\Circle \Circle \cdots \Circle}_n \underbrace{\CIRCLE \CIRCLE \cdots \CIRCLE}_n $$You can swap the stones by repeating the following operation. (Operation) Choose a positive integer $k (\leq 2n - 5)$, and swap $k$-th stone and $(k+5)$-th stone from the left. Find all positive integers $n$ such that we can make first $n$ stones to be black and the next $n$ stones to be white in finite number of operations.

Answer: All $n$ which $5$ divides. If $5|n$, it's obvious that we can do this operation. Assume contrary. If $n$ is not a multiple of $n$, let $n=5k+r$ such that $4\geq r\geq1$. If a white stone is in the $(5m+s).$ place, then it will be in $(5l+s).$ place for some $l$. Let's number the white stones from left to right as $w_1,...,w_n$ and number the black stones from left to right as $b_1,...,b_n$ for their initial positions. Let $f(w_i)$ be the place which the stone $w_i$ will be in the final position and $s(w_i)$ be the place which the stone $w_i$ is in at the initial position. We know that $s(w_i) \equiv f(w_i) (mod 5)$. There are $k$ stones which hold $s(w_i) \equiv 0 (mod 5)$. So there should be $k$ stones which $f(w_i)\equiv 0 (mod 5)$. There should be $k$ numbers in the set $(5k+r+1,5k+r+2,...,10k+2r)$ which is a multiple of $5$. If $r \geq 3$, then the numbers are $5(k+1),5(k+2),...,5(2k),5(2k+1)$ so there would be $k+1$ numbers which gives us contradiction. So $r\leq 2$. There are $k+1$ stones which hold $s(w_i)\equiv 1(mod 5)$. But there are $k$ stones which hold $f(w_i)\equiv 1(mod5)$ which gives us contradiction.