Q:

Discrete Math Pigeon-Hole

How can we solve below problem?

Let $X = \{1,2,3,\dotsc,100\}$. If eleven numbers are selected from $X$, show that there are at least two numbers $u$ and $v$ such that $$0 \lt \left| \sqrt{u} - \sqrt{v} \right| \lt 1\;.$$

A:

Since it is absolute value, the expression cannot go below zero, so we do not have to worry about the results being too low. We just have to prove that it cannot go to $1$ or above. A way to ensure that there are no eleven numbers that can be picked from $X$ that do not satisfy the expression is to find the set of numbers where the smallest $|\sqrt{u}-\sqrt{v}|$ is as large as it can be. Given those eleven numbers in a set from least to greatest, adjacent numbers would have the best chance at being the two numbers that can satisfy the expression. To ensure that $|\sqrt{u}-\sqrt{v}|$ is as large as it can be, that expression must be equal among adjacent elements. This will give us a set of eleven decimals but it still works for the problem at hand to test if it is true because a set of integers would be even more restricted than decimals and would have $|\sqrt{u}-\sqrt{v}|$ smaller than or equal to the decimal version.
The first element must be $1$, and the last element must be $100$ because we want the set of eleven to be as spread out as much as possible.
Lets define $x$ as the result of the expression given two adjacent numbers.
$|\sqrt{u}-\sqrt{v}|=x$
$\sqrt{u}=x+\sqrt{v}$
$u=(x+\sqrt{v})^2$
Start with $v=1$ because that must be the first element.
$u=(x+\sqrt{1})^2$
$u=(x+1)^2$
Now plug that back into $u=(x+\sqrt{v})^2$ as $v$
$u=(x+x+1)^2$
$u=(2x+1)^2$
The pattern is now visible as to how the numbers must progress if the expression is to be equal among adjacent numbers. Lets define this set of eleven numbers as $Y$ where $n$ starts at $0$.
$Y_n=(nx+1)^2$
Since $n$ starts at $0$ to maintain a first element of $1$, the $n$ value for eleven iterations must be $10$.
We want $Y_{10}$ to equal $100$ so that the last element of $100$ is maintained.
$100=(10x+1)^2$
Now solve for $x$ and see if it is below $1$. If it is, we know the answer is true. If not, we can round the decimals to integers and re-evaluate the expression, or we can try a different method altogether.
$10=10x+1$
$9=10x$
$x=0.9$
Therefore it must be true. $0.9<1$
The eleven decimals that would provide this result are:
$Y_n=(0.9n+1)^2$
$Y=$ {$1,3.61,7.84,13.69,21.16,30.25,40.96,53.29,67.24,82.81,100$}
As I said before, this is valid because an integer set is more restricted and could only have the expression evaluate to something less than or equal to $0.9$. It could not be equal in this case because for it to be equal, the decimal set would have to naturally occur without any decimals.
This can be generalized further for other problems of the same nature.
Lets define $a$ to be the first element, $b$ to be the last element, and $c$ to be the number of elements selected.
$b=((c-1)x+\sqrt{a})^2$
$\sqrt{b}=(c-1)x+\sqrt{a}$
$\sqrt{b}-\sqrt{a}=(c-1)x$
$x=\frac{\sqrt{b}-\sqrt{a}}{c-1}$
This method can only prove that it is true, with the original set being solely composed of whole numbers. If this method yields false, that does not necessarily mean it is false.

