Choose any 38 different natural numbers less than 1000.
Prove that among the selected numbers there exists at least two whose difference is at most 26.
I think I need to use pigeon hole principle, not sure where to even begin.
[Math] Choose 38 different natural numbers less than 1000, Prove among these there exists at least two whose difference is at most 26.
combinatoricspigeonhole-principle
Related Question
- [Math] The sum of five positive numbers is $100$. Prove that there are two numbers among them whose difference is at most $10$.
- [Math] Given seven points inside a hexagon with side length $1$ prove that there exists two points with distance at most $1$
- Show there must be two numbers in the list whose difference is $12$.
Best Answer
Pigeonhole principle is not necessary.
Hint: Suppose the statement is false. Then $\exists x_1,x_2,\dots,x_38$ each less than $1000$. Suppose without loss of generality that $x_1<x_2<\dots<x_{38}$. Then it must be true that $x_2 \geq x_1 + 27$. Similarly $x_3 \geq x_2+27\geq x_1 + 27\times2$. What is the lower bound on $x_{38}$?