Some cells of an infinite chessboard (infinite in all directions) are coloured blue so that at least one of the $100$ cells in any $10 \times 10$ rectangular grid is blue. Prove that, for any positive integer $n$, it is possible to select $n$ rows and $n$ columns so that all of the $n^2$ cells in their intersections are blue.
Problem
Source: Well-known
Tags: combinatorics, infinite grid
03.08.2023 12:44
I'll solve this problem by solving the following: Let $m$ be a positive integer. There is an infinite chessboard. Each cell of the chessboard contains an integer in $\{1, 2, \dots, m\}$. Prove that for any positive integer $n$, one can always find $n$ rows and $n$ columns whose $n^2$ intersections contain the same number. Consider a $(nm)\times(nm^{nm})$ rectangular grid ($nm$ rows). Since there are $m^{nm}$ ways to assign $\{1, 2, \dots, m\}$ to the cells in a single column, by pigeonhole principle, there exists $\lfloor\frac{nm^{nm}}{m^{nm}}\rfloor=n$ columns such that the numbers on the cells of these columns on the same row are the same. Since there are $m$ ways to assign $\{1, 2, \dots, m\}$ to the cells on the intersection of a single row and the $n$ columns (note that the numbers on the same row are the same), by pigeonhole principle, there exists $\lfloor\frac{nm}m\rfloor=n$ rows such that the numbers on the cells of the intersection of the $n$ columns and these rows are the same. These $n$ rows and $n$ columns is what we required. Back to this problem, let's call a $10\times10$ rectangular grid a bigcell, and number the $100$ different position of cells in a bigcell from $1$ to $100$. The original chessboard is also an infinite chessboard of bigcells. For each bigcell, assign an integer in $\{1, 2, \dots, 100\}$ representing the cell with the smallest number that is colored blue in this bigcell. From the above, we can find $n$ rows of bigcells and $n$ columns of bigcells such that the number on the $n^2$ intersections are the same. That is, the colored cells of the $n^2$ bigcells are at the same position in the bigcells. Therefore, one can select a row from each of the $n$ rows of bigcells and a column from each of the $n$ columns of bigcells, such that the intersection of these selected $n$ rows and $n$ columns are colored blue.