Seven colors in a lattice
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?
For example, the coloring shown would be illegal since the three vertices of the grey triangle share the same color, red.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Here is a solution provided by @Jon Haussmann:
For the sake of induction, we're going to strengthen the problem. We claim that for n colors, there is a triangular grid of some size, say f ( n ) , such that if the grid is colored with n colors, then there is a monochromatic triangle.
Clearly, f ( 1 ) = 1 . Assume that f ( n − 1 ) exists for some n > 1 .
Suppose we have an infinite triangular grid with n colors. Then by Van der Waerden's Theorem , there exists some number W , so that for any W vertices in a row, there exist f ( n − 1 ) + 2 vertices, equally spaced, that have the same color. If we draw the lines through these f ( n − 1 ) + 2 points, then we effectively have a triangular grid of size f ( n − 1 ) , and at most n − 1 colors, so by the induction hypothesis, there exists a monochromatic triangle. Thus, we can take f ( n ) = W − 1 . By induction, we are done.
So Van der Waerden's Theorem , on arithmetic sequences (which is a somewhat advanced, but established result) is exactly what we need to generate the smaller grid.