Problem:
Let be distinct points on the unit circle other than . Each point is colored either red or blue, with exactly of them red and of them blue. Let be any ordering of the red points. Let be the nearest blue point to traveling counterclockwise around the circle starting from . Then let be the nearest of the remaining blue points to traveling counterclockwise around the circle from , and so on, until we have labeled all of the blue points . Show that the number of counterclockwise arcs of the form that contain the point is independent of the way we chose the ordering of the red points.
Solution:
(Proposed by Maria Monks Gillespie)
We may assume the points have been labeled as in order, going counterclockwise from . Now, write out the color of each point in order, and replace each with a +1 and each with a -1 , to get a list of +1 's and -1 's. Consider the partial sums of this sequence, and choose the index such that the th partial sum has as small a value as possible; if several partial sums are tied for smallest, let be the lowest index among them. Now, rotate the circle clockwise so that points are moved past ; the resulting sequence of +1 's and -1 's from the new orientation now has all nonnegative partial sums, and the total sum is 0 .
Consider any red point in the rotated diagram and label it . The arc does not cross , for otherwise the sequence ends with a string of +1 's and the partial sums before those +1 's would be negative. Furthermore, the sequence of entries from to looks like , and so removing and is equivalent to removing a consecutive pair of a +1 and -1 , so the partial sums remain all nonnegative. It follows that the next pairing also doesn't cross , and so on, so no matter which way we pick the ordering of the red points in the rotated circle, there are no counterclockwise arcs containing .
Finally, note that in any ordering of the red points, the blue points among are all paired with red points, and those red points among are paired with blue points in this same subsequence since there are no crossings in the rotated picture. Let be the difference between the number of blue and red points among . Then it follows that exactly blue points in were matched with red points from . Therefore, when we rotate the circle back to its original position, there are exactly crossings, no matter which ordering we pick for the red points. Since is independent of the ordering, the proof is complete.
The problems on this page are the property of the MAA's American Mathematics Competitions