Question 137
Let be given an integer $n \ge 2$ and a rectangular board of size $n \times 2n$ ($n$ rows, $2n$ columns). One labels randomly $n^2$ little squares of the board. Prove that for every integer $k$ such that $1 \lt k \le \lfloor n/2 \rfloor + 1$, there always exist $k$ rows of the board so that the rectangular board of size $k \times 2n$ formed by these $k$ rows has no less than
$$
\frac{k!(n - 2k + 2)}{(n - k + 1)(n - k + 2)\dots(n - 1)}
$$
columns containing only labelled little squares.
($[a]$ denotes the greatest integer not exceeding $a$)
$$
\frac{k!(n - 2k + 2)}{(n - k + 1)(n - k + 2)\dots(n - 1)}
$$
columns containing only labelled little squares.
($[a]$ denotes the greatest integer not exceeding $a$)