Prove that in a given coloring of a square, there exists a sub-square with a certain coloring.

Question

I was given the following question:

There is a square which is divided to sub-squares by edges which are parallel to the edges of the big square (vertices are connected by the edges).

The vertices of the big square are colored $1,2,3,4$, and each vertex which lies on the edges of the big square can be colored only in the color of the two vertices which define the edge of the square.

Any inner vertex could be colored in any color $1,2,3,4$.

Prove that there is at least $1$ sub-square who's vertices are colored in at least $3$ different colors.

This seems to be a variation of Sperner's lemma - which could maybe solved by counting arguments, However I could not find a viable solution for this problem.

Would love to see the solution for this!

Answer 1

The proof does use Sperner's lemma after all: Treat colour $4$ as a variation of $3$, then flatten the two sides $33'$ and $3'1$ into a single side and add an edge in each square as shown. Then by Sperner's lemma there is a trichromatic triangle, either $123$ or $123'$. Because of the way we triangulated the square grid, this triangle's vertices belong to one square's vertices and we are done.