US-TST 2011 Problem 8

Let $n \geq 1$ be an integer, and let $S$ be a set of integer pairs $(a,b)$ with $1 \leq a < b \leq 2^n$ . Assume $|S| > n \cdot 2^{n+1}$ . Prove that there exists four integers $a < b < c < d$ such that $S$ contains all three pairs $(a,c)$ , $(b,d)$ and $(a,d)$ .