show that $\left|\frac{x_{i}}{x_{j}}-\frac{x_{k}}{x_{l}}\right|<\frac{1}{2}$

111 Views Asked by At

Let $x_{1},x_{2},x_{3},x_{4},x_{5}$ be $5$ distinct postive real numbers, show that :

There exist four distinct postive real numbers $x_{i},x_{j},x_{k},x_{l}$ where $i,j,k,l\in \{1,2,3,4,5\}$,such that $$\left|\frac{x_{i}}{x_{j}}-\frac{x_{k}}{x_{l}}\right|<\frac{1}{2}$$

It seems to use pigeonhole-principle to solve it. But How to use it?

2

There are 2 best solutions below

7
On

Assume WLOG that the numbers are sorted $0 \lt x_1 \lt x_2 \lt x_3 \lt x_4 \lt x_5\,$. Then all fractions $\,x_k/x_{k+j} \in (0,1)\,$ for $\,k=1,2,3,4\,$ and $\,j \ge 1\,$.

If any of them $\,x_k/x_{k+j}=1/2\,$ then all the other fractions will be within $\,\lt 1/2\,$ of it, so the inequality is obviouly satisfied.

Otherwise, $\,x_1/x_2\,$ must lie either strictly in $\,(0,1/2)\,$, or strictly in $\,(1/2,1)\,$. Suppose WLOG the former, then if either of the two fractions $\,x_3/x_4,x_4/x_5\,$ which don't involve $\,x_1,x_2\,$ lies in $\,(0,1/2)\,$ as well, then it would be within $\,\lt 1/2\,$ of $\,x_1/x_2\,$. Suppose then that both $\,x_3/x_4,x_4/x_5 \in (1/2,1)$. By the same reasoning as before:

  • $\,x_3/x_4 \in (1/2,1)\,$ requires that $\,x_2/x_5 \in (0,1/2)\,$, otherwise $\,\big|x_3/x_4 - x_2/x_5\big| \lt 1/2\,$

  • $\,x_4/x_5 \in (1/2,1)\,$ requires that $\,x_1/x_3 \in (0,1/2)\,$, otherwise $\,\big|x_4/x_5 - x_1/x_3\big| \lt 1/2\,$

But then both $x_2/x_5$ and $x_1/x_3$ belong to $\,(0,1/2)\,$, so $\,\big|x_1/x_3 - x_2/x_5\big| \lt 1/2\,$.

1
On

Without loss of generality let $0 < x_1 < x_2 < x_3 < x_4 < x_5$.

Then for all $i < j$ and $i,j\in \{1,2,3,4,5\}$ we have $0 < \dfrac{x_i}{x_j} < 1$.

If for some pair $x_i,x_j$ we have $\dfrac{x_i}{x_j} = \dfrac{1}{2}$ then there are $k,l$ different from $i,j$ such that $k < l$. Thus $0 < \dfrac{x_k}{x_l} < 1$ and then $-\dfrac{1}{2} < \dfrac{x_k}{x_l} - \dfrac{x_i}{x_j} < \dfrac{1}{2}$.

Otherwise each of the following is either in $\left(0,\dfrac{1}{2}\right)$ or $\left(\dfrac{1}{2},1\right)$:

$$\dfrac{x_1}{x_2}, \quad \dfrac{x_1}{x_3}, \quad \dfrac{x_2}{x_3}, \quad \dfrac{x_1}{x_4}, \quad \dfrac{x_2}{x_4}, \quad \dfrac{x_3}{x_4}, \quad \dfrac{x_1}{x_5}, \quad \dfrac{x_2}{x_5}, \quad \dfrac{x_3}{x_5}, \quad \dfrac{x_4}{x_5}.$$

By the pigeonhole principle, at least one of this intervals contains at least $5$ of this fractions. Out of those $5$ there are at least $2$ of them, $\dfrac{x_i}{x_j}$ and $\dfrac{x_k}{x_l}$, where $x_i,x_j,x_k,x_l$ are four different numbers. The difference of this two fractions is in $\left(-\dfrac{1}{2},\dfrac{1}{2}\right)$.


EDIT: If the assertion that among the $5$ fractions there are at least two suitable ones seems insufficient then use the following argument:

Let $S$ be the set of those (at least) $5$ fractions. Let $\dfrac{x_a}{x_b}\in S$. Then let $S_a = \left\{\dfrac{x_i}{x_j}\in S\mid x_i, x_j\neq x_a\right\}$ and $S_b = \left\{\dfrac{x_i}{x_j}\in S\mid x_i, x_j\neq x_b\right\}$. This sets are not empty because each $x_i$ appears exactly $4$ times among our total set and we have (at least) $5$ fractions.

If $S_a\cap S_b \neq \emptyset$ then we are done: $\dfrac{x_a}{x_b}$ and any element in $S_a\cap S_b$ form a suitable pair.

Otherwise all elements of $S_a$ are either $\dfrac{x_b}{x_i}$ or $\dfrac{x_i}{x_b}$ for some $x_i$ and similarly all elements in $S_b$ are of the form $\dfrac{x_a}{x_j}$ or $\dfrac{x_j}{x_a}$ for some $x_j$. Moreover, $S_a$ and $S_b$ form a partition of $S\setminus \left\{\frac{x_a}{x_b}\right\}$. So $|S_a| + |S_b|$ is (at least) $4$ and by the prigeonhole principle at least one of this two sets contains at least two elements.

Without loss of generality let $S_a$ be this set and let us select any element in $S_b$. It involves $x_a$ and some $x_c$, i.e. is either $\dfrac{x_a}{x_c}$ or $\dfrac{x_c}{x_a}$. Then $S_a$ must contain at least one element where the numerator and the denominator are not $x_c$. Indeed since all elements in $S_a$ are of the form $\dfrac{x_b}{x_i}$ or $\dfrac{x_i}{x_b}$ then the only case where this is not true is if $S_a = \left\{\dfrac{x_b}{x_c},\dfrac{x_c}{x_b}\right\}$ but this cannot be since then one of this fractions would be larger than $1$.


EDIT 2: This might be more concise although the first answer is more general. Let us begin like in the original answer but now we will only consider the fractions

$$\dfrac{x_1}{x_2},\qquad \dfrac{x_2}{x_3},\qquad \dfrac{x_3}{x_4},\qquad\dfrac{x_4}{x_5},\qquad \dfrac{x_1}{x_5}.$$

By the pigeonhole principle there are at least $3$ elements in either $\left(0,\dfrac{1}{2}\right)$ or in $\left(\dfrac{1}{2},1\right)$. Let $S$ be that set.

We have two cases to consider:

  • $\dfrac{x_1}{x_5}\notin S$. Then we either both $\dfrac{x_1}{x_2},\dfrac{x_3}{x_4}\in S$ or both $\dfrac{x_2}{x_3},\dfrac{x_4}{x_5}\in S$.

  • $\dfrac{x_1}{x_5}\in S$. Then either both $\dfrac{x_1}{x_2},\dfrac{x_4}{x_5} \in S$ or at least one of $\dfrac{x_2}{x_3},\dfrac{x_3}{x_4}\in S$.

In any case we have a suitable pair of fractions in $S$ and their difference is in $\left(-\dfrac{1}{2},\dfrac{1}{2}\right)$.