IZhO 2010 2-nd round-2

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

IZhO 2010 2-nd round-2

G H J

Reveal topic tags

greatest common divisor

modular arithmetic

combinatorics proposed

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ovchinnikov Denis

470 posts

Ovchinnikov Denis

#1 h Sep 4, 2010, 2:46 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

802 posts

Rofler

#2 h Sep 4, 2010, 3:43 PM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1343 posts

jgnr

#3 h Sep 18, 2010, 9:53 AM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a