Consider a $9 \times 9$ array of white squares. Find the largest $n \in \mathbb{N}$ with the property: No matter how one chooses $n$ out of $81$ white squares and colors in black, there always remains a $1 \times 4$ array of white squares (either vertical or horizontal).
Source: BdMO 2019 National Secondary P6
For the sake of contradiction, assume that there is a configuration of $19$ black squares such that there is no place for $1\times4$ white rectangle.
In any $1\times4$ rectangle, there is at least $1$ black cell.
So, in any $1\times8$ rectangle, there is at least $2$ black cells.
Now, in the first leftmost $9\times8$ rectangle, dividing it into $9$ rectangle of size $1x8$, we see that each of them has at least $2$ black cells. So, this $9x8$ area has at least 18 black squares.
There is a $9x1$ area remaining. Taking the top $8$ cells, we see there is also at least $2$ black cells.
So, the board has at least $20$ black cells. Contradiction.
Now, we need to show that there is a configuration of $20$ black cells that resists all $1x4$ white rectangles. So, the answer is $19$.
Gonitzoggoβ