2005 OIM Problems/Problem 6

Problem

Given a positive integer , points are aligned in a plane as . Each point is colored blue or red using the following procedure: In the plane, circles with end diameters and are drawn, disjoint two by two. Each , , belongs to exactly one circle. The dots are colored so that the two points of the same circle have the same color. Find how many different colorations of the points can be obtained by varying the circumferences and the distribution of colors.

~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Solution

{{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.

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 contra- dicts our hypothesis. Notice that the arrangement of the circles that gives a coloring does not need to be unique. For example, if all points are red, any arrangement of circles can give that coloring.

If we want to have k odd red points, we have (2) ways to choose them, and (2) ways to choose the even red points. Thus the total number of colorings is \binom{n}{0}^{2}+ \binom{n}{1}^{2}+\binom{n}{2}^{2}+\cdot\cdot\cdot+\binom{n}{n}^{2}=\binom{2n}{n}}}

See also

OIM Problems and Solutions