# The tough one from "A Brilliant Young Mind" (2014)

Great movie by the way. I'm quoting from memory, so I may get the wording wrong.

The positive integers are each colored Red, Yellow or Green.
Prove that for any such coloring, there must exist three distinct positive integers $a,b,c$ such that the colors of $~a$, $~b$, $~c$, $~a+b$, $~a+c$, $~b+c$, and $~a+b+c~$ are all the same.

The integers must be non-zero, but they do not have to be distinct.

• I want to note I've found a solution for two colours, and set {a,b} where a,b,a+b are the same colour. I made a tree of possible colourings and solved it 5 deep. But I'm not sure if this can be done with the full problem. Based on the movie, the solution may require a reduction to a different but equal problem. Oct 1 '15 at 20:20
• Is there any order to how they are colored: 1=red, 2=yellow, 3=green, 4=red, 5=yellow... or should we assume the potential for random distribution? Oct 1 '15 at 20:40
• @tfitzger you have to show one exists for ANY ordering Oct 1 '15 at 20:47
• @kaine is that even possible, though? I mean, if it is truly a random distribution, the color has no relation to the ordinal position of the number, which means there is no relation between a, b, and a+b in terms of color. Oct 1 '15 at 20:52
• Does this theorem help?
– S.C.
Oct 2 '15 at 8:07

## 1 Answer

The question concerns a special case of "Hindman's theorem":

Hindman's theorem
Suppose that the natural numbers are colored with $r$ different colors. Then there exists a color $c$ and an infinite set $D$ of natural numbers, so that all elements of $D$ are colored with $c$ and so that every finite sum of elements of $D$ also has color $c$.

For solving the puzzle, you just apply Hindman's theorem with $r=3$ colors (red, yellow, green). The theorem gives you an infinite mono-chromatic set $D$, from which you may pick three arbitrary elements $a,b,c$; these three elements have all desired properties.

Additional information:

• A wikipedia article on so-called IP sets and Hindman's theorem
• The article "A Simple Proof and Some Difficult Examples for Hindman's Theorem" by Henry Towsner on the arXive
• Example 3 in the Tricki article "How to use ultrafilters" contains another proof of Hindman's theorem
• Suggested reading: arxiv.org/pdf/0906.3885v3.pdf . This might have fit better on Math.SE Oct 2 '15 at 13:32
• @kaine: I have added your reference to the text. (Hope that's okay with you.) Oct 2 '15 at 14:05
• Any chance the general proof has a more accessible explanation when limited to 3 colors?
– xnor
Oct 2 '15 at 21:03
• @xnor The Tricki article on ultrafilters is more accessible than the arxiv post (at least for me), but it still requires mathematical maturity. tricki.org/article/How_to_use_ultrafilters Background: an ultrafilter is a way of calling some subsets of natural numbers "large" and other subsets "small." Every subset must be either large or small, and given a subset S, exactly one of S or its complement is large. Oct 3 '15 at 12:50
• @Lopsy: I have added your reference to the text; Oct 3 '15 at 13:15