Can you paint with all the colors of the integers?

I first encountered a variation of this problem while watching the film x+y, a drama about a boy participating in the International Mathematics Olympiad.

Suppose I paint the natural number 1,2,3,… red or blue, each number being painted exactly one color. Do you think you can always find two numbers a and b such that a, b, and a+b are all the same color, i.e. the triple (a,b,a+b) is monochromatic?

The answer is yes. In fact, if you are allowed to have a=b, then even in the worst case scenario you can find a solution without venturing past the number 5. This can be solved backwards: Assume 1 is red, then  in a worst case scenario 2 will be blue (otherwise you would have a=b=1 are red and so is a+b=2). By similar reasoning in the worst case scenario 4 is red, and thus 3 is blue (if 3 were red then we have 1, 3, and 4 are red). Now 5 is either blue or red but either way we have that (1, 4, 5) or (2, 3, 5) are monochromatic. So without even looking at the coloring of the numbers, we are sure to be able to find our monochromatic triple (a,b,a+b). If you aren’t allowed to have a=b, it’s a little more difficult but you can still do it. The worst case would look something like 1 Red, 2 Red, 3 Blue, 4 Red, 5 Blue, 6 Blue, 7 Blue, 8 Red, and regardless of what color 9 is, you’ll have your triple.

Now, what would happen if I were allowed to use more colors to paint? Suppose I can use 3, or 10, or even a million colors. Could I ever come up with a coloring of the natural numbers so that you won’t be able to find a monochromatic triple (a,b,a+b)? Obviously the technique above becomes much more laborious as at every step my repertoire of colors is rather large. Is there some number of colors that I can use though to make an impossible coloring, one in which you will not be able to find your monochromatic triple?

What if I further challenge you to look not for a triple (a,b,a+b) but instead for a 7-tuple (a,b,c,a+b,a+c,b+c,a+b+c) that is monochromatic? Or a 15-tuple (a,b,c,d, a+b,a+c,a+d,b+c,b+d,c+d,a+b+c,a+b+d,a+c+d,b+c+d,a+b+c+d)? Or worse, asking you to find an infinite set of natural numbers such that the sum of every finite subset is the same color. Are you feeling deterred by this Herculean task?

Fear not! For Hindman’s Theorem guarantees that regardless of how many colors I use, subject to it being finite of course, you can always do it. That’s right, even if I used a googolplex of colors, you can find an infinitely large set A of natural numbers such that ever finite subset S\subset A will have a sum \sum_{s\in S} s of the same color.

Note, we are not requiring that this set you find be closed under finite addition of repeated elements, i.e. if x is one color, we do not require x+x is to be the same color. This would actually be impossible even with just two colors as demonstrated by the coloring:

Red: 1
Blue: 2 3
Red: 4 5 6 7
Blue: 8 9 10 11 12 13 14 15
Red: 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 …

Here, by creating lists that double in length and alternating between coloring the lists red and blue, every x and x+x are colored differently.

For more details I recommend taking a look at Baumgartner’s short proof of Hindman’s theorem, and also checking out the film x+y when you get a chance!

References:
0) https://arxiv.org/abs/0906.3885
1) http://math.stackexchange.com/questions/789443/hindmans-theorem-on-coloring-a-set-with-n-colours
2) https://terrytao.wordpress.com/2008/01/21/254a-lecture-5-other-topological-recurrence-results/

Advertisements

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