Triangles defined on an infinite Go board by same-colored stones

Solution 1:

Any finite number $n$ will produce a right triangle, in fact an infinite number of them. The secret is that we can strike out lots of rows or columns and still have an infinite board. Given an $n$, pick a row of the board. There is at least one color that has an infinite number of stones in the row, call it red. Now delete all the columns that do not have a red stone in the row we are considering. We still have an infinite board, but the row under consideration has only red stones. If there is a red stone anywhere else on the board it will make an infinite number of red right triangles. Strike out the row under consideration and we have the same problem with $n-1$ colors. We can keep eliminating colors one by one until we get to just one.

Solution 2:

Consider a finite $m\times m$ board where every intersection either has a stone, or does not. If there are at least $2m$ stones on this board, then I claim there will exist three stones which are arranged in an axis-aligned right triangle.

To prove this, number the stones from $1$ to $2m$. For each $1\le k \le 2m$, let $f(k)$ be the number of rows spanned by the stones numbered $1$ to $k$, plus the number of columns spanned by these stones. Note that $f(1)=2$, $f(2m)\le 2m$, and $f(k)$ is a weakly increasing function. It cannot be strictly increasing; if it were strictly increasing, you would have $f(2m)\ge 2m-1+f(1)=2m+1$, contradicting $f(2m)\le 2m$. This means there must be some number $k$ for which $f(k)=f(k-1)$. But this means that stone number $k$ is the same row as a previous stone, and in the same column as a previous stone, so that these three stones form a right triangle.

In particular, if an $m\times m$ board is filled with stones in $n$ colors, then some color will appear on at least $m^2/n$ of the stones, so if $m^2/n\ge 2m$, there will be a right triangle of stones in that color. Therefore, for all $n$, an infinite colored board will have a monochromatic coloring, and to find one, you only need to search in a $2n\times 2n$ sub-square of stones.

This problem seems to fall under the topic of Ramsey theory.

As a side note, you can also prove that an $m\times m$ board with only $2m-1$ stones contains an axis-aligned right triangle. This is tight, since you can place $2m-2$ stones without forming a triangle.

Solution 3:

Call a stone h-unique if no other stone on the same row has the same colour, call it v-unique if no other stone on the same column has the same colour. Clearly, every row contains at most $n-1$ h-unique stones and every column at most $n-1$ v-unique stones. Hence in a rectangle of $n$ rows and $n^2-n+1$ columns, there are at most $n^2-n$ h-unique stones. Hence there is a column of this rectangle that does not have a h-unique stone. One stone in this column is not v-unique. This stone, plus a stone witnessing its non-h-uniqeness, plus a stone witnessing its non-v-uniqueness, form a right triangle of same-colour stones as desired.