Problem

Source: India Postal Coaching 2014 Set 5 Problem 4

Tags: combinatorics unsolved, combinatorics



Let $A_1,A_2,\ldots,A_n$ and $B_1,B_2,\ldots,B_n$ be two partitions of a set $M$ such that $|A_j\cup B_k|\ge n$ for any $j,k\in\{1,2,\ldots,n\}$. Prove that $|M|\ge n^2/2$.