Maths WorkshopMaths problems with full solutions
Exercise 1804Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026

Difference of at most $10$

#pigeonhole#difference#bound

Statement

Show that among any 1111 integers from {1,…,100}\{1,\ldots,100\}, some two differ by at most 99.

Hint

Sort the 1111 integers and bound consecutive differences.

Show solutionHide solution

Solution

Sorting. Let a1<a2<⋯<a11a_1<a_2<\cdots<a_{11} be the integers.

Range. a11−a1≤100−1=99a_{11}-a_1\le 100-1=99.

Average gap. There are 1010 gaps summing to at most 9999, so some gap is ≤⌊99/10⌋=9\le\lfloor 99/10\rfloor=9.

Conclusion. Two integers differ by at most 99.