Take n ≥ 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.
Solution
Answer: n for n = 0 or 1 (mod 3), n - 1 for n = 2 (mod 3).
Label the points 1 to 2n - 1. Two points have exactly n points between them if their difference (mod 2n - 1) is n - 2 or n + 1. We consider separately the three cases n = 3m, 3m + 1 and 3m + 2.
Let n = 3m. First, we exhibit a bad coloring with n - 1 black points. Take the black points to be 1, 4, 7, ... , 6m - 2 (2m points) and 2, 5, 8, ... , 3m - 4 (m - 1 points). It is easy to check that this is bad. The two points which could pair with r to give n points between are r + 3m - 2 and r + 3m + 1. Considering the first of these, 1, 4, 7, ... , 6m - 2 would pair with 3m - 1, 3m + 2, 3m + 5, ... , 6m - 1, 3, 6, ... , 3m - 6, none of which are black. Considering the second, they would pair with 3m + 2, 3m + 5, ... , 6m - 1, 3, ... , 3m - 3, none of which are black. Similarly, 2, 5, 8, ... , 3m - 4 would pair with 3m, 3m + 3, ... , 6m - 3, none of which are black. So the set is bad.
Now if we start with 1 and keep adding 3m - 2, reducing by 6m - 1 when necessary to keep the result in the range 1, ... , 6m - 1, we eventually get back to 1: 1, 3m - 1, 6m - 3, 3m - 4, 6m - 6, ... , 2, 3m, 6m - 2, 3m - 3, 6m - 5, ... , 3, 3m + 1, 6m - 1, ... , 4, 3m + 2, 1. The sequence includes all 6m - 1 numbers. Moreover a bad coloring cannot have any two consecutive numbers colored black. But this means that at most n - 1 out of the 2n - 1 numbers in the sequence can be black. This establishes the result for n = 3m.
Take n = 3m + 1. A bad coloring with n - 1 black points has the following black points: 1, 4, 7, ... , 3m - 2 (m points) and 2, 5, 8, ... , 6m - 1 (2m points). As before we add n - 2 repeatedly starting with 1 to get: 1, 3m, 6m - 1, 3m - 3, 6m - 4, ... , 3, 3m + 2, 6m + 1, 3m - 1, ... , 2, 3m + 1, 6m, 3m - 2, ... , 1. No two consecutive numbers can be black in a bad set, so a bad set can have at most n - 1 points.
Finally, take n = 3m + 2. A bad coloring with n - 2 points is 1, 2, ... , n - 2. This time when we add n - 2 = 3m repeatedly starting with 1, we get back to 1 after including only one-third of the numbers: 1, 3m + 1, 6m + 1, 3m - 2, ... , 4, 3m + 4, 1. The usual argument shows that at most m of these 2m + 1 numbers can be colored black in a bad set. Similarly, we may add 3m repeatedly starting with 2 to get another 2m + 1 numbers: 2, 3m + 2, 6m + 2, 3m - 1, ... , 3m + 5, 2. At most m of these can be black in a bad set. Similarly at most m of the 2m + 1 numbers: 3, 3m + 3, 6m + 3, 3m, ... , 3m + 6, 3 can be black. So in total at most 3m = n - 2 can be black in a bad set.
Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
12 Nov 1998