Find the smallest integer n for which the following is possible:

Consider a set of positive integers {1,2...n}. Each number is painted with either red or blue paint, but no matter which numbers have which color, you can always find four (not necessarily different) numbers x, y, z and w that are coloured with the same paint and satisfy x+y+z=w.

(In reply to Even smaller answer by Steve Herman)

n=11

assume a coloring can be found that does not allow x,y,z to be found.  wlog 1=red
3=blue (1+1+1)
9=red (3+3+3)
11=blue (9+1+1)

if 2=red then
4=blue (1+1+2)
11=red (3+4+4) -><-
if 2=blue then
6=red (2+2+2)
8=blue (6+1+1)
8=red (3+3+2) -><-


for n=10 here is a coloring that does not allow x,y,z to be found:
1=red
2=red
3=blue
4=blue
5=blue
6=blue
7=blue
8=blue
9=red
10=red

if x,y,z are blue w>=9 and so is red (or does not exist)
if x,y,z are red then either w>10 or w is > 2 and < 7 i.e. blue

Posted by Joel on 2006-12-06 13:40:12