Exercise 1812Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026

Separated integers

#pigeonhole#distance#bounded

Statement

Show that if $n+1$ distinct integers are chosen from $\{1,\ldots,2n\}$ , then some two have difference at most $1$ . (This is trivial: two must be consecutive.) Prove the stronger: if they are chosen to be pairwise at distance $\ge2$ , then at most $n$ can be chosen.

Hint

If pairwise distance $\ge2$ , then the $k$ chosen integers satisfy $a_k\ge2k-1$ .

Show solutionHide solution

Solution

Sorting. Let $a_1<a_2<\cdots<a_{n+1}$ . With pairwise distance $\ge2$ : $a_k\ge2k-1$ .

Bound. $a_{n+1}\ge2(n+1)-1=2n+1>2n$ . Contradiction.

Conclusion. At most $n$ pairwise-distant integers can be chosen from $\{1,\ldots,2n\}$ .

Separated integers

Statement

Solution

More problems in Pigeonhole principle