Let $ p $ be a natural number and let two partitions $ \mathcal{A} =\left\{ A_1,A_2,...,A_p\right\} ,\mathcal{B}=\left\{ B_1,B_2,...B_p\right\} $ of a finite set $ \mathcal{M} . $ Knowing that, whenever an element of $ \mathcal{A} $ doesn´t have any elements in common with another of $ \mathcal{B} , $ it holds that the number of elements of these two is greater than $ p, $ prove that $ \big| \mathcal{M}\big|\ge\frac{1}{2}\left( 1+p^2\right) . $ Can equality hold?
Problem
Source: Romanian TST 1978, Day 4, P3
Tags: set theory, partitions
Tintarn
12.10.2018 15:36
Bump! This is interesting. Note that it is quite easy to get a bound asymptotic to $\frac{p^2}{3}$ (smaller than the desired $\frac{p^2}{2}$): Let $a_{ij}=\vert A_i \cap B_j\vert$. Then for any $i,j \le p$ we have $a_{ij}+\frac{\sum_{k \ne i} a_{kj}+\sum_{l \ne j} a_{il}}{p+1} \ge 1$. Summing this over all $i,j$ this yields $(\sum_{i,j} a_{ij}) \left(1+\frac{2p-2}{p+1}\right) \ge p^2$ and hence $\vert M\vert \ge \frac{p^2(p+1)}{3p-1} \ge \frac{p^2}{3}$.
soryn
12.10.2018 21:26
Thanks...
Fever
13.10.2018 01:24
Let $a_i = |A_i|, b_i = |B_i|$. WLOG $a_i, b_i$ are increasing. Suppose contrary: $|M| <\dfrac{1+p^2}{2}$. Then $a_1 < \dfrac{1+p^2}{2p} < p$. So there are at least $\lceil p - \dfrac{1+p^2}{2p} \rceil$ sets from $B_i$ that don't have common elements with $A_1$. Then $|M| \geq (p+1) \lceil p - \dfrac{1+p^2}{2p} \rceil = (p+1) \lceil \dfrac{p^2 - 1}{2p} \rceil$. Considering cases $p = 2k, 2k+1$ we get, that $(p+1) \lceil \dfrac{p^2 - 1}{2p} \rceil \geq \dfrac{p^2 + 1}{2}$ which is contradiction.