Let $I$ be a set of size $2n$. Given any subset $S\subset I$ of size $n$, we call $S^2=S\times S$ a half-square.
Question: How many half-squares can cover the whole square $I^2=I\times I$?
Denote the minimal number in question by $c(2n)$. (It is easy to see that $c(2)$ doesn't make sense; $c(4)=6$, since each upper off-diagonal element must in a half-square.)
Thanks to comments of Rahul and achille hui, I suppose I figured out how to solve the problem. The answer is $c(4k)=6$ and $c(4k+2)=7$.
Let me show that $c(4k)=6$. The proof of $c(4k+2)=7$ is similar.
It is obviously that $c(4k)>(4k)^2/(2k)^2=4$. Using the block trick suggested by Rahul, we can cover the square by 6 half-squares. It remains to show that $c(4k)\ne 5$.
Suppose in the contrary that 5 can do the job. WOLOG, suppose the half-square $[1,...,2k]^2$ is chosen, we have 4 half-squares left. Consider the set $J=[1,...,2k]\times [2k+1,....,4k]$. We assert that any half-square $S^2$ can cover mostly $k^2$ elements of $J$. Let $x=\#(S\cap[1,...,2k])$. The assertion follows from $S^2\cap J = x*(2k-x)\le k^2$. Hence $J$ needs the remaining 4 half-squares to be covered. It is clear that this covering must be exactly what we had by the block trick. Therefore, the given five half-squares are all the same as that given by the block trick, they cannot cover the whole square. QED.