IMO 1990 · Problem 2

Let \(n \geq 3\) and consider a set \(E\) of \(2n - 1\) distinct points on a circle. Suppose that exactly \(k\) of these points are to be colored black. Such a coloring is “good” if there is at least one pair of black points such that the interior of one of the arcs between them contains exactly \(n\) points from \(E\). Find the smallest value of \(k\) so that every such coloring of \(k\) points of \(E\) is good.

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{ k_{\min}= \begin{cases} n-1,& n\equiv 2\pmod 3,\\ n,& n\not\equiv 2\pmod 3. \end{cases}} \]

Solution

Put \(N=2n-1\), and label the points \(P_0,P_1,\ldots,P_{N-1}\) in clockwise order, with all subscripts interpreted modulo \(N\).

The clockwise arc from \(P_i\) to \(P_{i+n+1}\) contains exactly the \(n\) points \[ P_{i+1},P_{i+2},\ldots,P_{i+n} \] in its interior. Conversely, any arc containing exactly \(n\) points in its interior has endpoints of this form, when read clockwise. Thus a coloring is not good precisely when no pair \[ P_i,\ P_{i+n+1} \] consists of two black points.

Consider the permutation \[ T(P_i)=P_{i+n+1}. \] Let \[ d=\gcd(N,n+1),\qquad L=\frac{N}{d}. \] Starting at any point, repeated application of \(T\) returns to that point after exactly \(L\) steps. Indeed, \[ T^t(P_i)=P_i \quad\Longleftrightarrow\quad N\mid t(n+1) \quad\Longleftrightarrow\quad L\mid t, \] where the last equivalence follows from \[ \gcd\left(\frac{N}{d},\frac{n+1}{d}\right)=1. \] Consequently, \(T\) partitions the \(N\) points into \(d\) disjoint cycles, each of length \(L\). Since \(N\) is odd and \(0<n+1<N\), the number \(L\) is odd and at least \(3\).

The pairs that make a coloring good are exactly the consecutive pairs in these cycles, including each cycle’s last and first points. We therefore determine how many black points a cycle can contain without two consecutive points being black.

If a cycle contains \(b\) black points and no two are consecutive, the successor of each black point must be white. These successors are distinct, so \[ b\leq L-b. \] As \(L\) is odd, this gives \[ b\leq \frac{L-1}{2}. \] This bound is attained: writing the cycle in order as \(Q_0,Q_1,\ldots,Q_{L-1}\), color exactly \[ Q_0,Q_2,\ldots,Q_{L-3} \] black. No two of these points are consecutive, including across the end of the cycle.

Applying this construction independently to all \(d\) cycles shows that the maximum possible number of black points in a coloring that is not good is \[ d\frac{L-1}{2}=\frac{N-d}{2}. \] Any smaller number is also possible by changing some of these black points to white. Hence the required minimum is \[ k_{\min}=\frac{N-d}{2}+1. \]

Finally, \[ d=\gcd(2n-1,n+1) =\gcd\bigl(2(n+1)-(2n-1),n+1\bigr) =\gcd(3,n+1). \] Thus \(d=3\) when \(n\equiv2\pmod3\), and \(d=1\) otherwise. Substituting \(N=2n-1\) gives the stated answer.

The solution was checked against John Scholes' IMO solution archive (Kalva).