Intersect Three

First, we have to show that 15 $*$ isn't sufficient, i.e. that we can find 3 rows and columns which do not have a $*$ in them. Proof by contradiction. Suppose such a configuration exists. If there exists 3 rows that contain at most $4 *$ , then we can find 3 columns which do not have any $*$ in these 3 rows to give the contradiction. Consider the number of rows with at most 2 $*$ . If there are at most 4 such rows, then there are 3 rows which contain at least $9 *$ , so the other 4 rows contain at most $6 *$ . By the pigeonhole principle, there are 3 rows that contain at most $\lfloor \frac {6 \times 3} {4} \rfloor = 4 *$ , so we are done. If there are at least 5 such rows, they will contain at most 10 $*$ . By the pigeonhole principle, there are 3 rows which contain at most $\lfloor \frac {10 \times 3} {7} \rfloor = 4$ $*$ . Hence, we reach a contradiction again.

It remains to show that 16 $*$ is sufficient. We can check that it is, using $(1, 1), (2, 2), (2, 3), (3, 4)$ , $(3, 5), (4, 6), (4, 7), (5,2)$ , $(5,4), (5, 6), (6,2), (6, 5)$ , $(6,7), (7,2), (7,3), (7,7)$ .