SELECTION EXAMINATION

Let $x_1,x_2,\dots ,x_8$ be the number of black squares in the rows, such that $x_1\ge x_2\ge \dots \ge x_8$. This means that if, for example, the fourth line has the maximum number of black squares, then these are $x_1$. From the problem condition we have:

$$x_1+x_2+\dots +x_8=12.(1)$$

We observe that it is impossible $x_1=x_2=\dots =x_8$, since then $8x_1=12$, a contradiction. This means that:

$$x_1+x_2+x_3+x_4>x_5+x_6+x_7+x_8.$$

We will prove that it is impossible to have: $$x_1+x_2+x_3+x_4=x_5+x_6+x_7+x_8+1,$$ Since then (1) gives $2(x_1+x_2+x_3+x_4)-1=12$, a contradiction, since the left hand side is odd, while the right hand side is even. Moreover, we cannot have: $$x_1+x_2+x_3+x_4=x_5+x_6+x_7+x_8+2.(2)$$ Indeed, if (2) was true, then from (1) we will have that $x_1+x_2+x_3+x_4=7$ and $$x_5+x_6+x_7+x_8=5,(3)$$ so that $4x_4\le 7\Rightarrow x_4\le 1$. From the ordering condition we have $x_8\le x_7\le x_6\le x_5\le x_4\le 1$, so $x_8+x_7+x_6+x_5\le 4$, which is a contradiction according to (3). Therefore: $$x_1+x_2+x_3+x_4\ge x_5+x_6+x_7+x_8+3,$$ so from (1) we have: $$2(x_1+x_2+x_3+x_4)-3\ge 12\Rightarrow x_1+x_2+x_3+x_4\ge 8,$$ thus, if we choose the $4$ lines with the maximum number of black squares, then these contain at least $8$ black squares. Then, we are left with at most $4$ black squares and for them we choose the $4$ columns in which they are located. As a conclusion, with $4$ lines and $4$ columns we can cover $12$ black squares.