16
$\begingroup$

Take the positive integers {1, 2, 3, ...} and color them red, green or blue. Is it true that no matter what coloring is chosen, we can always find three distinct numbers x, y and z so that x, y, z and x+y+z are all the same color?

This puzzle was inspired by: How do we find the numbers?

Improve this question
$\endgroup$
13
  • 7
    $\begingroup$ This puzzle implies the answer is yes, though the weaker condition here might allow a nicer and more accessible argument. $\endgroup$
    – xnor
    Commented May 22 at 8:26
  • 4
    $\begingroup$ With computer programs, I found that {1, ..., 93} allows a quad-free coloring but {1, ..., 94} doesn't. Doesn't feel like a useful insight though. $\endgroup$
    – Bubbler
    Commented May 22 at 9:07
  • 1
    $\begingroup$ @xnor I saw that puzzle after I posted my question and I debated whether I should delete my question or not. I decided to keep my question because I am hoping my weaker constraint can lead to an elegant solution. $\endgroup$
    – Will.Octagon.Gibson
    Commented May 22 at 9:38
  • 2
    $\begingroup$ @Moti The phrase, “no matter what coloring is chosen ...” is meant to include all possible colorings including all random colorings. $\endgroup$
    – Will.Octagon.Gibson
    Commented May 24 at 20:41
  • 1
    $\begingroup$ @Bubbler generalizing it into {1, ..., N} and K colours might be a better insight. $\endgroup$
    – Ver Nick
    Commented May 29 at 17:00

1 Answer 1

Reset to default
8
$\begingroup$

Does a solution exist?

Yes.

Proof:

Label the vertices of a graph from $0$ to $n$. Between every pair of vertices $x<y$, draw an edge with the color of $2^y-2^x$. By Ramsey's theorem, for large enough $n$, there exist vertices $w<x<y<z$ such that the edges between every pair have the same color. Then $2^x-2^w$, $2^y-2^x$, and $2^z-2^y$ are distinct and have the same color as their sum $2^z-2^w$.

This solution was inspired by this one.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Nice answer. It's fun to note that you have a (very loose) bound of $2^{236}$. $\endgroup$
    – Benjamin Wang
    Commented Aug 24 at 22:48
  • $\begingroup$ @BenjaminWang If we use the Ramsey number for 4-cycles this improves to $2^{10}$(!) (not a factorial) $\endgroup$
    – noedne
    Commented Aug 24 at 22:52
  • 1
    $\begingroup$ What is the justification for using the powers of 2? Is it sufficient to use any sequence for which all differences between two elements are distinct? $\endgroup$
    – AxiomaticSystem
    Commented Aug 25 at 20:24
  • 1
    $\begingroup$ @AxiomaticSystem That's correct, only distinctness is necessary. $\endgroup$
    – noedne
    Commented Aug 26 at 21:00
  • 1
    $\begingroup$ The construction does not consider cycles that visit the vertices in a "wrong" order, such as w->y->x->z or w->x->z->y, so I think $R(C_4, C_4, C_4)$ is not the right number to use. $\endgroup$
    – Bubbler
    Commented Aug 28 at 0:38

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.