IT-CESENATICO 2014 Problem 6

A $(2n + 1) \times (2n + 1)$ grid, with $n> 0$ , is colored in such a way that each of the cell is white or black. A cell is called special if there are at least $n$ other cells of the same color in its row, and at least another $n$ cells of the same color in its column.

(a) Prove that there are at least $2n + 1$ special boxes. (b) Provide an example where there are at most $4n$ special cells. (c) Determine, as a function of $n$ , the minimum possible number of special cells.