Choose 38 different natural numbers less than 1000, Prove among these there exists at least two whose difference is at most 26.

Question

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.

Answer 1

Pigeonhole-principle is a good idea.

Hint: Think about partitioning $\{1,2,\ldots,999\}$ into subsets $\{1,2,\ldots,27\}$, $\{28,29,\ldots, 54\}$, $\{55,56,\ldots,81\}$, ..., $\{\ldots,998,999\}$ of size $27$ each.

Answer 2

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}$?

Answer 3

Reasoning by contradiction, so suppose that we can choose 38 natural numbers $$0< a_1<a_2<\cdots<a_{38}<1000$$ such that the difference of any two numbers is at least 27. We can see easily that $$a_{n}\geq a_1+27(n-1),\forall n=1,\ldots,38, $$ so $$a_{38}\geq a_1+27\times37\geq1+27\times37=1000.$$ Contradiction. We conclude.