32
$\begingroup$

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.

Improve this question
$\endgroup$
11
  • $\begingroup$ 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. $\endgroup$
    – Kevan St. John
    Commented Oct 1, 2015 at 20:20
  • $\begingroup$ 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? $\endgroup$
    – tfitzger
    Commented Oct 1, 2015 at 20:40
  • $\begingroup$ @tfitzger you have to show one exists for ANY ordering $\endgroup$
    – kaine
    Commented Oct 1, 2015 at 20:47
  • $\begingroup$ @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. $\endgroup$
    – tfitzger
    Commented Oct 1, 2015 at 20:52
  • 1
    $\begingroup$ Does this theorem help? $\endgroup$
    – S.C.
    Commented Oct 2, 2015 at 8:07

1 Answer 1

Reset to default
16
$\begingroup$

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
Improve this answer
$\endgroup$
7
  • $\begingroup$ Suggested reading: arxiv.org/pdf/0906.3885v3.pdf . This might have fit better on Math.SE $\endgroup$
    – kaine
    Commented Oct 2, 2015 at 13:32
  • $\begingroup$ @kaine: I have added your reference to the text. (Hope that's okay with you.) $\endgroup$
    – Gamow
    Commented Oct 2, 2015 at 14:05
  • 1
    $\begingroup$ Any chance the general proof has a more accessible explanation when limited to 3 colors? $\endgroup$
    – xnor
    Commented Oct 2, 2015 at 21:03
  • 3
    $\begingroup$ @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. $\endgroup$
    – Lopsy
    Commented Oct 3, 2015 at 12:50
  • 1
    $\begingroup$ @Lopsy: I have added your reference to the text; $\endgroup$
    – Gamow
    Commented Oct 3, 2015 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.