Sayan Condition

Assume that there exists a coloring for $n = 11$ s.t. the condition does not hold.

WLOG, color $1$ red. $1+1+1=3$ must then be colored blue. $3+3+3=9$ is red, and $1+1+9=11$ is blue.

Assume $2$ is red. $1+1+2=4$ through $2+2+2=6$ must be colored blue. $3+4+4=11$ must be colored red, but since we already stated it must be colored blue, this is a contradiction. Therefore, $2$ is blue.

$2+2+2=6$ through $2+3+3=8$ are red, and $1+1+6=8$ is colored blue.. However, since $8$ was determined to be colored red, this is a contradiction, and therefore, it is impossible to create a coloring for $n=11$ s.t. the condition does not hold.

This only provides an upper bound. We still must show that there is a coloring for $n=10$ s.t. the condition does not hold. There are multiple colorings that work, for example: RRBBBBBBRR

Since a coloring that does not satisfy the condition exists for $n=10$ , a lower bound can be set for $n=11$ . Since the lower bound is now equal to the upper bound, the answer is shown to be $11$ .

If $n=10$ , the set of the first 10 positive integers can be colored in red or blue as follows: $1,2,9,10$ are colored red; $3,4,5,6,7,8$ are colored blue.

If $n\ge11$ , assume that the elements of the set of the first $n$ positive integers are colored in red or blue, there are (not necessarily distinct) integers $x,y,z,$ and $w$ in a set of the same color such that $x+y+z=w$ .

Without loss of generality, assume that: $1$ is colored red.

Since $1+1+1=3 \Rightarrow 3$ is colored blue.

Since $3+3+3=9 \Rightarrow 9$ is colored red.

Since $1+1+9=11 \Rightarrow 11$ is colored blue. $(1)$

Since $1+1+7=9 \Rightarrow 7$ is colored blue.

Since $2+2+3=7 \Rightarrow 2$ is colored red.

Since $1+1+2=4 \Rightarrow 4$ is colored blue.

Since $3+4+4=11 \Rightarrow 11$ is colored red. $(2)$

From $(1)$ and $(2)$ , wa have a contradiction. So the minimum value of $n$ is $11$ .

Here, we start with the blank integers, without having given them any colours. Then we fit in colours while trying to avoid having the condition hold (that of having $x, y, z$ and $x+y+z$ all being the same colour) - think of each number being a slot for putting in either Red or Blue. We keep going until we can't fit in any more colours without having a match for the condition - then we have to go back and check what maximum size we reached. A few intermediate patterns are shown along the way.

Starting off at 1 seems a good idea. It doesn't matter which colour it is, so we choose Red. If 1 is Red, then 3 can't be Red too - otherwise, we could have $(x=y=z=1, w=3)$ , and this satisfies the condition we're trying to avoid. Therefore, 3 must be Blue. Similarly, 9 must be Red, or we could have $(x=y=z=3, w=9)$ .

$Red-Blue- - - - - Red -...$

If 9 and 1 are both Red, then 7 can't be Red too, or we could have $(x=y=1, z=7, w=9)$ . 7 is therefore Blue. $(x=y=2, z=3, w=7)$ makes another group, which means 2 must be Red, since 3 and 7 are already both Blue. Now that 2 is Red, 6 must be Blue, or we could have $(x=y=z=2, w=6)$ . We could also have $(x=y=1, z=2, w=4)$ or $(x=1, y=z=2, w=5)$ , so 4 and 5 must be Blue as well.

$Red\, Red\, Blue\, Blue\, Blue\, Blue\, Blue- Red-...$

We now look at number 10 - it could be made from $3+3+4$ , all of which are Blue. So, 10 has to be Red. 10 can also be made up of $1+1+8$ . This means we can't make 8 Red, or they'll make a match, so 8 must be Blue.

$Red\, Red\, Blue\, Blue\, Blue\, Blue\, Blue\, Blue\, Red\, Red-...$

You can convince yourself that there are no matches in this colouring for $x, y, z$ and $w$ ; because we also worked out this colouring through the only logical possibilities, this is the only one that would fit (unless we swapped every Red for Blue and vice versa). If we add in number 11 though, we have to make a match and break the setup. 11 could be made from $1+1+9$ , which are all Red, or $3+4+4$ , which are all Blue. So, whatever colour we put in at 11, there will be a way of picking $x, y$ and $z$ . We can't rearrange the pattern either because we worked it out as the only possible arrangement that works. Therefore, we can give a colouring with no matches for $n = 10$ , but have shown it is impossible for $n \geq 11$ . For this $n$ , there must be a way to choose $x, y$ and $z$ no matter how it is coloured, which is what the question has asked for - 11 is then the answer.

We want to find the minimum n. Consider the colouring (red,red,blue,blue,blue,blue,blue,blue,red,red) for 10 numbers. It is not possible to find four numbers w,x,y,z. Therefore n>=11. Assume for n=11 there is a way to color all the numbers such that no four numbers w,x,y,z can be found. Clearly 1 and 3 must be of different color, assume 1 is red and 3 is blue. If 2 is blue, then all numbers from (2+2+2=6) to (3+3+3=9) must be red, but this is not possible since (6+1+1=8) are all red. If 2 is red, then we need to have all numbers from (1+1+1=3) to (2+2+2=6) all blue. Therefore all numbers from (3+3+3=9) to (4+4+3=11) must be red, but (9+1+1=11) are all red. This contradiction gives us n<=11. Hence, minimum n is 11.

Main idea : Kind of brute force actually. Also considering that I've made a similar problem ( actual wording, Proposal 2 ) before...

Complete proof :

Define a hit as the existence of positive integers $x,y,z,w$ , all colored the same, such that $x+y+z=w$ .

First, observe that we can avoid a hit with $n = 10$ : RRBBBBBBRR. Thus $n > 10$ . We now prove that $n = 11$ guarantees a hit. We will do this by assuming otherwise (there is no hit) and deriving a contradiction.

WLOG we color $1$ with red, so $3 = 1+1+1$ must be blue.

Suppose $2$ is blue, then $6 = 2+2+2, 8 = 2+3+3$ must be red. But then $1,1,6,8$ is a hit. So $2$ is red.

Since $1,2$ are red, then $4 = 1+1+2$ is blue. Since $3,4$ are blue, then $9 = 3+3+3, 11 = 3+4+4$ are red. But then $1,1,9,11$ is a hit.

So we have proven that for $n = 11$ , there must be a hit, thus the answer is $\boxed{11}$ .

Motivation : I've been exposed to too much coloring integers problems that my first instinct is immediately to brute force it.

Generalization : There are a lot of coloring integers problems (color as many integers as possible such that a set of conditions holds). In all of those I've encountered, I keep managing to bash everything by bruteforcing. I wonder whether a variant exists that involves more than just bruteforcing...

We claim that $n=11$ is minimal.

First, we show that $n=11$ satisfies the condition. Consider two cases, one where $1$ and $2$ are colored the same, and two where they are colored differently.

Case 1: WLOG, say $1$ and $2$ are both colored red. Then, $3=1+1+1$ and $4=1+1+2$ must both be colored blue. Since $3$ is blue, $9=3+3+3$ must be red. Now, $11=1+1+9=3+4+4$ , so a quadruple will be formed no matter how 11 is colored. Hence, with $11$ integers such that $1$ and $2$ are colored the same, the condition holds.

Case 2: WLOG, say $1$ is colored red and $2$ is colored blue. Then, $3=1+1+1$ must be colored blue, and $7=2+2+3$ must be colored red. Now, $9=3+3+3=1+1+7$ , which implies that a quadruple will be formed no matter how $9$ is colored. Thus, $9$ integers is sufficient for the condition to hold if $1$ and $2$ are colored differently.

Therefore, $n=11$ satisfies the condition. Also, $n=10$ doesn't satisfy the condition, as the coloring $R,R,B,B,B,B,B,B,R,R$ does not satisfy the condition, so the answer is $\boxed{11}$ .

Assume 1 is red. Let's use italics for red and bold for blue , Then 3 must be blue ( 1 + 1 + 1 = 3 ). 2 may be either colour so we will in the first instance assume it is red and attempt to maximise n .

2 is red :
4, 5, 6 must all be blue ( 1 + 1 + 2 , 1 + 2 + 2 , 2 + 2 + 2 )
9 must be red ( 3 + 3 + 3 ) as must 10 ( 3 + 3 + 4 ).
So 7 must be blue (since if not 7 + 1 + 1 = 9 ) as must 8 ( 7 + 1 + 2 ).
11 must be blue ( 1 + 1 + 9 ).
Now 12 can be made wholly in either red ( 1 + 2 + 9 ) or blue ( 4 + 4 + 4 ).
So if 2 is red n =11.

2 is blue
6 must be red ( 2 + 2 + 2 )
Now 9 can be summed in either colour ( 6 + 1 + 1 ) or ( 3 + 3 + 3 ) so 2 is red gives a higher value of n .

Hence n is 11.

We have to find the maximum no were this condition wont be satisfied. set 1: 1 4 5 set 2: 2 3 5 is the maximum.

similarly the other combinations are 1 2 7 3 4 5 6 8

1 2 9 10 3 4 5 6 7 8

1 6 7 2 3 4 5

1 4 5 2 3 5

Hence the max possible is 10. So the minimum possible value to satisfy this is 11