Exercise 534Combinatorics › Pigeonhole principleL1Added 3 Nov 2026

A pair with difference of $n$

#pigeonhole#difference#exact value

Statement

Show that among any $n+1$ integers, two have difference exactly $n$ ? — False. Corrected: among any $n+1$ integers, two have the same difference as another pair. Actually, a true statement: among any $n+1$ integers from $\{1,\ldots,2n\}$ , two differ by exactly $1$ or by exactly $2$ . Both are false in general (choose $1,3,5,\ldots,2n-1$ ).

Let me state a correct problem: among any $n+2$ integers from $\{1,\ldots,2n\}$ , two differ by at most $1$ .

Hint

If $n+2$ integers are chosen, two must be consecutive (since the max gaps sum to $<n+1$ ).

Show solutionHide solution

Solution

Sorting. $a_1<\cdots<a_{n+2}$ in $\{1,\ldots,2n\}$ .

Gaps. There are $n+1$ gaps, total $a_{n+2}-a_1\le2n-1$ . Average gap $<2$ , so some gap is $1$ .

Conclusion. Two chosen integers are consecutive (differ by $1$ ).

A pair with difference of $n$

Statement

Solution

More problems in Pigeonhole principle