Exercise 1088Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026

$\{1,2,3,\ldots\}$ and pairwise differences

#pigeonhole#difference#arithmetic

Statement

Show that among any $n+1$ integers from $\{1,\ldots,2n\}$ , some two have the same difference as another pair.

Hint

There are $\binom{n+1}{2}$ pairs among $n+1$ integers, and differences are in $\{1,\ldots,2n-1\}$ . This is not immediately pigeonhole.

Show solutionHide solution

Pairs. $n+1$ integers give $\binom{n+1}{2}=\frac{n(n+1)}{2}$ pairs.

Differences. Each difference is in $\{1,\ldots,2n-1\}$ .

Bound. $\frac{n(n+1)}{2}$ vs $2n-1$ : for $n\ge3$ , $\frac{n(n+1)}{2}>2n-1$ . So two pairs share the same difference.

Conclusion. Some two pairs have the same difference.