In every vertex of a regular $n$ -gon exactly one chip is placed. At each $step$ one can exchange any two neighbouring chips. Find the least number of steps necessary to reach the arrangement where every chip is moved by $[\frac{n}{2}]$ positions clockwise from its initial position.
Problem
Source:
Tags: number theory, greatest common divisor, modular arithmetic, combinatorics proposed, combinatorics
04.09.2010 18:43
If the number of chips is even, label them $1,2,\cdots,2k$. Move all chips from $1$ to $k$ only clockwise, and all chips from $k+1$ to $2k$ counter clockwise, making sure that any switch is of a chip from $1$ to $k$ with a chip from $k+1$ to $2k$. Stop moving a chip when it is in it's correct place. This will move each of the $2k$ chips by it's minimum $k$, and it achieves the final position, so the minimum is $\frac{2k^2}{2}=k^2=\frac{n^2}{4}$, where we divided by 2 to accommodate for the fact that a swap moves two chips at once. If the number of chips is odd, then break the chips up into two groups $A$ and $B$, where each chip in $A$ has a net clockwise movement, and each chip in $B$ has a net counterclockwise movement after all moves have been done. If some chip winds around the circle, then the minimum is at least $n+n[\frac{n}{2}]$. If no chip does traverse the circle, then each chip in $A$ moves $[\frac{n}{2}]$, and each chip in $B$ moved $[\frac{n}{2}]+1$. Since the net clockwise motion equals the net counterclockwise motion by the nature of the step move, we have that $[\frac{n}{2}]|A|=([\frac{n}{2}]+1)|B|$. Since $gcd([\frac{n}{2}],[\frac{n}{2}]+1)=1$, we know that $|B|=k[\frac{n}{2}]$, and $|A|=k([\frac{n}{2}]+1)$ for some integer $k$. Clearly $k$ is positive, and since $|A|+|B|=n$, $k$ is uniquely determined. Since $k=1$ works, we must have $|B|=[\frac{n}{2}]$, $|A|=[\frac{n}{2}]+1$, so the number of moves in $A$ is $([\frac{n}{2}]+1)[\frac{n}{2}]$, and the number of moves in $B$ is $([\frac{n}{2}]+1)[\frac{n}{2}]$, so the number of swaps is at most $([\frac{n}{2}]+1)[\frac{n}{2}]$. This number is smaller than $n+n[\frac{n}{2}]$, and is attainable by taking $1,2,...,[\frac{n}{2}]+1$ as $A$, and the rest as $B$, moving them like in the even numbered case. Cheers, Rofler
18.09.2010 12:53
Answer: $[\frac{n}2](n-\frac{n}2)$ Let $k=[\frac{n}2]$. Suppose that chip $i$ is moved clockwise $a_i$ times and anti-clockwise $b_i$ times. So $a_i-b_i\equiv k\pmod{n}$. Let $c_i$ be the integer such that $a_i-b_i=c_in+k$. If we sum over $i=1,\ldots,n$, then $0=\sum c_in + kn$, and we get $c_1+\ldots+c_n=-k$. WLOG assume that $c_1\ge c_2\ge\ldots\ge c_n$. We claim that $c_1+\ldots+c_{n-k}\ge0$. If $c_{n-k+1}\ge0$ then obviously the claim is true, otherwise we have $c_{n-k+1}+\ldots+c_n\le-1-1-\ldots-1=-k$ which gives $c_1+\ldots+c_{n-k}\ge0$, so our claim is proved. Therefore the number of steps is $\sum_{i=1}^na_i\ge\sum_{i=1}^{n-k}=\sum_{i=1}^{n-k}(b_i+c_in+k)\ge\sum_{i=1}^{n-k}k=k(n-k)$. If we move chip 1 by $k$ positions clockwise and each of chips $2,3,\ldots,k+1$ by $n-k-1$ positions anti-clockwise, then each chip is moved $k$ positions clockwise and $k+k(n-k-1)=k(n-k)$ steps have been done.