We have a circle and two families of $n$ red arcs and $n$ blue arcs, positioned on the circle so that every two arcs of different colors intersect. Can one show that there is a point in the perimeter which is part of at least $n$ arcs?


(The statement sounds very simple. It makes me think the answer should be very simple too, but I've been struggling with this one for a bit and got nowhere.)


After reading Suresh's answer below, I can't help but think that there must be some colorful Helly theorem on manifolds, of which the question above is a special case. At the moment I don't even have a meaningful formulation of what this theorem could be, has it been treated before?



Covering a circle with red and blue arcs
This is the second half of a proof started by Peter Shor.


I assume that the set of arcs is already in a position as in Peter's answer: the red arcs $(L\_1,R\_i)$ are cyclically ordered and all blue arcs are of the form $(R\_i,L\_{i-1})$. For convenience, I also assume that no two of red arcs coincide (and hence their $2n$ endpoints are distinct). This is easy to achieve by perturbation. Let $S$ denote the set of the red endpoints and $r:S\to\mathbb N$ denote the covering multiplicity by red arcs: $r(p)$ is the number of red arcs containing $p$.


Fix the red arcs. Then a configuration is determined by a vector of $n$ multiplicities $T=(t\_1,\dots,t\_n)$ where $t\_i$ is how many copies of a blue arc $(R\_i,L\_{i-1})$ we have. For such $T$ and each $p\in S$, let $b\_T(p)$ be the number of blue arcs (in the configuration defined by $T$) containing $p$. Note that $b\_T$ is linear in $T$. By Peter's observation, we have $b\_{T\_0}(p)=n-r(p)$ for all $p\in S$ where $T\_0$ is the standard vector: $T\_0=(1,\dots,1)$.


We have $\sum t\_i=n$ for every admissible vector $T$. I claim that none of the resulting functions $b\_T:S\to\mathbb R\_+$ strictly majorizes any other. The result follows from this claim applied to $T=T\_0$. To prove the claim, it suffices to find a collection $w:S\to\mathbb R\_+$ of nonnegative weights such that, for every (potentially) blue arc, the sum of weights of points covered by this arc equals 1. Indeed, if such weights are found, we have $\sum\_{p\in S} w(p) b\_T(p)=n$ for any $T$, and the claim follows.


To construct $w$, consider the standard covering map $f:\mathbb R\to S^1$. On the line, we have a discrete set $\tilde S=f^{-1}(S)$ and a collection of segments corresponding to pre-images of the potentially blue arcs (both structures are $2\pi$-periodic). The endpoints of the segments are in $\tilde S$, and the segments are ordered from left to right (none of them is contained in another). Let us first solve the weight problem on the line. Begin with one of the segments and mark is right endpoint. Then take the first segment contained in the open half-line after the marked point, and mark its right end. Repeat for the new marked point, and so on. Then every segment to the right of the first one contains exactly one marked point. Let the marked points have weight 1 and all other points have weight 0. We have solved the weigh problem on a half-line.


Observe that the set of marked points is eventually $2\pi k$-periodic for some integer $k$. This follows from the deterministic nature of the construction: once some $x$ and some $x+2\pi k$ are both marked, the pattern will repeat itself. Hence there is a $2\pi k$-periodic weight function on the whole line. We can make it $2\pi$-periodic by averaging over $2\pi m$-translations, $0\le m<k$. Once it is $2\pi$-periodic, it projects back to the circle.


