El País' weekly challenge

For a while now, the Spanish newspaper “El País” has been posing a weekly mathematical challenge to promote a collection of books, and celebrate a hundred years of their country’s Royal Mathematical Society.

The latest of these challenges—the fourth—is a beautiful problem in combinatorics:

Consider a clock, with its twelve numbers around a circle: \( 1, 2, \dotsc, 12.\) Color each of the twelve numbers in either blue or red, in such a way that there are exactly six in red, and six in blue. Proof that, independently of the order chosen to color the numbers, there always exists a line that divides the circle in two perfect halves, and on each half there will be exactly three numbers in red, and three numbers in blue.

While there are many different ways to solve this challenge, I would like to propose here one that is solely based upon purely counting techniques.

The first step is “coding” the clock: To every situation, we assign a new clock where each number has been substituted with plus and minus ones: \( +1 \) instead of a blue number, and a \( -1 \) instead of any red number.

Notice that, if you add all the plus and minus ones in the second clock, you obtain zero: this is of course, due to the fact that there are as many blue as red numbers.

Consider any line that divides the circle in two equal halves: let \( M \) be the sum of plus and minus ones of one of the halves. The previous property tells us that the sum of plus and minus ones of the other half must be precisely \( -M \).

For example, in the clock above, consider the two halves containing the hours 1 through 6, and 7 through 12. The sum of plus and minus ones for the former is \( -1-1+1-1+1-1=-4+2=-2, \) and hence it will be \( +2 \) for the latter. Note that, no matter the half chosen, the sums \( M \) of plus and minus ones for this particular example are always going to be even numbers.

To solve our problem, all we have to do is prove that there exists a line that divides the clock in such a way that the sums of plus and minus ones of both halves is precisely zero. How are we going to prove it?

Assume we choose a given half, and the value of the sum of its plus and minus ones is not zero. Now, rotate that line one hour clockwise. The sum of ones and minus ones of the new halves change, but the way they change is by not too much. If the sum of ones and minus ones of the previous half was \( M \), then the sum of ones and minus ones of the new half can only be:

\( M+2 \) in case we lose a red \( (-1) \) and gain a blue \( (+1) \)
\( M \) in case we lose and gain the same color.
\( M-2 \) in case we lose a blue \( (+1) \) and gain a red \( (-1) \)

Another important fact derived of this property is that, no matter how we half the clock, the parity of the sum of plus and minus ones for each half is always the same (that is, they are all even, or they are all odd).

Notice what happened: We started picking a half of the clock. The sum of plus and minus ones for that half was some value \( M \). If this value is zero, then we are done. But if not, by rotating the line clockwise six times, we go from \( M \) to \( -M \) by adding or subtracting \( 2 \) (or keeping the same value). We have to cross the zero at some point!

And this is the punch-line: all we need to prove now is that, no matter the arrangement of colors for the numbers in any clock, and no matter how we half them, the sum of the corresponding plus and minus ones of each half is always even. This guarantees us that, when we cross zero, we do it so by actually finding a line with the required properties. How would you prove this fact?

I encourage you to also find other ways to solve this challenge. Feel free to use big theorems from Combinatorics, code the clock as a graph and use techniques of that field… anything goes.