A $8\times 8$ board is given. Seven out of $64$ unit squares are painted black. Suppose that there exists a positive $k$ such that no matter which squares are black, there exists a rectangle (with sides parallel to the sides of the board) with area $k$ containing no black squares. Find the maximum value of $k$.
The answer is $k=8$. This is clearly achievable, as some row is empty. To see that we can't do any better, consider the following coloring:
O O O O O O O O
O O X O O X O O
O O O O O O O O
O X O O O O X O
O O O X O O O O
O O O O O O O O
O O X O O X O O
O O O O O O O O