A combinatorics question on a $n \times n$ grid In the book 'Foundations of Data Science' by Hopcroft and Kannan, they have the following exercise (Ex. 5.46):

Let G be a $n \times n$ lattice and let $S$ be a subset of $G$ with cardinality at most $\frac{n^2}2$. Define $$N = \{(i,j) \in S \,\, | \text{all elements in row $i$ and all elements in column $j$ belong to $S$}\}$$Show that 
  $$\displaystyle |N| \leq \dfrac{|S|}2$$

My failed attempt:
I tried to fix $k$ elements in $N$ and calculate the minimum number of elements that should be added to $S$ so that the membership criteria of $N$ is satisfied. I added an element, one at a time to $N$, and kept track of how $|S|$ increases.
The first element in $N$, immediately adds $2n-1$ elements to $S$. The second element adds at least $n-1$ elements and the third element adds at least $n-2$ elements. Sadly, I ran into a problem. As an example consider, adding row 1 and column 1 to $S$, that is, adding $(1,1)$ to $N$. Now subsequently add $(1,2)$ and $(2,1)$ to $N$ and therefore add $n-1 + n-2$ more elements in $S$. But observe how $(2,2)$ can now be freely added to $N$ without adding any elements in $S$. This shows that picking elements for $S$ affects the choice of elements for $N$ and it is hard to keep track. :(
Is there a simple solution to this problem? Or is there a work around for my failed attempt?
Thanks
 A: I'm not sure how to make your idea work, but it could still be possible. Consider the following however.
First note that $|S|\le n^2/2$ implies $|S|/n^2 \le 1/2$.
I'll write $S$ covers a row or column to mean all elements of that row/column are in $S$.
Given $|S|$ we want to know how many whole rows or columns we could cover with $S$ of that size, as each row/column has $n$ entries we could cover at most $|S|/n$ rows or $|S|/n$ columns.
(You could stop reading here and maybe try and finish it off with this idea in mind :))
Now a pair $(i,j)\in N$ if and only if both its row and its column are covered by $S$. So as we have at most $|S|/n$ rows and $|S|/n$ columns covered by elements of $S$ there can be at most $(|S|/n)^2$ elements of $N$.
So $$|N| \le \frac{|S|^2}{n^2}  = |S| \frac{|S|}{n^2} \le \frac{|S|}{2}.$$
A: Here's an entirely different approach (although somewhat related to Alex' solution) that can give a much stronger bound
$$
\sqrt{|N|}+\sqrt{n^2-|S|}\le n
$$
from which the result follows.
If $S$ contains $p$ full rows and $q$ full columns, then $|N=pq|$. However, with $p$ rows and $q$ columns full, if $k$ of the remaining $(n-p)(n-q)$ grid points (from the rows and columns other than these $p$ and $q$ full ones) are in $S$, that makes
$$
|S|=n^2-(n-p)(n-q)+k\ge np+nq-pq.
$$
Now, we may use $\frac{x+y}{2}\ge\sqrt{xy}$ for any $x,y\ge0$ to get
$$
n^2-|S|\le(n-p)(n-q)\le\left(n-\frac{p+q}{2}\right)^2.
$$
On the other hand,
$$
|N|=pq\le\left(\frac{p+q}{2}\right)^2.
$$
Taking square roots and adding these two inequalities, we get
$$
\sqrt{|N|}+\sqrt{n^2-|S|}\le n,
$$
which, entering $s=|S|/n^2$, makes
$$
\frac{|N|}{n^2}\le \left(1-\sqrt{1-s}\right)^2
=\left(\frac{s}{1+\sqrt{1-s}}\right)^2
$$
which is $\le s/2$ whenever $s\le8/9$. If $s\le 1/2$, then
$|N|/|S|\le3-2\sqrt{2}=0.17157\ldots$
follows.
