29

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.

Doorknob
  • 4,657
  • 5
  • 35
  • 50
Kevan St. John
  • 451
  • 4
  • 7
  • 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 01 '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 01 '15 at 20:40
  • @tfitzger you have to show one exists for ANY ordering – kaine Oct 01 '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 01 '15 at 20:52
  • @tfitzger, hence why it is a puzzle. It seems possible it might work but it is not easy. Can you show there is a configuration that doesn't work? – kaine Oct 01 '15 at 21:00
  • Reminds me of Coloring the reals – Rob Watts Oct 01 '15 at 21:00
  • I can get everything except for $a+c$ to be the same color... this is tricky. – Lopsy Oct 01 '15 at 22:50
  • @Lopsy, If that's true I can prove that that occurs infinitely many times. Does that help? ;p – Ben Frankel Oct 02 '15 at 01:10
  • 1
    Does this theorem help? – S.C. Oct 02 '15 at 08:07
  • @SeraphCheng That theorem looks like an immediate solution for the degenerate case $a=b=c$, where the 7 possibilities reduces to just $a, 2a, 3a$. – Lawrence Oct 03 '15 at 06:44

1 Answers1

10

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
Gamow
  • 45,573
  • 10
  • 147
  • 381
  • Suggested reading: http://arxiv.org/pdf/0906.3885v3.pdf . This might have fit better on Math.SE – kaine Oct 02 '15 at 13:32
  • @kaine: I have added your reference to the text. (Hope that's okay with you.) – Gamow Oct 02 '15 at 14:05
  • 1
    Any chance the general proof has a more accessible explanation when limited to 3 colors? – xnor Oct 02 '15 at 21:03
  • 3
    @xnor The Tricki article on ultrafilters is more accessible than the arxiv post (at least for me), but it still requires mathematical maturity. http://www.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. – Lopsy Oct 03 '15 at 12:50
  • 1
    @Lopsy: I have added your reference to the text; – Gamow Oct 03 '15 at 13:15