Pigeonhole principle problem involving inequality 0 < |$\sqrt{x} - \sqrt{y}$| < 1

Question

21 integers are selected from {1, 2, 3, ..., 400}. Prove that two of them, say x and y, satisfy 0 < |$\sqrt{x} - \sqrt{y}$| < 1.

I am confident you have to use and apply the Pigeon Hole Principle. From what I gathered, there are 400 numbers in the set and $\sqrt{400} = 20$. The minimal difference is obtained by looking at consecutive integers. I don't know where to go from here.

Answer 1

Divide the 400 integers into 20 groups $g_1\ldots g_{20}$, where $n\in g_i$ if $i\le\sqrt n\lt i+1$. That is: $$\begin{align} g_1 & = \{\mathbf{1}, 2, 3\} \\ g_2 & = \{\mathbf{4}, 5, 6, 7, 8\} \\ g_3 & = \{\mathbf{9}, 10, \ldots, 15\} \\ & \;\vdots \\ g_{19} & = \{\mathbf{361}, 362, \ldots, 399\} \\ g_{20} & = \{\mathbf{400}\} \end{align} $$

Of the 21 pigeons, two must be in the same group $g_i$.

Answer 2

You practically have the solution. Let us arrange the selected integers in non-decreasing order and denote them $a_1, a_2, \ldots, a_{21}$. Now, $0 < a_1 \leq a_{21} \leq 400$, therefore $\sqrt{a_{21}}- \sqrt{a_1} < 20$.

Now notice that $$ \sqrt{a_{21}}- \sqrt{a_1} = (\sqrt{a_{21}} - \sqrt{a_{20}}) + (\sqrt{a_{20}} - \sqrt{a_{19}}) + \ldots + (\sqrt{a_2} - \sqrt{a_1}). $$

There are $20$ summands on the right hand side, they are all nonnegative, and their sum is less than $20$. It follows by the pigeonhole principle that one of them is less than $1$.

This is somewhat different from the usual pigeonhole method, i.e. there aren't really any pigeons and pigeonholes. But the principle is similar. We assume that each summand is greater than or equal to $1$, we conclude that the sum is greater than or equal to $20$, and this is a contradiction.

UPDATE: if you look at BFD's answer, it becomes clear that he standard, usual, "normal" pigeonhole principle can be applied too.

Answer 3

Consider the collection of twenty numbers {$1=1^2, 4=2^2,.....,400=20^2$} If you choose 21 numbers, one of them will be inside of an interval $(n^2, (n+1)^2)$

Answer 4

Choose $21$ integers $x_1 \leq x_2 \leq \cdots \leq x_{21}$. Suppose for the sake of contradiction that $|\sqrt{x_i} - \sqrt{x_j}| \geq 1$ for all distinct $i$ and $j$. In particular, we have $\sqrt{x_2} - \sqrt{x_1} \geq 1$, $\sqrt{x_3} - \sqrt{x_2} \geq 1$, and so on until $\sqrt{x_{21}} - \sqrt{x_{20}} \geq 1$. Adding them up, we obtain $\sqrt{x_{21}} \geq 20+\sqrt{x_{1}} \geq 21\implies x_{21} \geq 441$, a contradiction.

Answer 5

There are 20 pigeonholes, and there are 400 pigeons, from which you will select 21. The pigeonholes in this case happen to be squares of different integer widths: 1", 2", and so on up to 20". Conveniently, the pigeons also happen to be square. They have distinct integral areas in square inches, from 1 square inch to 400 square inches.

The pigeons know they must roost in the smallest pigeonhole they can fit into, so if two pigeons (of areas $x$ and $y$) are roosting in the same hole, $\lfloor{\sqrt{x}}\rfloor=\lfloor{\sqrt{y}}\rfloor$, and therefore $0<\left|\sqrt{x} - \sqrt{y}\right|< 1$. Twenty-one pigeons, twenty pigeonholes.