26
$\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.

$\endgroup$
  • $\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 Oct 1 '15 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 Oct 1 '15 at 20:40
  • $\begingroup$ @tfitzger you have to show one exists for ANY ordering $\endgroup$ – kaine Oct 1 '15 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 Oct 1 '15 at 20:52
  • 1
    $\begingroup$ Does this theorem help? $\endgroup$ – S.C. Oct 2 '15 at 8:07
10
$\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
$\endgroup$
  • $\begingroup$ Suggested reading: arxiv.org/pdf/0906.3885v3.pdf . This might have fit better on Math.SE $\endgroup$ – kaine Oct 2 '15 at 13:32
  • $\begingroup$ @kaine: I have added your reference to the text. (Hope that's okay with you.) $\endgroup$ – Gamow Oct 2 '15 at 14:05
  • 1
    $\begingroup$ Any chance the general proof has a more accessible explanation when limited to 3 colors? $\endgroup$ – xnor Oct 2 '15 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 Oct 3 '15 at 12:50
  • 1
    $\begingroup$ @Lopsy: I have added your reference to the text; $\endgroup$ – Gamow Oct 3 '15 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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