Each cell of the checkered plane is colored in one of $n^2$ colors so that in any square of $n \times n$ cells all colors occur. It is known that in some line all the colors occur. Prove that there exists a column colored in exactly $n$ colors.
Source:
Tags: combinatorics, Coloring
Each cell of the checkered plane is colored in one of $n^2$ colors so that in any square of $n \times n$ cells all colors occur. It is known that in some line all the colors occur. Prove that there exists a column colored in exactly $n$ colors.