Problem

Source: 2019 Grand Duchy of Lithuania, Mathematical Contest p2 (Baltic Way TST)

Tags: combinatorics, Coloring, square table



Every cell of a $20 \times 20$ table has to be coloured black or white (there are $2^{400}$ such colourings in total). Given any colouring $P$, we consider division of the table into rectangles with sides in the grid lines where no rectangle contains more than two black cells and where the number of rectangles containing at most one black cell is the least possible. We denote this smallest possible number of rectangles containing at most one black cell by $f(P)$. Determine the maximum value of $f(P)$ as $P$ ranges over all colourings.