# British Maths Olympiad (BMO) 2004 Round 1 Question 3 Proof with pigeon hole principle?

The question states:

Determine the least natural number $n$ for which the following result holds:

No matter how the elements of the set ${1, 2,... ,n}$ are coloured red or blue, there are integers $x,y,z,w$ in the set (not necessarily distinct) of the same colour such that $x + y + z = w.$

I believe $11$ is the smallest such $n$ and my general idea for the proof is to show counterexamples from $n = 1$ to $10$ (which are relatively easy to find) and then show no partitioning of the $11$ elements violates the condition stated above.

I am thinking something along the lines of:

Suppose the $11$ numbers are separated into red and blue sets and that w.l.o.g there are $11-k$ elements in the red set and $k$ elements in the blue set.

Then we must show that that $x + y + z = w$ is true in either the red or the blue set.

Case 1

Suppose that the condition is not true in the red set, then we have that the triples from the $k$ elements can produce $k^3$ numbers (not necessarily distinct).

Is there a way to use the pigeon hole principle to make an argument that some number in the set must be the same as one of the $k^3$ possibilities?

If there is. I imagine I can use similar reasoning to make an argument for the second case and complete the proof. As always points on how to approach problems like these are also welcome and appreciated!

without loss of generality $1$ is red, we prove if $n\geq 11$ there is a problem:

Case $1$:

$1$ is red and $2$ is red. We conclude $3,4,5,6$ are blue. We conclude $9,10,11$ are red. A contradiction as $1+1+9=11$ and all are red.

Case $2$:

$1$ is red and $2$ is blue. We conclude $3$ is blue. We conclude $6,7,8$ are red, this is a contradiction as $1+1+6=8$ and all are red.

We now give a coloring for $1,2,3,4,5,6,7,8,9,10$ that works:

Color $1,2,9,10$ red and the rest blue. Clearly if we add three red colors we cannot get $9$ or $10$. On the other hand if we add three blue colors we get at least $9$ and all blue colors are less than $9$.

Hence the answer is $11$ as suspected.

• Thanks for this answer, do you know if the approach I have outlined can be completed? – Abe May 3 '18 at 17:30