There are $n$ people standing on a circular track. We want to perform a number of moves so that we end up with a situation where the distance between every two neighbours is the same. The move that is allowed consists in selecting two people and asking one of them to walk a distance $d$ on the circular track clockwise, and asking the other to walk the same distance on the track anticlockwise. The two people selected and the quantity $d$ can vary from move to move. Prove that it is possible to reach the desired situation (where the distance between every two neighbours is the same) after at most $n-1$ moves.
Problem
Source: Gulf Mathematical Olympiad 2013
Tags: vector, function, modular arithmetic, rotation, geometry, geometric transformation, combinatorics unsolved
05.04.2013 21:57
Cal people standing on a track $A_{1}, A_{2}...A_{n}$. Imagine regular $n$-gon on this track $B_{1}, B_{2}...B_{n}$. Consider $n-1$ moves ( $A_{1};A_{n}$ ) ; ( $A_{2};A_{n}$ ) ... ( $A_{n-1};A_{n}$ ) Such that $A_{i}$ will go the shortest arc between $A_{i}$ and $B_{i}$ and end up at $B_{i}$ for $i \leq n-1 $. Define $d_{i}$ as the diffrence between the lengths of $A_{i}$ went clockwise and anticlockwise. It is easy to see that $d_{1} + d_{2}+...+d_{n}=0$ (1) If $A_{n}$ ended at $B_{n}$ then we found desired $n-1$ moves . Else define the shortest length from the final position of $A_{n}$ to $B_{n}$ as $l$. ( $l$ can be negative ) and $ a = \frac{l}{n}$. Now we look at moves ( $A_{1};A_{n}$ ) ; ( $A_{2};A_{n}$ ) ... ( $A_{n-1};A_{n}$ ) such that $d'_{i}=d_{i} - a $ for $i \leq n-1$ And since (1) $d'_{n}= d_{n} + (n-1)a$ And now it is easy to see that the final positions of $A_{i}$ form $n$-gon $B'_{i}$ which is transformed from $B_{i}$ by moving each vertex on the distance $-a$
17.05.2013 17:17
Suppose the clockwise or anticlockwise moving guy meets another person during his walk: can he move right through the other guy, or is the move blocked at this point?
17.05.2013 23:48
No, he is not blocked.
19.05.2013 17:14
Identify the circular track with the unit circle (centered at the origin $O$), and associate with every man $M$ on the track the angle $\alpha(M)$ that the vector $OM$ encloses with the positive part of the $x$-axis. For a situation with $n$ men $M_1,\ldots,M_n$ define the potential function $\sum_i \alpha(M_i) \pmod{2\pi}$. In the initial situation, there are two consecutive men $M_a$ and $M_b$ along the track such that the angle $\angle M_aOM_b$ is at least $2\pi/n$. First we embed the initial situation on the unit circle such that $M_a$ is standing at the intersection point $X$ of unit circle and positive $x$-axis. Then we slowly rotate the situation by an angle of $2\pi/n$. As during this rotation no man crosses point $X$, the rotation increases the angle of every man by $2\pi/n$ and thus increases the potential by $2\pi$. Hence somewhere during the rotation process, the potential must become zero; and that's the good embedding that we choose for the initial situation. For the final situation, we choose a regular $n$-gon $P_1,\ldots,P_n$ on the unit circle that has one of its vertices in point $X$. It is easy to see that the potential value of this final situation is zero. Now we perform the following $n-1$ moves: In the $k$th move ($k=1,\ldots,n-1$), the $k$th man moves from his current position clockwise to the vertex $P_k$ of the regular polygon. Simultaneously, the $n$th and last man moves the same distance counter-clockwise. As a move increases the angle of the counter-clockwise moving man by the same amount as it decreases the angle of the clockwise moving man, the value of the potential function remains constant throughout the game. After the $(n-1)$th move, the first $n-1$ men are standing in the points $P_1,P_2,\ldots,P_{n-1}$. Since the potential is still zero, the only possible position for the last man is the point $P_n$.