I found a problem on Brilliant, and wonder if it has a Pigeonhole solution.
You have an infinite lattice of equilateral triangles and you would like to fill each node with one of seven colors.
Is there any way to do this so that no equilateral triangle of any size formed by the lattice lines has its three vertices sharing the same color?
I think that there can be a large region that can be proved to have an equilateral triangle.
Here's a problem that uses a rectangular grid and proves that a rectangle has to exist with all same vertices using three colors.
I can't create any proof on it, however. Can anyone show me if (or if not) the statement above can be proven and how it can / why it can't?
Note: a solution that someone contributed includes induction and Van der Waerden's theorem. Maybe that solution could be used to find the Pigeonhole approach?
Best Answer
There's no quick pigeonhole solution.
We can solve the problem using the Ajtai-Szemerédi corners theorem. The corners theorem is not about equilateral triangles in a triangular grid, but about right triangles of the form $\{(x,y), (x,y+h), (x+h, y)\}$ in a rectangular grid; this is an insignificant modification, since we can just skew the rectangular grid and turn these right triangles into the equilateral triangles we want. Or to put it differently, if we number the nodes in the grid as in the diagram below, then the triples of the form $\{(x,y), (x,y+h), (x+h, y)\}$ are precisely the (upright) equilateral triangles.
The corners theorem is also a density result rather than a coloring result: it says that for any $\epsilon>0$, if we pick $\epsilon N^2$ out of $N^2$ points in a $N\times N$ grid, then we can find the triangle among the points we picked, provided $N$ is sufficiently large. But this can be used to get a coloring result: just take $\epsilon = \frac17$, pick a sufficiently large finite subgrid of your infinite grid, and choose the most popular color used on points in that subgrid.
The corners theorem is a fairly high-powered result in Ramsey theory. But I claim that no simple result will do the trick, because the problem is at least as hard as finding monochromatic $3$-term arithmetic progressions, and you can see the arguments in the Wikipedia article on van der Waerden's theorem to see how tricky the proof for those is even for $2$ or $3$ colors.
Suppose you have a $7$-coloring of the integers $1,2,\dots,n$, for some large $n$ with no $3$-term arithmetic progression. Then by giving a point $(x,y)$ in the grid the color of the integer $2x+y$, we can color some large portion of the triangular grid; that portion of the grid will not have any monochromatic triangles. An upright triangle has coordinates $\{(x,y), (x,y+h), (x+h,y)\}$ which corresponds to the integers $2x+y, 2x+y+h, 2x+y+2h$. An inverted triangle has coordinates $(x,y+h), (x+h,y), (x+h,y+h)$ which corresponds to the integers $2x+y+h, 2x+y+2h, 2x+y+3h$. Either way, they form a $3$-term arithmetic progression.
So if you found a quick pigeonhole solution here, you'd have a quick pigeonhole solution to the length-$3$ case of van der Waerden's theorem, which would be a pretty big deal!