isosceles right-angled triangles defined on an infinite Go board by same-colored stones

139 Views Asked by At

You start with an infinite Go board. On every point of the board you place one colored stone. There are n>1 different colors. Find all natural numbers n that no matter how the stones colored, three stones of the same color form the vertices of a isosceles right-angled triangle. The catheti (legs) of the isosceles right-angled triangles must me be on the lines of the board.

This question is already answered for right-angled triangles.

1

There are 1 best solutions below

10
On

I will sketch an elementary argument for $n=2,3$ and let you extend it to the general case.
In the following lines, for brevity, triangle stands for a set of the $\{(a,b),(a,b+c),(a+c,b+c)\}$ kind with $a,b\in\mathbb{Z}$ and $c\in\mathbb{N}^+$.


$n=2$. Let us consider the points $(x,x)$ together with their colors: by the Van Der Waerden theorem we may assume that $$ (0,0),(d,d),(2d,2d)$$ all have the same color (i.e. we have a monochromatic $3$-AP), say white. If one of the points $$(0,d),(d,2d)$$ is white we are done, hence we may assume they are black. In such a case the point $(0,2d)$ completes a monochromatic triangle no matter what.


$n=3$. Let us consider the points $(x;x)$ together with their colors: by the Van Der Waerden theorem we may assume that $$ (0,0),(d,d),(2d,2d),\ldots,(Nd,Nd)$$ all have the same color (i.e. we have a monochromatic $(N+1)$-AP), say red. If one of the points $$(0,d),(d,2d),\ldots((N-1)d,Nd)$$ is red we are done, hence we may assume they all are green or blue. If $N$ is large enough we have a monochromatic $3$-AP among the previous points, which we may assume to be $$(kd,(k+1)d),((k+1)d,(k+2)d),((k+2)d,(k+3)d)$$ made by green points. If one of the points $$ (kd,(k+2)d),((k+1)d,(k+3)d)$$ is either red or green we are done, hence we may assume they are both blue. But in such a case we have a monochromatic triangle with a vertex in $(kd,(k+3)d)$.

enter image description here

Addendum: this can be easily turned into a proof of the Hales-Jewett theorem for monochromatic squares in $\mathbb{Z}^2$. The argument above shows that in any $M\times M$ square (for an explicit, huge $M$) there is a monocromatic $|\overline{\phantom{a\,}}$, which can be positioned in $\leq M^4$ ways in the $M\times M$ square. It follows that by diagonally stacking $\leq M^4+1$ squares $M\times M$ we surely find two monochromatic $|\overline{\phantom{a\,}}$ with the same relative position. By diagonally stacking more $M\times M$ squares, we surely find two monochromatic $|\overline{\phantom{a\,}}$ with the same relative position and the same color. By diagonally stacking more $M\times M$ squares, we surely find a $k$-AP of monochromatic $|\overline{\phantom{a\,}}$ with the same relative position. We finish by considering the color of the missing square vertex in any $|\overline{\phantom{a\,}}$ and by applying induction on $n$.