Here's an idea that might (I'm not sure) work: We regard the sectors as $2n$ colored and numbered points. The problem asks us to show there is a line which contains points numbered $1,2,..,n$ on each of its sides. We draw $n$ segments, each having $2$ points numbered the same as its extremities. It's obvious that no $2$ such segments intersect. I think it's easy to derive from here that there must be a line cutting all $n$ segments, and that solves the problem. Think it's Ok?

I do not see why two segments won't intersect Pierre.

You are right: it is possible for them to intersect . As I said in that message, it just seemed Ok. Sorry.

Now that you broughtit up, does anyone have a really nice and short solution? I think I managed to solve it, but I doubt ever having the patience to write it here, since it's a bit hard to explain (even though it's not long). I have to define all sorts of orientations and stuff . A diagram would help a lot, but I don't know what to use to draw one which is fairly accurate.

I have one i found when the tst was pusblished but i think its the same as you, because it is imposible to write, lot of considerations and things, i will try to do it later

True source of this problem: 20th Tournament of Towns, Spring 1999, Juniors, hard variant, problem 4. Author of the problem: V. Proizvolov. See here: In Russian: http://www.turgor.ru/20/turnir20.php . In English: http://servus.matematik.su.se/matcir/turgor/tg20vo.htm .

Is the official solution not so ugly to be given? Pierre.

Ok Pierre, I will post the official solution soon.

I don't know the official solution, but here my solution is. Let us consider two auxiliary disks consisting of n sectors, one over another. One for blue sectors (we will call it "blue disk") and another for red sectors (we will call it "red disk"). Consider some half-disk on the original disk. There are some blue sectors in it and some red sectors. Consider corresponding sequences of sectors on the blue and red disks. If we rotate the half-disk there are 4 cases of behaviour these sequences: 1. Red sequence rotates clockwise by one sector. 2. Blue sequence rotates counter-clockwise by one sector. 3. One sector from the end of red sequence moves to the head of blue sequence. 4. One sector from the end of blue sequence moves to the head of red sequence. Observe that in all cases the distance between the heads of sequnces always decreases by 1 or allways increases by 1. (Distance is a number of sectors between these heads.) WLOG we may assume that in decreases (otherwise we may consider the distance between the ends of the sequences). Distance is a number from 0 to n-1. Therefore after at most n rotations we will have that such a distance will be 0. It is easy to see that this case corresponds the case that the half-disk contains all numbers 1, ..., n.

It looks pretty much like what I did . I guess it wasn't as nasty as I thought .

Ah... I didn't understand what you meant with the blue/red circles and what is a head and the distance, and how it uses the values... Hope Valentin's proposal would be clearer... Pierre.

Hi!! Maybe the easiest consideration (also the official one ) is to consider the 2 numbers that are equal, of different colors, and closest to each other among all other such pairs. Some checking will help you see that somewhere there lies the sequence we are looking for!

Ok, I think I got it. Thanks Dust. Pierre.

Here is my version: If all the blue sectors lie in a demi-disk, then all the integers are also in it. Suppose that there is no demi-disk with only one color, and suppose that all the integers of the blue sectors are placed. The position of the integers on red sectors is only determined by the position of 1. So, there are n ways to place the integers on red sectors in the counter clockwise direction. Now, I define a bijection between the n diameters, and the n possible positions for the 1 on red sector. A diameter separates the disk in 2 demi-disks, and there is only one position for the red 1 so that all the integers from 1 to n are on these 2 demi-disks (here we use the hypothesis that there is no demi-disk with only one color). It is quite easy to see that this function is an injection (this is again due to the fact that there is no unicolor demi-disk). As the two sets have the same number of elements, the function is also a surjection, which means that for every position of 1, there is a diameter which splits the disk in two demi-disks which contain all the numbers from 1 to n.

Quote: There is a circle, which is divided into 2n sectors. n of them are black and n are white. Now you have to number the white ones consecutively clockwise and the black ones counterclockwise. You have to proof that there is always a way to divide the circle into to halves so you have the numbers from 1 to n in each of them, no matter in which way the black and white sectors are arranged and where you start to number them. Does this work? First of all suppose that there is no line that divides the circle in a black and a white half; in that case that line would verify the assertion. Then order the sectors clockwise and call f(i) the number of sector i, where 0<=i<=2n-1 and "i" is taken modulo 2n and f(i) modulo n. Define also g(i) belonging to {0,1} as the colour of the corresponding sector, where g(i)=0 means "white" and g(i)=1 means "black". Define the k-th "half of the circle" ( k modulo 2n) as the one made up by the n sectors k+1, k+2,... k+n. Consider the sequence f(k+1), f(k+2).. f(k+n); it can be partitioned in 2 nonempty (by the initial assumption) subsequences, the one made up by the f(i) for which g(i)=0, and the one made up by the f(i) for which g(i)=1. The first subsequence is an increasing sequence of consecutive residues modulo n ( in the sense a(i+1)=a(i)+1 (mod n) ) which has as its initial and bottom element f(j) for the "leftmost" (in the sense "conterclockwise-most") j in the k-th half of the circle such that g(j)=0. We will call that element W(k). The second subsequence, on the contrary, is a decreasing sequence of consecutive residues modulo n which has as its initial term, which we will call B(k), f(j) for the "leftmost j" in the k-th half of the circle such that g(j)=1. The fact that the k-th half contains all the n numbers is then equivalent to B(k)=W(k)-1 or D(k)=W(k)-B(k)=1 (mod n).When we pass from k-th half to the k+1-th one. There are 2 possibilities: for the leftmost j in the k-th half g(j)=0 and therefore W(k+1)=W(k)+1 and B(k+1)=B(k), or g(j)=1 and therefore W(k+1)=W(k) and B(k+1)=B(k)-1. In both cases D(k+1)=D(k)+1 (all mod n). Now it becomes obvious thar proceeding clockwise we will reach a k such that D(k)=1, and we are done. Sorry for any mistakes.

Just an addendum: it's problem 1 of 2. round of Bundeswettbewerb Mathematik 2006, too.

I hope that this works. Solution to CWMO Problem: Number the balls in clockwise order on the circle as $\omega_1, \omega_2, \dots, \omega_{2n}$ where $\omega_1$ is chosen arbitrarily. All indices of balls will be taken in $\pmod{2n}$. Let $a_{i}$ denote the number on the white ball either equal to $\omega_i$ or closest to $\omega_i$ in a clockwise direction around the circle. Let $b_{i}$ denote the number on the black ball either equal to $\omega_i$ or closest to $\omega_i$ in a clockwise direction around the circle. Let $c_i = a_i - b_i$. Now, considering the cases corresponding to the colours of consecutive balls, it follows that $c_{i+1} \equiv c_{i} + 1 \pmod{n}$. This implies that varying the ball $\omega_i$ causes $c_i$ to assume all values in $\pmod{n}$. Hence there exists a ball $\omega_{j}$ such that $c_{j} \equiv 1 \pmod{n}$ which implies that $a_j = b_j +1=m$ for some $m$. Now consider the balls $\omega_j, \omega_{j+1}, \dots, \omega_{j+n-1}$. If this set of balls contains $k$ white balls, then these have numbers $m, m+1, \dots, m+k-1 \pmod{n}$ and the blacks balls have numbers $m-1, m-2, \dots, m+k-n \pmod{n}$. Since this forms a complete residue set in $\pmod{n}$, the numbers on the balls $\omega_j, \omega_{j+1}, \dots, \omega_{j+n-1}$ are $\{ 1, 2, \dots, n \}$ in some permutation.

Label the sectors $A_0, A_2, \dots A_{2n-1}$ in circular order. Take the integer $i$ such that the two sectors with number $i$ are closest together over all choices of $i.$ WLOG, the two sectors in question are $A_0$ and $A_k$ where $k \le n.$ Sectors $A_1, A_2, \dots A_{k-1}$ must be all the same color. Suppose WLOG sectors $A_0$ through $A_{k-1}$ are one color and $A_k$ is another, then choosing $A_1, A_2, \dots A_{n}$ works.