Question 176
For a natural number $n$, an $n \times n$ board is given. We now colour $k$ of the cells black in such a way that for any three columns there is at most one row in which all the cells at the intersections with the three columns are coloured black. Show that
$$
\frac{2 k}{n} \leq \sqrt{8 n-7}+1
$$
$$
\frac{2 k}{n} \leq \sqrt{8 n-7}+1
$$