Problem

Source: Croatia MO 2001 4th Grade P4

Tags: combinatorics, game



Suppose that zeros and ones are written in the cells of an $n\times n$ board, in such a way that the four cells in the intersection of any two rows and any two columns contain at least one zero. Prove that the number of ones does not exceed $\frac n2\left(1+\sqrt{4n-3}\right)$.