1. Order the collinear points from left to right, and call them $P_1,P_2,\ldots,P_n$ in this order. 2. It is easy to see that the circles with diameters $P_aP_b$ and $P_cP_d$ with $a<b$ and $c<d$ intersect at two distinct points, if and only if (i) $a,b,c,d$ are four distinct integers and if (ii) the indices satisfy $a<c<b<d$ or $c<a<d<b$. In other words, the circles intersect at two distinct points, if and only if the two intervals $[a,b]$ and $[c,d]$ overlap with each other (that is, they have non-empty intersection, and neither contains the other one). 3. Hence the problem boils down to coloring a so-called proper interval graph (-> google). 4. As proper interval graphs are perfect graphs, their chromatic number coincides with their clique number. 5. As every interval in a clique consumes two new points $i$ and $j$, the maximum clique size is bounded by $k:=\lfloor n/2\rfloor$. Furthermore, the $k$ intervals $[1,k+1]$ and $[2,k+2]$ and $[3,k+3]$ and $\cdots$ and $[k,2k]$ form a clique. 6. This yields that the answer is $\lfloor n/2\rfloor$.

Sorry if I'm wrong but shouldn't it be something like $\lfloor n^2/4 \rfloor$? Consider the intervals whose left border is to the left of $n/2$ and right border is to the right of $n/2$: there are $\lfloor n^2/4 \rfloor $ of them and all of them intersect, so the answer is at least that...? A simple greedy construction should suffice: say we have colored all segments which cross $P$ (i.e. left border is to the left of $P$ and right border is to the right of $P$). To color all segments which cross $P+1$, we remove all segments which end at $P$ and add those which start at $P+1$ and color the new intervals with distinct colors (possibly with those that have been removed at the last step); this way the set of intervals crossing $P$ have at most $P(n-P)$ distinct colors, which is maximized at $P = n/2$. EDIT: Ignore.

AnonymousBunny wrote: Sorry if I'm wrong but shouldn't it be something like $\lfloor n^2/4 \rfloor$? Consider the intervals whose left border is to the left of $n/2$ and right border is to the right of $n/2$: there are $\lfloor n^2/4 \rfloor $ of them and all of them intersect, so the answer is at least that...? Nope. For example when $n=4$, and the points are ordered like $P_1P_2P_3P_4$ on the line, the circle with diameter $P_2P_3$ is completely inside the circle with diameter $P_1P_4$

test20 wrote: 4. As proper interval graphs are perfect graphs, their chromatic number coincides with their clique number. 5. As every interval in a clique consumes two new points $i$ and $j$, the maximum clique size is bounded by $k:=\lfloor n/2\rfloor$. Furthermore, the $k$ intervals $[1,k+1]$ and $[2,k+2]$ and $[3,k+3]$ and $\cdots$ and $[k,2k]$ form a clique. 6. This yields that the answer is $\lfloor n/2\rfloor$. Erm, for $n=5$ we need $3$ colors. Assume the contrary, that it can be done with $2$ colors; blue and red. WLOG $[1,3]$ is colored red, then $[2,4]$ is colored blue, so $[3,5]$ is colored red. Then $[1,4]$ and $[2,5]$ are both blue. Contradiction.

The odd case is easy, on similar lines of even case . So lets do it for the latter Let $n=2m$. We easily get that we need at leasr $m$ colours by looking at $(1,m+1),(2,m+2)...(m,2m)$ which form a $m$ clique. Now we give a construction for $m$ colours. Define sets $S_1={0,1}, S_2={2,3}.... S_m={2m-2,2m-1}$. Now give a circle $(x,y)$ the colour $c_i$ if $x+y(mod 2m)$ belongs to $S_i$. We claim that no two circles of same colour intersect at two pts.Indeed if $(a,b),(c,d)$ intersect with $a<c<b<d$ then $c+d-a-b$ will be strictly between $2,2m-2$ hence they are not of same colour. Done!!

I'm not sure where the hole is in test20's argument, but I am also getting $\lceil n/2 \rceil$. For even $n$ this lower bound is obvious since it's the clique number. If $n = 2k+1$ and we try to do it in $k$ colors, then $P_1 P_{k+1}$ and $P_{k+1} P_{2k+1}$ must have the same color $R$ (all other $P_i P_{i+k}$ form the other $k-1$ colors), which then means none of $P_i P_{i+k+1}$ can be color $R$. But they form a $k$-clique, so this is a contradiction. For $n = 2k$, a construction (that I got sniped with) is to color $P_i P_j$ with color $\left\lfloor \frac{i+j}{2} \right\rfloor$ taken mod $k$, and $n = 2k-1$ can be constructed by just removing some of the circles from $n = 2k$.

Aaargh. The hole is that the graphs are not "proper interval graphs" (which are perfect), but "interval overlap graphs" (which are not perfect graphs). http://www.graphclasses.org/classes/gc_913.html

Initially I used a similar thought process as test20, but the problem reduces to a subgraph $S$ of an interval graph $G$. So we know that the chromatic number of $S$ is at most the clique number of $G$, which can be greater than the clique number of $S$ .

vsri56 wrote:

Oh my god I just had written "If n=2 or n=3 the answer is 1 which is trivial" But at the beginning and the end i had written "the answer is $\lfloor\frac{n+1}{2}\rfloor$"

Here's a slightly different solution. Let $f(n)$ denote the answer. I claim that we have $f(n)=1$ if $n=3$ and $f(n)=\lceil n/2 \rceil$ otherwise. It is easy to verify that $f(2)=f(3)=1$. Henceforth we assume $n \geq 4$. First, order the points in $S$ from left to right, and call them $P_1,P_2,\ldots,P_n$. It is clear that the circles with diameters $P_aP_b$ and with diameters $P_cP_d$, with $a<b$ and $c<d$ intersect at two points if and only if $a<c<b<d$ or $c<a<d<b$, i.e. the intervals $(a,b)$ and $(c,d)$ intersect and one does not contain the other. Now I will prove the bound of $\lceil n/2\rceil$. To prove this, I claim that for every color, there are at most $2n-3$ circles with that color. Let $g(n)$ denote the maximum number of circles with one color, given $n$ points ($n>1$). First ignore $P_1P_n$, since we can always add that later. Now consider all circles of some color having a diameter $P_1P_k$, where $k \neq n$, and pick the one where $k$ is maximal. Then, any circle $P_aP_b$ either satisfies $a,b \in [1,k]$ or $a,b \in [k,n]$. In this case, the maximum number of circles we can draw is $g(k)+g(n-k+1)+1$. Thus we have that $g(n)$ is equal to the maximum of $g(k)+g(n-k+1)+1$ over all $k$, where we add $1$ back in to account for $P_1P_n$. Now we use strong induction to prove $g(n)=2n-3$, with the base case of $n=2$ being obvious. If $g(r)=2r-3$ for all $r<n$, then as $k,n-k+1<n$, we conclude that the maximum of $g(k)+g(n-k+1)+1$ over all $k$ is $2n-3$. Thus $g(n)=2n-3$. Since one can always add circles with diameter $P_1P_n$ or $P_aP_{a+1}$, it follows that there are at most $n-3$ circles which are not of those two forms in any color. As there are $\tbinom{n}{2}=\tfrac{n(n-1)}{2}$ circles in total, and $n$ of those are either of the form $P_1P_n$ or $P_aP_{a+1}$, there are $\tfrac{n(n-3)}{2}$ circles which are not of this form. Since we have to divide these circles amongst colors, each of which can only accomodate $n-3$of these circles, we need at least $\lceil n/2 \rceil$ colors, which is the desired bound. Now I will provide a construction. Since $f(n)$ is clearly nondecreasing, it suffices to verify that $f(2k)=k$ for integer $k$, where $k \geq 2$. Number the $k$ necessary colors $0,1,2,\ldots,n-1$. Now color the circle with diameter $P_aP_b$ with color $a$ if $b-a<n$ and with color $b$ if $b+a \geq n$. I'll leave it to the reader to verify that this works. Not because I'm lazy or anything. $\blacksquare$

The question can be regarded as a complete graph and we should only focus on the intersection points and we can easily solve this question.

The answer is $1$ if $n=3$, $\frac{n+1}{2}$ if $n$ is odd and $n>3$, $\frac{n}{2}$ if $n$ is even. Mark the points from left to right $P_1,\dots,P_n$. Denote by $\Gamma_{i,j}$ the circle with diameter $P_iP_j$, $1\leq i<j\leq n$. Two circles $\Gamma_{i,j}$ and $\Gamma_{i',j'}$ intersect at two distinct points if and only if $i<i'<j<j'$ or $i'<i<j'<j$. We first give the coloring with least colors used. For $n=2k$, color the circle $\Gamma_{i,j}$ with color $c_l$ iff $$i+j\equiv 2l-1 \quad \text{or} \quad 2l \pmod {2k}$$for $1\leq l\leq k$, $1\leq i<j\leq 2k$. This requires $k$ different colors. For $n=3$, just color all three circles with $c_1$. For $n=2k+1$, where $k>1$, color the circles on $P_1,\dots,P_{2k}$ the same way as the case $n=2k$, then take another color $c_{k+1}$ to color all the circles passing through $P_{k+1}$. Now we show that we can not use any less colors. For $n=2k$, consider the circles $$\Gamma_{1,k+1},\Gamma_{2,k+2},\dots,\Gamma_{k,2k}$$Each pair of them intersect at two distinct points, thus the above $k$ circles require $k$ different colors. For $n=3$, it is trvial. For $n=2k+1$, where $k>1$. Suppose the contrary, assume that we can color the circles with $k$ colors. Consider the circles $$\Gamma_{1,k+1},\dots,\Gamma_{k,2k},\Gamma_{k+1,2k+1}$$The first $k$ circles and the last $k$ circles have different colors, therefore $\Gamma_{1,k+1}$ and $\Gamma_{k+1,2k+1}$ must have the same color, WLOG $c_1$. However, if we now look at the circles $$\Gamma_{1,k+2},\dots,\Gamma_{k,2k+1}$$We can see that these $k$ circles have different colors, but every one of them intersect at two distinct points with either $\Gamma_{1,k+1}$ or $\Gamma_{k+1,2k+1}$. This means it requires at least $k+1$ colors, contradiction. Hence $n=2k+1$ requires at least $k+1$ colors, for $k\geq 2$.

The answer is $\boxed{ \left \lceil \frac{n}{2} \right \rceil}$ when $n > 3$ (and $1$ when $n=3$). If we wrap the line that the $n$ points lie on into a circle, we can see that two semicircles $\{ A, B \}$ and $\{C, D \}$ intersecting corresponds to the two chords $AB$ and $CD$ intersecting inside the circle. WLOG assume the points are equally spaced about the circle. For even $n$ we just draw the $\frac{n}{2}$ diameters; these all have to be different colors, obviously. We can get a construction with $\frac{n}{2}$ colors as follows: color the $\frac{n}{2}$ diameters differently. Then, for any chord parallel to a diameter, color it the same as that diameter. For any chord not parallel to a diameter, rotating the chord $\frac{180^{\circ}}{n}$ counterclockwise will yield a segment parallel to a diameter, which determines the color of that chord. For odd $n$ we do something similar; consider the $n$ "pseudo-diameters"; chords that go from vertex $i$ to vertex $i + \left \lfloor \frac{n}{2} \right \rfloor$. When $n > 3$ there may be at most two pseudo-diameters with the same color; if there are three pseudo-diameters with the same color, two of them must intersect inside the circle. Therefore there must be at least $\left \lceil \frac{n}{2} \right \rceil $ colors used. In this case every chord is parallel to exactly one pseudo-diameter, so color chords the same as the corresponding pseudo-diameter. (Verifying that each construction works is left as an exercise to the reader.)

The answer is $\lceil n/2 \rceil$. Let the points be $A_1, A_2, \dots, A_n$ in that order. Bound: Construct a graph with vertices $(i, j)$ where $1 \leq i \leq n-1$ and $2 \leq j \leq n$, where two vertices $(i, j)$ and $(k, \ell)$ are connected if and only if the circles $(A_iA_j)$ and $(A_kA_\ell)$ intersect. When $n$ is even, I claim there always exists an $n/2$-clique; this is satisfied by the points $(1, n/2+1), (2, n/2+2), \dots, (n/2, n)$. Hence at least $n/2$ colors are required. When $n$ is odd, obviously we must need at least $\frac{n-1}2$ colors. Assume this many colors suffice. Notice that $\left(1, \frac{n+1}2+1\right), \dots, \left(\frac{n-1}2, n\right)$ form a $\frac{n-1}2$-clique; however, $\left(1, \frac{n-1}2+1\right), \dots, \left(\frac{n-1}2, n-1\right)$ and $\left(2, \frac{n-1}2+2\right), \dots, \left(\frac{n+1}2, n\right)$ also both form $\frac{n-1}2$-cliques. Hence $\left(1, \frac{n-1}2+1\right)$ and $\left(\frac{n+1}2, n\right)$ must be colored the same color, say color $1$. However, since $\left(1, \frac{n-1}2\right)$ and $\left(i, \frac{n+1}2+i\right)$ are connected for all $i > 1$, so $\left(1, \frac{n+1}2\right)$ is also colored $1$. However, $\left(1, \frac{n+1}2\right)$ and $\left(\frac{n+1}2, n\right)$ are connected and both colored $1$, hence a contradiction. Construction: For $n$ even, for each circle $(A_iA_j)$, if $i < j - n/2$, color $(A_iA_j)$ by $j \bmod n/2$; otherwise, color $(A_iA_j)$ by $i \bmod n/2$. In this case, if two circles $A_iA_j$ and $A_{i+n/2}A_k$ are colored the same, then $j \leq i+n/2$, so the two circles will not intersect. If $A_iA_j$ and $A_kA_{i+n/2}$ are colored the same, then $k < i$, and $j < i+n/2$, so one circle will contain the other. Hence the coloring is valid. For $n$ odd, just use the coloring for $n-1$ and add one color for all circles that pass through $A_n$.