Let $n$ be a fixed positive integer. The points $A_1$, $A_2$, $\ldots$, $A_{2n}$ are on a straight line. Color each point blue or red according to the following procedure: draw $n$ pairwise disjoint circumferences, each with diameter $A_iA_j$ for some $i \neq j$ and such that every point $A_k$ belongs to exactly one circumference. Points in the same circumference must be of the same color.
Determine the number of ways of coloring these $2n$ points when we vary the $n$ circumferences and the distribution of the colors.
I was trying out this problem, and I got stuck..While reading the solution, I couldn't understand this part:
Let $a_1 , a_2 , . . . , a_{2n}$ be the points on the line, in that order. Notice that if
two points are in the same circle, between them there must be an even number of
points, and thus the circles join points with even index with points with odd index.
Thus there is the same number of odd red points and even red points.
Like the last part I followed, that if there are even number of points between two diametric points, then we get equal number of odd blue points and even blue points and the same for red.
But why is it necessary to have even number of points?
Once the above mentioned line is true, we then use induction on $n.$
We are going to prove by induction on $n$ that any coloring that has the same
number of even red points and odd red points can be obtained by drawing circles.
If $n = 1,$ both points must have the same color, thus by drawing the circle that has
their segment as diameter we are done. If there are two consecutive points with the
same color, we can draw a circle that has them as diameter, and we are left with
$2(n − 1)$ points as indicated. These $2(n − 1)$ points can be colored using circles (by
the induction hypothesis). If there are no two consecutive points of the same color,then all even points have one color and all odd points have another, which contradicts our hypothesis.
Hence, If we want to have $k$ odd red points, we have ${n\choose k}$ ways to choose them and $n\choose k$ blue even points.
Hence the total number of ways are $${2n\choose n}={n\choose 0}^2+\dots+{n\choose n}^2. $$
I followed the full solution, except the line I mentioned i.e "Notice that if
two points are in the same circle, between them there must be an even number of
points, and thus the circles join points with even index with points with odd index."
Can someone explain? Also if one knows an alternate solution, please feel free to post!
Best Answer
For each circle put $($ and $)$ symbols on its left and right points respectively. Then within each circle there must lie a string of balanced brackets, since circles can't cross, so there must be an even number of points in each circle.