For every 17-coloring of N (the naturals- not including 0) there exists x, y, z such that x,y,z are distinct x,y,z that are same color such that 2x+3x-6z = 0It turns out that this is FALSE. We'll call a set b1,...,bn REGULAR if
for every c, for every c-coloring of N, there exists x1,....,xn such that x1,....,xn are all the same color, and b1x1 + ... + bnxn = 0The following is known as (abridged) Rado's Theorem. Rado proved it in 1933.
(b1,...,bn) is regular iff some nonempty subset of the bi's sum to 0.For an exposition of the proof see Ramsey Theory by Graham, Rothchild,and Spencer or see my writeup
NOW- here is a question to which the answer is known, and I'll tell you the answer in my next post.
TRUE OR FALSE:
For every coloring of R (the reals) with a countable number of colors there exists distinct x,y,z,w x,y,z,w same color x+y=z+w.When I asked this in seminar I got
- 5 thought it was TRUE
- 4 thought it was FALSE
- 5 thought it was a STUPID QUESTION.
Did you mean x+y=z+w?
ReplyDeleteThanks for the correction,
ReplyDeleteI have made it.
I think it's true. I'd still guess true if you replaced R with N, and I believe the constants for the first problem were carefully choosen to make the answer false.
ReplyDeleteenjoying your notes so far, Bill...
ReplyDeletesmall typo note: page two, point 3 on your list, I see a j where there should be a k.
guilherme: it couldn't be true for N because you could color each integer a distinct color.
ReplyDeleteBut I agree that my hunch says it's true for R. I reformulate the question as follows: if you partition the reals into countably many subsets, can you always find four of them P1,...,P4 such that there are x1,...,x4 in the P's such that any two of them add up to the other two.
My intuition screams yes. Mind you, my intuition about the reals has been wrong before.
I should actually revise my comment, you should be looking for one partition containing the 4 integers (I read "same color" as "different colors" in the second part of my post).
ReplyDeleteBut I still think it's true for some reason!
Why did those who thought it was a stupid question think it was a stupid question?
ReplyDeleteHummm... I didn't realize the number of colors didn't have to be finite. I'm changing my vote to "a stupid question", which just means "a question I don't really care about".
ReplyDeleteThe reason I don't care about it is that the problem is based on this extremely discontinuous use of the reals, where you can do things like assign each rational number a different color. You can't even color any interval, no matter how small, with the same color!
This would be a "stupid" (i.e. trivial) problem if you had a monochromatic interval of positive length. However, a finite number of colors won't guarantee that either.
ReplyDeleteI would actually guess that it's false, but I have to think about it a bit more.
>You can't even color any interval, no matter how small, with the same color!
ReplyDeleteWell, what would prevent you from doing so.
You can't even color any interval, no matter how small, with the same color!
ReplyDeleteBut the same thing would be true if you considered using only 2 colors for R.
I suppose you can call it a stupid question if you are one of those people who would like to get rid of the axiom of choice, for example.
ReplyDeleteWhat the hell? Aren't you guys sick of coloring already given that everyone has been talking about coloring the graphs this way or that way, that now you have moved to coloring those innocent natural and real numbers? STOP DOING THAT!! All things colored not necessarily look good. At least leave N and R uncolored. Coloring, coloring, coloring, HUH!
ReplyDeleteI believe it's true from measure theory arguments(you need to find 2 pairs which are same distance)
ReplyDeleteIn your first equation you write 2x+3x-6z = 0. One of the x's is probably a y, right?
ReplyDeleteeither yes or no would be a boring answer...
ReplyDeleteI'm gonna go with it's equivalent to the negation of the Axiom of Choice. Or something.
If all color classes are measurable, then one of them must have positive measure, and so there has to be an interval within which that color class has density, say, 99%. Say that, after scaling, the interval is [0,1], then pick at random x in [0,1/4], w in [1/4,1/2] and epsilon in [0,1/2], and set z=x+epsilon and y = w+epsilon. Then by the union bound there is at least a 88% probability (or something like that) that all four points have the same color, and by construction x-z=w-y.
ReplyDeleteSo if the answer is that a coloring exists, its definition must use the axiom of choice, because otherwise you can't construct non-measurable sets. (Under the proper assumptions, like ZF plus some cardinal assumption is consistent.)