Given a square board of and one colors exactly squares of the board. Prove that for every way of coloring, there always exists a sub-square size of the board on which exactly one square is colored.
Solution
We number rows numbered from to (from top to bottom), and columns numbered from to (from left to right). Suppose by contradiction that each square board does not contain exactly one colored square.
Obviously there must also be an empty column, let's say it is the column with . Let's consider the left column (if any) of this column, that is, the -th column. If on that -th column, there is a colored square. Let's consider the corresponding square containing squares on -th column (which are two uncolored squares) and also containing the cell. Thus, the remaining cell in -th column must also be colored because otherwise the table contains exactly colored cell, which contradicts the assumption.
Continuing like that, consider the squares containing cells in column and containing a colored cell in column , then by similar reasoning, the remaining cell is also colored. This shows that the entire column must be colored, that is, there are colored cells, which is absurd. From there, we can deduce that column is an empty column. The same reasoning goes for column . From there, we can continue to expand to columns and columns , which are also empty columns. Therefore, the entire table is not colored, which is also absurd. This proves the given assertion.