painting

Color each natural number ${\mathbb{N}}^{>1}$ one of two colors. Show that, for each $n\in \mathbb{N}$, there are natural numbers $a,b>n$ such that $a$, $b$, $a+b$ are all the same color.

The exercise claims that given any painting of $\mathbb{N}$ the statement holds. We will continue with a proof by contradiction, first assuming that there is a specific painting of $\mathbb{N}$ where the rest of the statement does not hold

If the rest of the statement doesn't hold, then that means that there is some integer $n\in N$ such that given any $a,b$ greater than $n$, then $a,b,a+b$ are not all the same color $\left(\alpha \right)$.

Before we continue, let's think about how ${\mathbb{N}}^{>n}$ is forced to be painted, for our example, let's consider the two colors being white and black.

Given two numbers $x<y\in {\mathbb{N}}^{>n}$, if they are both black, then we know that $x+y$ must be white, or else we would have a contradiction with $\left(\alpha \right)$. Additionally suppose all numbers between them are white and that $y-x\ge 3$ and , then if that's the case we would also get a contradiction as then $(x+1),(y-1)$ would both be white, forcing $x+1+y-1=x+y$ to be black by $\left(\alpha \right)$, but x + y is either black or white not both, this is a contradiction, so assuming still that all numbers between $x,y$ are white, then we must know that $y-x\le 2$ $\left(\beta \right)$ by that very contradiction

This means given any two $x<y\in {\mathbb{N}}^{>n}$ that are black, if all numbers between the two are white, then $y-x\le 2$ meaning that there is at most one other white number between the two of them. We could also redo the above argument exchanging the words white and black, which would convince you that between any two white numbers, there is at most one black number.

Therefore due to this, we can see that there are 3 possible situations, paintings of ${\mathbb{N}}^{>n}$ either it eventually is all black, all white, or it is alternating white and black. We can see this is true as follows, suppose at some $k\ge n$ we know that $k$ is white $\left(\gamma \right)$

- if for all $l>k$ $l$ is white, then it is eventually all white
- if there is a point at which we can find a black number, then consider $p$ to be the first black number after $k$
- if $p+1$ is also black, then $p+2$ cannot be white because then $k$ and $p+2$ would both be white and $(p+2-k)\ge 3$ which would contradict $\left(\beta \right)$, by iterating this argument we can see the the rest of the numbers would be black or we would get the same contradiction
- if $p+1$ is white, then go back to $\left(\gamma \right)$ and repeat the argument with $k=p+1$

Let $c$ be the point at which it becomes all white, all black, or alternates forever.

If ${\mathbb{N}}^{>c}$ is eventually all white, then we'd have a contradiction since for any $a,b\in {\mathbb{N}}^{>c}$, then $a,b,a+b\in {\mathbb{N}}^{>c}$ are all white, which contradicts $\left(\alpha \right)$, the same argument shows it cannot be all black either.

Suppose that ${\mathbb{N}}^{>c}$ is alternating white and black, then let $a\in {\mathbb{N}}^{>c}$ and let $b=a+4$ be two black numbers. By $\left(\alpha \right)$ we know that a + b cannot be black, so it must be white. But then $a+1,b-1$ are both white, so by $\left(\alpha \right)$ $a+1+b-1=a+b$ must be black, which is a contradiction.