Here is my solution given in the contest. First, choose a sense, suppose clockwise. Now consider that the tokens are $2n$ frogs and when two tokens $A$ and $B$ are swapped (tokens are read in the chosen sense) the frog $A$ jumped over $B$ while $B$ was crawling back. We are interested only in jumps. We have the following rules: 1) a frog could jump only forward (the chosen sense); 2) a frog could jump only over the frog situated immediately in front of it; 3) if a frog $A$ jumped over $B$, then $B$ couldn't jump over $A$ and $A$ couldn't jump again over $B$; 4) in the end, for every two frogs $A$ and $B$, $A$ jumped over the $B$ or vice-versa. Lemma: There is a frog that jumped over all the others. Proof: Let $M$ be the frog which made the maximal number of jumps. Suppose that $M$ didn't jump over all frogs, then it exists a frog $N$ that jumped over $M$. Until $N$ jumped over $M$, $N$ jumped over the frogs that $M$ jumped over because $N$ had to be immediately behind $M$, otherwise it couldn't jump over $M$. After the jump, $M$ couldn't jump over a bigger number of frogs than the number of frogs $N$ jumped over because $M$ still remains in front of $N$. Therefore $N$ made at least one jump more than $M$, contradiction! Remark. Moreover, using the same method we can easily prove that each frog made a different number of jumps, hence the number of jumps made by frogs are $0,1,2,...,2n-1$. Let $T$ be the frog which made $2n-1$ jumps and $S$ be the frog behind it. (in the chosen sense) We claim that the edge $ST$ was not swapped that solves the problem. Let's prove this result. Denote by $T_0$ the initial position of $T$. Suppose the edge $ST$ was used, then a frog $X$ that was somewhere behind $T$ at the initial moment arrived sometime in the position $T_0$. If it remains there or in a position in front of $T_0$, then $T$ wouldn't jump over $X$. So $X$ returns behind $T_0$, but then a frog $Y$ that was in front of $T$ at the initial moment will reach behind $T_0$ and $T$ will jump two times over it, contradiction! Remark. In the end the order of the frogs will be the same if we read them counter clockwise.

Here is my sketch (1) Prove that if initially the tokens A,B,C are in that order clockwise, then at the end they will be in that order anticlockwise. (2) Use this to prove that there exists a line L such that if token A started in position P, at the end it will be at the position P' (reflection of P through the line). (3) Using parity to prove that L doesn't pass through any vertex, and instead bisects two opposite sides (note: each token moves an odd number (2n-1) of times) (4) Name the two sides that the line bisects X and Y. Prove that each token crosses exactly one of these sides. (Use the fact that each token moves 2n-1 times). (5) Prove that if A and B are initially in positions that are reflections across L, then they either both cross X or they both cross Y. (6) Prove that if A and B are consecutive and in the same side w.r.t L, then they either both cross X or both cross Y. (7) Conclude that one of X or Y isn't used. (8) Assume another edge wasn't used, get a contradiction easily. Thus exactly 2n-1 edges are used.

I think I also proved it for odd numbers with a similar argument

Interesting alternative proof: We arrange 4n counters in a new circle of 2n different kinds like so: $A_1,B_1,C_1,...,H_1,A_2,B_2,...,H_2$ clockwise and (letting the original circle be $A,B,...,H$) identifying A with $A_1,A_2$ and so on. if we swap say $A,B$ n the original circle we swap both pairs of adjacent $A$s, $B$s, in the second so we would get $B_1,A_1,...,H_1,B_2,A_2,...,H_2$. So if we swapped $A,H$ in the original circle we would get $H_2,B_1,...,A_2,H_1,B_2,...,A_1$. In this way the order of the 4n counters at any given time is given by the order of the 2n counters, repeated, and with some $1$s and $2$s thrown in, and for any given $C$, $C_1$ and $C_2$ are always diametrically opposite. Now if we swap $A,B$ the order of $A_1, B_1, A_2, B_2$ around the circle clockwise from $A_1$ changes from $A_1, B_1, A_2, B_2$ to $A_1, B_2, A_2, B_1$ or vice versa, and the orders for any other pair of kinds of counters (even if either of them is A or B, but not both) remains unchanged, and similarly. Thus at the end, the order clockwise from $A_1$ of the 4 counters is $A_1, B_2, A_2, B_1$, and similarly it is reversed for all other pairs of counters. I show inductively that the order of $A_1,B_1 ..., D_1, E_1,A_2,B_2...,D_2, E_2$ clockwise around the circle is $A_1, E_2, D_2, ,...,B_2, A_2,E_1, D_1,...,B_1$. The base case is above. We already know that this is true for everything except $E_1, E_2$. Also $A_1, E_2, A_2, E_1$ and $D_1, E_2, D_2, E_1$ are around the circle in that order, so that is the only place they can go. At the end the order is $A_1, H_2, ..., B_2, A_2, H_1,...,B_1$ rotated somewhat. So it's a reflection of the original 4n counters about some line. If the line goes through a counter (line if 2n odd ), the counter pair furthest from the line moves $2n$ times, which it cannot (every counter swaps 2n-1 times). Otherwise I show that the pair of segments furthest from this line are never involved in a swap. Assume the pairs of segments are where $A_1H_2$ and $H_1A_2$ are at the beginning so the final position is $H_1, ... ,A_1, H_2,...,A_2$. If the $k$th counter crosses where $A_1H_2$ originally were, it takes at least $k$ moves to get there, at least 1 to swap, at least $2n-k$ to get back -- more than $2n-1$ in total, which is impossible. All other situations we want to eliminate are similar. So here nothing would cross where $AH$ originally is.

Nope srry

We will prove a stronger statement: namely, the statement holds for all $k$-gons, even if $k$ is not even. Index the moves starting from 1 and counting upwards. We will sometimes refer to moves as if they were moments in time. Let's assume for the sake of contradiction that every edge has been chosen at least once. For each edge $e$, let's let $t_e$ denote the first time it gets chosen. Let $E$ be the edge that has the latest value of $t_e$; let this value of $t_e$ be $T$. We will focus on $E$. Let us cut the edge $E$ with scissors. We can then line up the remaining edges such that they are all horizontal. This leads to a natural left-to-right ordering induced by $E$ of the vertices. By definition, we know that after time $T - 1$, every edge except $E$ has been chosen. Let $a,b$ denote the tokens that after move $T - 1$ are on the leftmost, rightmost vertices respectively. (This means that move $T$ swaps $a$ and $b$, so after move $T$ the tokens $a,b$ are on the rightmost, leftmost vertices respectively.) It's obvious that before move 1, $a$ is to the left of $b$. Furthermore, until move $T$, token $a$ never moves to the right. This is because if $a$ moves to the right on move $S$, we must have another token $r$ that after move $S$ is always to the left of $a$, contradicting the fact that $a$ is leftmost after move $T-1$. Similarly, until move $T$, token $b$ never moves to the left. Note that each edge is chosen, so if we partition the vertices into two nonempty sets $L$ and $R$ such that every vertex in $L$ is to the left of every vertex in $R$, there must be two tokens $l,r$ (dependent on $L,R$) such that before move 1, $l$ is in $L$ and $r$ is in $R$ but before move $T$, $l$ is in $R$ and $r$ is in $L$. We will call "before move 1" initial, "before move $T$" final, and "after move $T$" coda. We will perform the following algorithm. Define token $y_1 = a$. Now, for each $i \ge 1$, we define: $x_i$ is the token that is final-rightmost such that $x_i$ is initial-left of $y_i$. $y_{i+1}$ is the token that is initial-rightmost such that $y_i$ is final-left of $x_i$ By our above result, $x_i$'s final position is right of $y_i$'s initial position, and $y_{i+1}$'s initial position is right of $x_i$'s final position. We stop when we reach $k$ such that $x_k = b$. At initial, we have $x_1, y_1, x_2, y_2, \cdots, x_k, y_k$ from left to right. It's clear that at final, we have $y_1, y_2, x_1, y_3, x_2, y_4, \cdots, x_{k-2}, y_k, x_{k-1}, x_k$ in order from left to right. After the coda, we have $x_k, y_2, x_1, y_3, x_2, y_4, \cdots, x_{k-2}, y_k, x_{k-1}, y_1$ in order from left to right. Now if any two of these are swapped, we can do the algorithm to reduce $k$ by 1. We can keep doing this until $k$ becomes 2, at which point we get a basic contradiction.

Choose the 2n-1edges which has already used. We will prove that unchoosen 1edge(let this edge @) will not be used. Here is the sketch. Suppose that at the first state the number which is written in each of @ is token1and 2n. If we use the @ let the two tokens which was in the @ is i,j if |j-i|=1 easy contradiction if |j-i|>2 choose the token k(min(i,j)<k<max(i,j)) and think of k,i,j contradiction. (Sorry for my bad englishhh!!!!)

Hopefully this works... ($2n$ is replaced by $n$ in the solution below)

We solve this question for a regular $n$-gon. Claim 1: There exists a token that only moves clockwise. Proof: Suppose otherwise. Consider the movements of all tokens, and choose a token $T$ which has the largest amount of consecutive clockwise moves. Obviously, this number is less than $n$, since we assumed the contrary. Also, WLOG the end of this series of moves isn't the end of $T$'s movements (otherwise, flip the n-gon such that ccw becomes cw, and also reverse the order of all the moves, so now this series of moves begins at the beginning of $T$'s movements.) So, right after this sequence of moves, $T$ must swap with the token directly ccw from it, say $S$. Now, consider the motion of token $S$, in particular its motion during $T$s sequence of clockwise movements. I claim that, during this time, it only moves clockwise. Indeed, if it swaps with its ccw neighbor at some point, say $U$, then $U$ will always stay between $S$ and $T$, since it can't swap with $S$ again, and it can't swap with $T$ since it's counter-clockwise from it. So, we get a contradiction, since $S$ and $T$ can't swap. So, we must have that $S$'s motion is also strictly clockwise. However, its starting position is ccw from $T$'s starting position, and its ending position is further clockwise, so it has a sequence of consecutive clockwise moves which is greater than that of $T$. So, we have a contradiction, and the claim is correct. Now, call the token which only moves clockwise $T$. As $T$ makes $n-1$ swaps, it goes over all but one edge - the edge $e$ directly ccw from its starting position. I claim that $e$ is never operated on. Suppose otherwise, and consider the first operation on $e$. Right before this move, the token $S$ which is on $T$'s starting position has already been swapped with $T$. When it swaps with the other token on edge $e$, say $U$, it will be between $U$ and $T$. However, $T$ can't pass $S$ since it has already swapped with it, so $U$ can't swap with $T$ since it's always on the wrong side of it. Therefore, $T$ and $U$ never swap, and we reach a contradiction, as desired.

Solved with Wizard_32 We start by labelling the stones as $1,2, \dots 2n$ clockwise . We claim that If three stones are present in a clockwise manner initially , then they must be present in a anti clockwise manner at the end. Firstly note that given any $3$ stones $i,j,k$ , with $(i <j<k)$ ,there are exactly two ways in which these stones can appear around the polygon , namely $i \mapsto j \mapsto k$ and $i \mapsto k \mapsto j$ (when looked in clockwise order) . Note that when exactly one pair of stones is swapped , the order of the stones changes . Hence , since there are $3$ swaps in total , we end with $i \mapsto k \mapsto j $ in clockwise order . Hence the claim holds. Note that the above claim implies that the final configuration is a reflection of the initial configuration about a line of symmetry of the polygon . Call that line $\ell$ . Note that the parity of the initial and final positions of the stones are different .(because each of them are involved in $\underbrace {2n-1}_{\text {odd}}$ swaps ) Hence we conclude that $\ell$ passes through the midpoints of two sides of the polygon. Call those 2 sides as $a$ and $b$ from henceforth. WLOG $a= \{1,2n\}$ and $b=\{n,n+1\}$ . Now we consider how the stones move around $\ell$ . Note that every stone must cross $\ell$ atleast once and hence it must be swapped at atleast one of $\{a,b\}$ . We now claim that every stone must be swapped (possibly multiple number of times) at exactly one of $\{a,b\}$ . To prove this, assume FTSOC there exists a stone $s$ that is swapped atleast once at both $a$ and $b$ . Assume WLOG that the swap occurs at $a$ occurs before that of $b$ . Then the path of the stone $s$ must be something like : It moves from $s$ to $a$ . This accounts for $s$ swaps . It moves from $a$ to $b$ . This accounts for $n$ swaps . It moves from $b$ to $2n+1-s$ .This accounts for $n-s$ swaps. Hence the total number of swaps involved is $s+n+(n-s)=2n$ . However this isn't possible and the claim holds . Now we prove that atleast one of the edges $a$ and $b$ is actually never used . This completes the proof . FTSOC assume that a swap occurs at both of $a$ and $b$ and assume that the token moving clockwise in the swaps are $x$ and $y$ . Initially $x$ and $y$ start out from different sides of $\ell$ . Also by the above claim $x \neq y$ . Consider the instant when the $x \leftrightarrow y$ swap occurs. WLOG this occurs on the same side of $\ell$ as $y$ . We note that before this instant $x$ must have crossed $a$ and $y$ has to cross $b$ atleast once after this . Note that from this instant onwards, $x$ is always constrained to move on the clockwise arc $y \mapsto b$ . However $y$ must cross $b$ at some instant so this cant hold true. We arrive at the desired contradiction. $\blacksquare$

For clarity's sake, say that a token $A$ "hops" over another token $B$ if when $A$ and $B$ are swapped $A$ moves clockwise.Additionally read "left" and "counter-clockwise" as equivalent. First, observe that if $A,B,C$ lie clockwise in that order, they will stay in that order unless a swap occurs among some of them, in which case the two tokens which are swapped will swap in order. In particular, if $A$ is to at some point hop over $C$, either $A$ must first over $B$ or $B$ must first hop over $C$. Claim. There exists some token which hops over every token. Proof. Let $T$ be the token that hops the most. Suppose for the sake of contradiction, that there exists a token $S$ which hops over $T$. Moreover, let $S$ be the first token to do so. Call the move on which this happens the reckoning. We claim that $S$ also hops over all tokens which $T$ hops over. Suppose that $A$ is a token which $T$ hops over before the reckoning occurs. Immediately after $T$ hops over $A$, the tokens $S,A,T$ lie clockwise in that order. Hence $S$ must as some point hop over $A$ in order to reach the vertex immediately to the left of $T$. Similarly, let $B$ be a token which $T$ hops over after the reckoning. Then, in the immediate aftermath of the reckoning, $T,S,B$ lie clockwise in that order. Thus, in order for $T$ to hop over $B$, $S$ must first hop over $B$. It follows that $S$ hops over each token that $T$ hops over. Since $S$ also hops over $T$, this contradicts the maximality of $T$, concluding the proof of the claim. Let $V$ be the vertex which $T$ starts on. Then we claim that the edge immediately to the left of $V$ is never chosen. Suppose otherwise for the sake of contradiction, and let $A$ and $B$ be the first tokens which are swapped on it, with $A$ on $V$. Since $A$ occupies $V$, it follows that $A$ has already swapped with $T$. After $A$ and $B$ are swapped, the tokens $T,A,B$ lie clockwise in that order. Thus in order for $T$ to hop over $B$, $A$ and $T$ must swap. However, they cannot swap again.

Inscribe the $2n$-gon in a circle. There are two main parts to the problem. Claim 1: If token $A$ is directly counterclockwise from token $B$ initially, then $A$ ends directly clockwise from $B$. Proof: Consider the clockwise-direction arc from $A$ to $B$ (not including either), which initially contains no tokens. It is clear by induction that the tokens inside this arc are precisely those which have swapped with $A$ or $B$ a different parity of times than the number of times $A$ and $B$ have swapped: that is, if $A$ and $B$ have not swapped yet, the arc contains tokens which have swapped with $A$ or $B$ an odd number of times, and if $A$ and $B$ have been swapped then the arc contains tokens which have been swapped with $A$ or $B$ an even number of times. Then when every token has been swapped exactly once, the clockwise arc from $A$ to $B$ should contain every token, which implies the conclusion. $\blacksquare$ Now place the $2n$-gon in the complex plane with its center as the origin and the midpoint of an arbitrary edge as $1$. Let $z=e^{\pi i/n}$ be a primitive $2n$-th root of unity. Then by the above claim, there exists some choice of $k$ such that mapping $w \mapsto \overline{w}z^k$ sends the original configuration to the final one (with no rotation). As $w$ ranges among the $2n$-th roots of unity (i.e. the midpoints of edges), it is clear that there are two diametrically opposite fixed points. If we draw the line $\ell$ connecting these fixed points, then each token's final position is the reflection of its initial position over $\ell$. Call the two edges whose midpoints $A$ and $B$. Claim 2: The parity of the number of times a token swaps over $A$ (similarly $B$) is the same across all tokens. Proof: Take two fixed tokens $(i,j)$, and consider the relative ordering of $i$ and $j$, where we start from the midpoint of $A$ and move clockwise (the token that comes first is the one we hit first). WLOG let $i$ start before $j$, so it ends after $j$. The relative ordering is swapped whenever $i$ and $j$ swap with each other, and also whenever exactly one of $i$ or $j$ is swapped across $A$. It then clearly follows that the number of times $i$ is swapped across $A$ must have equal parity as the number of times $j$ is swapped across $A$. Since this is for arbitrary $i,j$, the conclusion follows. $\blacksquare$ Also note that a token clearly must move over $A$ or $B$ an odd number of times in total. On the other hand, we also have the following claim. Claim 3: No token can move over both $A$ and $B$. Proof: A token moves a total of $2n-1$ times. This is enough to exclude the token from moving over $A$, then $B$, then $A$, since in this case it would have to have made a complete revolution about the polygon ($BAB$ is similarly forbidden). Thus it clearly suffices to show (by symmetry) that we can't move over $A$ twice in a row and then move over $B$—cases with larger odd numbers can easily be reduced to this. But this is just a simple arithmetic calculation: if we make $k$ moves, then swap over $A$ and back again (for $2$ more moves), then move over $B$ (taking $n$ moves), we need $n-k-1$ moves to reach the final position of the token, for a total of $2n+1$ moves, which is too many. $\blacksquare$ Then claims 2 and 3 together imply that the (unique) edge among $A$ and $B$ which every token gets swapped over an even number of times must actually never get swapped over, so we're done. $\blacksquare$ Remark: I think for an odd number of vertices you might be able to consider the edge that gets fixed and the vertex diametrically opposite it instead.

Label the tokens $1, 2, \dots, 2n$ in clockwise order in their initial position. Claim: Consider a triple $(i, j, k)$ of stones with $i<j<k$. Then in clockwise order, the ending state has these stones in the order $i, k, j$ in clockwise order. Proof. Note that the order of these stones are changed exactly $3$ times, by a swapping two of them each time. By casework on the possible swaps, it is easy to see that the resulting ordering will be $i, k, j$ or a cyclic shift of it, as claimed. Claim: In the ending state, the pairs $(k, 2n+1-k)$ have been swapped for $k=1, 2, \dots, n$. Proof. Globalize the previous claim. Claim: Let $f(k)$ denote the direction of the final move (clockwise or counterclockwise) of token $k$. Then $f(k)$ is the same for $k=1, 2, \dots, n$ and the same for $k=n+1, n+2, \dots, 2n$; $f(k) \neq f(2n+1-k)$ always. Proof. For the first part, assume otherwise. Then there exist two tokens that will land on the same vertex in the ending state (by using the previous claim), a contradiction. For the second part, we have a similar contradiction. Claim: One of the edges that had $v=\{1, 2n\}$ and $w=\{n, n+1\}$ as vertices in the initial state was never swapped. Proof. First, I claim that for each stone $x$, $x$ is swapped by exactly one of $v$ and $w$. It takes at least $2n$ moves to move $x$ from its initial position to $v$ to $w$, a contradiction. Next, I claim that one of $v$ and $w$ is never swapped. Assume otherwise. Then there exists a stone $x$ that is swapped only by $v$ and not $w$ and a stone $y$ that is swapped only by $w$ and not $v$. However, this implies that $x$ and $y$ can never be swapped, so we again have a contradiction, proving the claim. The last claim implies the problem statement, and we conclude.

this is a problem ig Order the stones counterclockwise as $X, Y, \dots$. Now, WLOG assume that the first two stones swapped are $X$ and $Y$ such that $X$ is counterclockwise to $Y$ afterwards. Let the arc of stones (initially empty) between $X$ and $Y$ be the buffer, and the rest of the $n-2$ stones be the ground. Note that each other stone swaps with both $X$ and $Y$. If it swaps with $X$ first, call it $X$-biased. If it swaps with $Y$ first, call it $Y$-biased. Claim: $X$-biased stones and $Y$-biased stones only swap in the buffer, or after one of the stones has passed through the buffer back into the ground. Proof. If not, they would swap in the buffer, contradiction. $\blacksquare$ Thus, going counterclockwise, we have $X$, then $X$-biased vertices, then $Y$, then $Y$-biased vertices. Let $E$ be the edge between $X$ biased and $Y$-biased vertices. Claim: No swap at $E$ can occur with $X$ or $Y$. Proof. Each $X$-biased vertex moves $X$ and $Y$ both counterclockwise, each $Y$-biased moves them both clockwise. However, there isn't enough of either to make it so $X$ crosses $E$ counterclockwise or $Y$ crosses clockwise, as desired. $\blacksquare$ Claim: No other stone swaps at $E$. Proof. We first show that the swap at $E$ can't be with an $X$-biased vertex more counterclockwise or a $Y$-biased vertex more clockwise. Each $X$-biased vertex can only swap with other non $X$-biased vertices with it going counterclockwise, so the result of this. As such, by ignoring all $X$-biased vertices but one, any $X$-biased vertex must have swapped with all of the non $X$-biased vertices to get there. Then if such a swap occurs, it must be be betewen two $X$-biased vertices. However, then this means one $X$-biased vertex can't actually be $X$-biased, contradiction. The same idea works for $Y$. Then the only swap can occur if the $Y$-biased stone is counterclockwise of an $X$-biased stone at $E$. However, this contradicts their biases, so we are done. $\blacksquare$ Remark: I proved that the final configuration consists of the initial configuration but reflected. Motivationwise, this just says that after doing things, we effectively flip without going through $E$. I also watched like all of Madoka Magica and Lycoris Recoil while not solving this problem LMAO.