We place randomly the numbers $1,2, \dots ,2006$ around a circle. A move consists of changing two neighbouring numbers. After a limited numbers of moves all the numbers are diametrically opposite to their starting position. Show that we changed at least once two numbers which had the sum $2007$.
Problem
Source: Swiss Imo Selection 2006
Tags: combinatorics proposed, combinatorics
26.05.2006 22:11
It works with any $2(2k+1),\ k\ge 0$ instead of that $2006$ (and conversely, it's easy to find examples of such procedures for numbers of the form $4k$ which do not interchange any two numbers with sum $4k+1$). For each move made by a number in a counterclockwise direction add $1$, and for each move made in the opposite direction add $-1$. Clearly, we get a total of zero because each move contributes both a $1$ and a $-1$. Now suppose the contrary to what we want to prove is true, i.e. no two numbers with sum $4k+3$ are ever interchanged. Then for each pair of such numbers, both contribute the same: either $n$ or $-n$ to the total count described above. This means that each pair contributes either $2n$ or $-2n$. However, there's an odd number of pairs: $2k+1$, which means that their contributions cannot cancel out (as they should because we've established that the total coun is $0$), so we have a contradiction.
22.04.2014 18:43
Nice little problem. Let $f(x,y)$ be the number of times $x$ and $y$ switched. Take any $a$, let $a'=2007-a$, and take any $b$. Say the initial configuration of these numbers if $aba'$ (clockwise). Then the final configuration must be $a'ba$ (clockwise). Since $a$ and $a'$ never switched places, it is easy to see $f(b,a)+f(b,a')$ is odd. Let $b'=2007-b$. Now, if we add these values for $a \in \{1,2,...,1003\} - \{b,b'\}$ we get that, since $f(b,b')=0$, $b$ switched places an even number of times. But for $b$ to go from its original position to the diametrically opposite position, $b$ must have switched places an odd number of times. Contradiction. We're done.
10.08.2020 22:31
grobber wrote: It works with any $2(2k+1),\ k\ge 0$ instead of that $2006$ (and conversely, it's easy to find examples of such procedures for numbers of the form $4k$ which do not interchange any two numbers with sum $4k+1$). For each move made by a number in a counterclockwise direction add $1$, and for each move made in the opposite direction add $-1$. Clearly, we get a total of zero because each move contributes both a $1$ and a $-1$. Now suppose the contrary to what we want to prove is true, i.e. no two numbers with sum $4k+3$ are ever interchanged. Then for each pair of such numbers, both contribute the same: either $n$ or $-n$ to the total count described above. This means that each pair contributes either $2n$ or $-2n$. However, there's an odd number of pairs: $2k+1$, which means that their contributions cannot cancel out (as they should because we've established that the total coun is $0$), so we have a contradiction. I think this is wrong because the numbers could both contribute $3n$, or in fact any odd multiple of $n$. But this is easily fixable as in the solution below. Let $n=1007$. Let $x_i(0)=0$ for all $i\in\{1,2,\ldots,2n\}$. If the $t$th move swaps $i$ and $j$ with $i$ moving clockwise and $j$ moving counterclockwise, then let $x_i(t)=x_i(t-1)+1$, $x_j(t)=x_j(t-1)-1$, and $x_k(t)=x_k(t-1)$ for all $k\ne i,j$. Suppose that the numbers are in their final position after the $T$th move. For all $i$, we have $x_i(T) = n(2\ell+1)$ for some integer $\ell$. We now have the following claim. Claim: If $i$ and $j$ never swap, then $x_i(T)=x_j(T)$. Proof: For each increment $t\to t+1$, each $x_k$ changes by at most $1$. We claim that for all $t$, \[-2n+d<x_i(t)-x_j(t)<d,\]where $d$ is the clockwise distance from the original position of $i$ to $j$. This is because $i$ and $j$ never swap, so $\Delta(x_i-x_j)\in\{-1,0,1\}$, and clearly $x_i(t)-x_j(t)\not\in\{d,-2n+d\}$ (that would imply that $i$ and $j$ occupy the same position), so the inequality is always true by discrete continuity. The interval $(-2n+d,d)$ has size $2n-1$, so at most one possible odd multiple of $n$ can be in it, so both $x_i(T)$ and $x_j(T)$ must be that same multiple. This proves the claim. $\blacksquare$ Assuming for the sake of contradiction that $i$ and $j$ never swap when $i+j=2n$, the claim implies that $x_i(T)=x_{2n+1-i}(T)=(2\ell_i+1)n$ for some integer $\ell$. However, we obviously have \[\sum_{i=1}^{2n}x_i(T) = 0,\]so we in fact have \[\sum_{i=1}^n x_i(T) = 0,\]or \[\sum_{i=1}^n (2\ell_i+1) = 0.\]This is a contradiction as $n$ is odd, so we're done.
22.04.2021 13:38
This is a really nice problem. I will prove the following general statement instead. Generalized version wrote: We place randomly the numbers $1, 2, \dots, 2k$ around a circle, for some odd number $k$. A move consists of changing two neighboring numbers. After a limited number of moves all the numbers are diametrically opposite to their starting position. Show that we changed at least once two numbers which had the sum $2k + 1$. To prove this, we fix the position of $1$ as the number in the top position. Assume otherwise, that we can achieve such orientation without switching any two numbers having the sum $2k + 1$. We claim that if the orientation of the numbers is not changed after a finite number of moves, then this finite number of moves involved switching $1$ an even number of times. [asy][asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.9] \draw[line width=1pt,color=green] (-3,0) circle (2 cm); \draw[very thick, red, ->] (-0.5,0) -- (0.5,0); \draw[line width = 1 pt, color = green] (3,0) circle (2 cm); \draw[fill=blue] (-3,2) circle (2 pt); \draw[fill=blue] (3,2) circle (2 pt); \draw[fill=blue] (-5,0) circle (2 pt); \draw[fill=blue] (5,0) circle (2 pt); \draw[fill=blue] (-1,0) circle (2 pt); \draw[fill=blue] (1,0) circle (2 pt); \draw[fill=blue] (-3,-2) circle (2 pt); \draw[fill=blue] (3,-2) circle (2 pt); \draw[fill=blue] (-1.59, 1.41) circle (2 pt); \draw[fill=blue] (1.59, 1.41) circle (2 pt); \draw[fill=blue] (-4.41, -1.41) circle (2 pt); \draw[fill=blue] (4.41, -1.41) circle (2 pt); \draw[fill=blue] (-4.41, 1.41) circle (2 pt); \draw[fill=blue] (4.41, 1.41) circle (2 pt); \draw[fill=blue] (1.59, -1.41) circle (2 pt); \draw[fill=blue] (-1.59, -1.41) circle (2 pt); \node[black, font = \small] at (-3,2.3) {$1$}; \node[black, font = \small] at (3,2.3) {$1$}; \node[black, font = \small] at (-3,-2.3) {$5$}; \node[black, font = \small] at (3,-2.3) {$5$}; \node[black, font = \small] at (-5.3,0) {$7$}; \node[black, font = \small] at (5.3,0) {$3$}; \node[black, font = \small] at (-0.7,0) {$3$}; \node[black, font = \small] at (0.7,0) {$7$}; \node[black, font = \small] at (-4.6, -1.6) {$6$}; \node[black, font = \small] at (4.6, -1.6) {$4$}; \node[black, font = \small] at (1.4, -1.6) {$6$}; \node[black, font = \small] at (-1.4, -1.6) {$4$}; \node[black, font = \small] at (-4.6, 1.6) {$8$}; \node[black, font = \small] at (4.6, 1.6) {$2$}; \node[black, font = \small] at (1.4, 1.6) {$8$}; \node[black, font = \small] at (-1.4, 1.6) {$2$}; \end{tikzpicture}");[/asy][/asy] We'll use the diagram of when $k = 4$ to simplify what I meant by preserving orientation. Now, consider the following pairs of numbers: \[ (2k - 1,2), (2k - 2, 3), \dots, (k + 1, k) \]Note that all of these pair of numbers are the form of $(a_i, b_i)$ in which $a_i$ is in the left of $b_i$. Now, these pairs of number cannot be switched wrt each other, and $1$ can't be switched with $2k$ by assumption. Notice that since $(a_i, b_i)$ can't be switched for all $i$, it means that throughout the process, $a_i$ must stay between the left of $b_i$, except when them switching with $1$: which changes $(a_i, b_i)$ to $(b_i, a_i)$. Since we need to preserve the orientation: each of these switching with $1$ must happen an even number of times for every pairs $(a_i , b_i)$, which means that $1$ is switched an even number of times, proving our claim. Now, we are back to the problem. Consider fixing the circle (like how the original question was supposed to be) instead of number $1$. Since $1$ is switched an even number of time, we claim that the position of $1$ changes by an even number of position. We call a left switch wrt $1$ if $1$ is switched with the number to its left, and right otherwise. Now, our previous claim is true by parity since \[ \text{Displacement} = \# \text{Left Switch} - \# \text{Right Switch} \equiv \# \text{Left Switch} + \# \text{Right Switch} \equiv 0 \pmod{2}. \]Now, suppose that we can achieve the position where all numbers are diametrically opposite to their starting position. Note that the displacement of the number $1$ is $k$, which is odd. However, since the displacement must be even if the orientation is preserved (which is true in our case), this is a contradiction. Therefore, we must change at least once two numbers which had the sum $2k + 1$.
26.02.2023 02:41
Funny problem. Replace $2006$ with $4n+2$. Connect pairs of numbers that add to $4n+3$ with a line segment. Notice that you need an odd number of moves to move every number to the opposite point. we see that every time a pair of adjacent numbers are swapped, given that a line segment does not connect them, some pair of line segments either change from crossing to disjoint or vice versa. Thus, if we make an odd number of moves and never swap two connected numbers, the number of intersecting pairs of line segments is opposite parity to the initial configuration. This is contradiction since if every number is on the opposite point from its position in the initial configuration, the number of pairs of intersecting line segments should be equal in both the initial and end configurations. Thus, we must have swapped two numbers connected by a line segment.
26.12.2023 23:46
Reminiscent of 2013 RMM #6. Assume for contradiction that we never swapped a pair of numbers whose sum is $2007$. We give weights to the numbers as follows. In the initial configuration, let all numbers have weight $0$. When a number moves clockwise, add $1$ to its weight, and when it moves counterclockwise, add $-1$ to its weight. This way, the total weight of the numbers is invariant. Denote the weight of $k$ at the end of the process by $w(k)$. By our assumption, $w(k)=w(2007-k)$ for each $k$. Thus, the sum of $w(k)$ over $k \in \{1, 2, \dots, 1003\}$ is $0$. Meanwhile, we have that $\tfrac{w(k)}{1003}$ is odd for each $k \in \{1, 2, \dots, 1003\}$, which means that the sum of $w(k)$ over these $k$ is odd, owing to the fact that $1003$ is odd. This is impossible since we computed this quantity to be $0$, so we have a contradiction.
22.04.2024 04:50
solved with NTguy smh me when unicode