We take all of the positive integers that are greater than 100 and color them black or white. Prove that no matter what the coloring is, we can always find two distinct numbers a and b so that a, b, and a+b are all the same color.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ You don't get to choose the colouring so that is also a very wrong answer. The point is that you should not need to, but why? @humn $\endgroup$– NijFeb 19 at 2:59
-
1$\begingroup$ Did you mean to say "Prove that whatever coloring is chosen, we can always find two distinct numbers a and b so that a, b, and a+b are all the same color."? Because the problem as written is trivial. $\endgroup$– A. I. BreveleriFeb 21 at 7:38
-
$\begingroup$ @A.I.Breveleri, yes. And the way it is written, it actually isn't trivial. $\endgroup$– NielIGuessFeb 22 at 23:12
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
First I'll ignore the requirement that the numbers are greater than 100, and show that the positive integers cannot be coloured black/white without creating a monochrome additive triplet.
Without loss of generality, we can assume the number 1 is white.
The numbers (5,10,15) cannot all be black, so at least one of them is white. Let k be one such white number.
Clearly k-1 and k+1 must be black to avoid white triplets (1,k-1,k) and (1,k,k+1).
Number 2 must be white to avoid black triplet (2,k-1,k+1).
Number k+2 must be black to avoid white triplet (2,k,k+2).
Number 3 must be black to avoid white triplet (1,2,3).
We now have black triplet (3,k-1,k+2).
Note that 3 and k-1 are distinct because k is at least 5.
To accommodate the requirement that the numbers are greater than 100
the same argument can be used but with everything multiplied by 101.
answered Feb 18 at 17:47
$\begingroup$
$\endgroup$
We'll prove the assertion that there are distinct a,b,a+b of the same colour.
Obvious Fact: If there is a threshold above which all numbers are the same colour the assertion is true.
So let's instead make the
Assumption: There are arbitrarily large numbers of either colour.
Using the assumption find k<l<m of colour x such that l>2k and m>2l. Then if any of the (distinct) numbers l-k,m-l,m-k is colour x we are done. Otherwise they are all colour y and we are done, also.
$\begingroup$
$\endgroup$
Proof by contradiction: assume there are no such pairs.
We can easily see that there must be infinitely many numbers of both colors, e.g. if there were only finitely many black numbers then any two numbers greater than the largest black number would both be white, as well as their sum.
Let a, b, c be three distinct numbers of the same color. Without loss of generality, let them be black. We'll add/subtract pairs of numbers of the same color to get new numbers that must be the opposite color to satisfy our assumption.
a + b : white
b + c : white
(a + b) + (b + c) = a + 2b + c : black
(a + 2b + c) - c = a + 2b : white
(a + 2b + c) - a = 2b + c : white
(a + 2b) + (2b + c) = a + 4b + c : black
(a + 4b + c) - (a + 2b + c) = 2b : white
Since there's nothing special about b (we can always find two other numbers of the same color as any given number) this means that for any number x, 2x must be the opposite color. So 4b must also be black.
4b - b = 3b : white
But now we have a contradiction: b and 4b are both black, while 2b and 3b are both white. So b + 4b = 2b + 3b = 5b must be both black and white, which is impossible.
