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.

relojes

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?

masrelojes

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.


You can subscribe to El País on your Kindle through Amazon:

El País Kindle 3G, Free 3G + Wi-Fi, 3G Works Globally, Graphite, 6″ Display with New E Ink Pearl Technology – includes Special Offers & Sponsored Screensavers
Advertisements
  1. Raymond Rogers
    April 28, 2011 at 11:25 am

    Excellent problem and solution.

    It seems to me that your solution is an application of the discrete Ham Sandwich Theorem. The more abstract problem, involving more than two colors and Y or X or… divisors, dumps one back into specialized group theory analysis; permutations with a strict set of constraints and all possible sets satisfying those constraints.

    I think it’s interesting that the Ham Sandwich Theorem can provide answers to questions in group theory 🙂

    Ray

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: