Team Selection Test for IMO 2019

Answer: $m=2n-1$. Let us show that if a device has a good labeling by $R_n$ then it has a sensitive labeling by $R_m$, where $m=2n-1$. In $$R_m=R_{2n-1}=\{-(n-1),-(n-2),\dots ,-1,0,1,\dots ,n-2,n-1\}$$ there are $n$ non-negative elements. Any good labeling of the device by these $n$ non-negative elements will be also a sensitive labeling.

Now we construct a device which has a good labeling by $R_n$ and has no sensitive labeling for any $m<2n-1$. Let us define a grid $2n-1\times n$ ($2n-1$ lines and $n$ columns) and place a ball into each cell. Let us connect any two balls belonging to the same line by red rope and any two balls belonging to different lines and different columns by white rope (there is no rope between any two balls from the same column). The device has a good labeling by $R_n$. Indeed, there are $n$ distinct colors and if we color all balls from the same column identically and balls from different columns differently then we get a good labeling.

Suppose that the device has a sensitive coloring by $R_m$.

Case 1. There is a line all balls of which are differently colored. Since all balls of this line are connected by red ropes, for each $k$ at most one of the colors $\{-k,k\}$ is used. Therefore, the total number of elements in $R_m$ with different absolute values should be at least $n$ and consequently $m\ge 2n-1$.

Case 2. Each line contains at least two identically colored balls. Suppose that the repeated color on some two lines are $a$ and $b$. Since any two balls belonging to different lines and different columns are connected by a white rope we get $a\ne b$. Therefore, repeated colors of any two lines are different and the total number of different colours is at least $2n-1$ and consequently $m\ge 2n-1$. Done.