Say a finite set $M$ has two partition $A_1,A_2,...A_p$ and $B_1,B_2,...B_p$ such that ... 
Say a finite set $M$ has two partitions $A_1,A_2,...A_p$ and $B_1,B_2,...B_p$ such that $$A_i\cap B_j = \emptyset \implies |A_i|+|B_j|\geq p.$$
  Prove: $$|M|\geq {1\over 2}(p^2+1).$$

As far as I can remember (now forgot) the solution was short and easy at the time a saw the problem (about 5 years ago).
My try:
Say $A_1$ cuts $k$ sets from other partition, say $B_1,,,B_k$. Clearly $k\leq |A_1|$ since each element in $A_1$ is in exactly one $B_j$. Then we have \begin{align}|A_1|+|B_1| &=|A_1|+|B_1|\\
&\vdots \\
|A_1|+|B_k| &=|A_1|+|B_k|\\
|A_1|+|B_{k+1}| &\geq p\\
&\vdots \\
|A_1|+|B_p| &\geq p
\end{align}
Summing all those we get  $$p|A_1|+|M| \geq k|A_1|+|A_1|+p(p-k)$$ and now I don't have control over $k$...
 A: Proposition: Let $p$ and $q$ be non-negative integers.  Suppose that $M$ is a set with two partitions $\{A_1,A_2,\ldots,A_p\}$ and $\{B_1,B_2,\ldots,B_p\}$ such that
$$|A_i|+|B_j|\ge q$$
for all pairs $i,j\in\{1,2,\ldots,p\}$ such that $A_i\cap B_j=\emptyset$.  Then,
$$|M|\geq\left\{ \begin{array}{ll}\left\lceil\frac{pq}{2}\right\rceil &\text{if}\ 0\leq q \leq p,\\
\left\lceil\frac{6pq-p^2-q^2}{8}\right\rceil &\text{if}\ p<q<3p,\\
p^2&\text{if}\ q\ge 3p.
\end{array}\right.$$
In particular when $q=p$, we have $|M|\ge \left\lceil\frac{p^2}{2}\right\rceil$. 
Proof: Let $G(V,E)$ be the bipartite graph such that $V=V_A\sqcup V_B$ where
$$V_A=\{A_1,A_2,\ldots,A_p\}$$
and
$$V_B=\{B_1,B_2,\ldots,B_p\},$$ and there exists an edge joining $A_i$ and $B_j$ iff $A_i\cap B_j$ is empty.  Let $I\subseteq E$ be a maximal pairing of $G$ (i.e., a pairing of $G$ with the largest possible number of edges).
Wlog suppose that $I=\big\{\{A_1,B_1\},\{A_2,B_2\},\ldots,\{A_k,B_k\}\big\}$.  Then by maximality of $I$, there are no edges between the vertices of $V_A'=\{A_{k+1},A_{k+2},\ldots,A_p\}$ and the vertices of $V_B'=\{B_{k+1},B_{k+2},\ldots,B_p\}$.  Obviously, this means $A_i\cap B_j\ne\emptyset$ for every $i,j=k+1,k+2,\ldots,p$. 
Furthermore, if there exists $s\in\{1,2,\ldots,k\}$ such that for some $i,j\in\{k+1,k+2,\ldots,p\}$, $A_s\cap B_{j}$ and $A_{i}\cap B_s$ are both empty, then $$\Big(I\setminus\big\{\{A_s,B_s\}\big\}\Big)\cup\big\{\{A_s,B_{j}\},\{A_{i},B_s\}\big\}$$ is a larger pairing of $G$ than $I$.  This is a contradiction.  Therefore, for every $s\in \{1,2,\ldots,k\}$ and for any $i,j\in\{k+1,k+2,\ldots,p\}$, either $A_s\cap B_j$ or $A_i\cap B_s$ is non-empty.  This proves that 
$$|A_i|+|B_j|\geq (p-k)+(p-k)+k=2p-k$$
for all $i,j=k+1,k+2,\ldots,p$.
Because $\sum_{i=1}^p|A_i|=|M|=\sum_{j=1}^p|B_j|$, we get
$$2|M|=\sum_{i=1}^p|A_i|+\sum_{j=1}^p|B_j|=\sum_{s=1}^k\big(|A_s|+|B_s|\big)+\sum_{s=k+1}^p\big(|A_s|+|B_s|\big).$$
Since $|A_s|+|B_s|\ge q$ for all $s=1,2,\ldots,k$, as well as $|A_s|+|B_s|\ge 2p-k$ for $s=k+1,k+2,\ldots,p$, we conclude that
$$2|M|\ge qk+(2p-k)(p-k)=2p^2-(3p-q)k+k^2.$$
Note that $0\le k\le p$.  If $q\le p$, then $$2p^2-(3p-q)k+k^2\ge 2p^2-(3p-q)p+p^2=pq$$  If $p<q<3p$, then $$2p^2-(3p-q)k+k^2\ge 2p^2-(3p-q)\left(\frac{3p-q}{2}\right)+\left(\frac{3p-q}{2}\right)^2=\frac{6pq-p^2-q^2}{4}.$$  If $q\ge 3p$, then  $$2p^2-(3p-q)k+k^2\ge 2p^2-(3p-q)0+0^2=2p^2.$$  The claim follows.
Remark:  I don't think the bound in the proposition is always sharp.  However, the bound above is sharp at least in the following three cases: 


*

*$q\ge 3p$,

*$q\le p$ and $q$ is even, and

*$q=p$ and $q$ is odd. 


When $q\ge 3p$, we can take $M=\{1,2,\ldots,p^2\}$ along with two partitions $\{A_1,A_2,\ldots,A_p\}$ and $\{B_1,B_2,\ldots,B_p\}$ with
$$A_i=\big\{(i-1)p+1,(i-1)p+2,\ldots,(i-1)p+p-1,(i-1)p+p\big\}$$
and
$$B_j=\big\{j,p+j,\ldots,p(p-2)+j,p(p-1)+j\big\}$$
for $i,j=1,2,\ldots,p$.  If $q\le p$ and $q=2b$ is even, then we can take $M=\left\{1,2,\ldots,pb\right\}$ along with two partitions $\{A_1,A_2,\ldots,A_p\}$ and $\{B_1,B_2,\ldots,B_p\}$ with
$$A_s=B_s=\big\{(i-1)b+1,(i-1)b+2,\ldots,(i-1)b+b-1,(i-1)b+b\big\}$$
for $s=1,2,\ldots,p$.  If $q=p$ and $q=2b+1$ is odd, then we can take $M=\left\{1,2,\ldots,2b^2+2b+1\right\}$ with
$$A_i=\big\{(i-1)b+1,(i-1)b+2,\ldots,(i-1)b+b-1,(i-1)b+b\big\}$$
and
$$B_j=\big\{j,b+j,\ldots,b(b-2)+j,b(b-1)+j\big\}$$
for $i,j=1,2,\ldots,b$, and
$$\small A_i=\big\{b^2+(i-b-1)(b+1)+1,b^2+(i-b-1)(b+1)+2,\ldots,b^2+(i-b-1)(b+1)+b,b^2+(i-b-1)(b+1)+(b+1)\big\}$$
and
$$\small B_j=\big\{b^2+(j-b),b^2+(b+1)+(j-b),\ldots,b^2+(b+1)(b-1)+(j-b-1),b^2+(b+1)b+(j-b)\big\}$$
for $i,j=b+1,b+2,\ldots,2b+1$.
