Question 43
Let $n \ge 1$ be an integer, and let $S$ be a set of integer pairs $(a, b)$ with $1 \le a \lt b \le 2^n$. Assume $|S| \gt n \cdot 2^{n+1}$. Prove that there exist four integers $a \lt b \lt c \lt d$ such that $S$ contains all three pairs $(a, c)$, $(b, d)$ and $(a, d)$.