United States — Team Selection Test

Let $p$ and $q$ be integers with $1 \le p \le 2^n$ and $0 \le q \le n-1$. We say that a pair $(a, b)$ has type $A(p, q)$ if $a = p$ and $2^q \le b - a < 2^{q+1}$, and we say that it has type $B(p, q)$ if $b = p$ and $2^q \le b - a < 2^{q+1}$. Because there are $n2^{n+1}$ total types and $|S| > n2^{n+1}$, we may find some $(a, b) \in S$ such that $(a, b)$ is neither
* the pair of type $A(a, q)$ in $S$ with the smallest possible value of $b$, nor
* the pair of type $B(b, q)$ in $S$ with the largest possible value of $a$.
Therefore, there exists $(a, b') \in S$ of type $A(a, q)$ with $b' < b$; note that $b' - a \ge 2^q$. Similarly, there exists $(a', b) \in S$ of type $B(b, q)$ with $a < a'$; note that $b - a' \ge 2^q$. Adding the two inequalities yields
$$2^{q+1} \le b' - a + b - a' < b' - a' + 2^{q+1},$$
hence $a' < b'$. Then, we have $a < a' < b' < b$, where $S$ contains the three pairs $(a, b)$, $(a, b')$, and $(a', b)$, as needed.