# 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. – Kevan St. John 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? – tfitzger Oct 1 '15 at 20:40
• @tfitzger you have to show one exists for ANY ordering – kaine 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. – tfitzger Oct 1 '15 at 20:52
• Does this theorem help? – S.C. Oct 2 '15 at 8:07

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.