Difference between revisions of "1991 IMO Problems/Problem 6"

Latest revision as of 02:20, 24 January 2024

Problem

An infinite sequence $x_0, x_1, x_2,\ldots$ of real numbers is said to be bounded if there is a constant $C$ such that $|x_i| \leq C$ for every $i \geq 0$ .

Given any real number $a > 1$ , construct a bounded infinite sequence $x_0,x_1,x_2,\ldots$ such that $|x_i-x_j|\cdot |i-j|^a\geq 1$ for every pair of distinct nonnegative integers $i,j$ .

Solution 1

Since $a>1$ , the series $\sum_{k=1}^\infty\frac{1}{k^a}$ is convergent; let $L$ be the sum of this convergent series. Let $I\subset \mathbb{R}$ be the interval $[-L,L]$ (or any bounded subset of measure $\geq 2L$ ).

Suppose that we have chosen points $x_0,x_1,\ldots,x_{m-1}$ satisfying

$\qquad(\ast)\quad |x_i-x_j|\cdot |i-j|^a\geq 1$

for all distinct $i,j<m$ . We show that we can choose $x_m\in I$ such that $(\ast)$ holds for all distinct $i,j\leq m$ . The only new cases are when one number (WLOG $i$ ) is equal to $m$ , so we must guarantee that $|x_m-x_j|\cdot |m-j|^a\geq 1$ for all $0\leq j<m$ .

Let $U_j$ be the interval $(x_j-\frac{1}{|m-j|^a},x_j+\frac{1}{|m-j|^a})$ , of length $\frac{2}{|m-j|^a}$ . The points that are valid choices for $x_m$ are precisely the points of $I\setminus(U_0\cup \cdots \cup U_{m-1})$ , so we must show that this set is nonempty. The total length $\mu(U_0\cup \cdot\cup U_{m-1})$ is at most the sum of the lengths $\mu(U_0)+\cdots+\mu(U_{m-1})=\frac{2}{m^a}+\frac{2}{(m-1)^a}+\cdots+\frac{2}{2^a}+\frac{2}{1^a}$ . This is $2\sum_{k=1}^m\frac{1}{k^a}<2\sum_{k=1}^\infty \frac{1}{k^a}=2L$ .

Therefore the total measure of $U_0\cup \cdots \cup U_{m-1}$ is $<2L=\mu(I)$ , so $I\setminus(U_0\cup \cdots \cup U_{m-1})$ has positive measure and thus is nonempty. Choosing any $x_m\in I\setminus(U_0\cup \cdots \cup U_{m-1})$ and continuing by induction constructs the desired sequence.

Solution 2

The argument above would not work for $a=1$ , since ${\textstyle\sum \frac{1}{k^a}}$ only converges for $a>1$ . But Osmun Nal argues in this video that $x_k=C\cdot\left(k\sqrt{2}-\lfloor k\sqrt{2}\rfloor\right), C=2\sqrt2+1$ satisfies the stronger inequality $|x_i-x_j|\cdot |i-j|\geq 1$ for all distinct $i,j$ ; in other words, this sequence simultaneously solves the problem for all $a\geq 1$ simultaneously.

Solution 3

Let $n = \max \left( \left\lceil \dfrac{1}{a - 1} \right\rceil, 3 \right)$ , then we have $\dfrac{\ln \left( n + 1 \right)}{\ln n} = \dfrac{\ln n + \ln \left( 1 + 1/n \right)}{\ln n} < \dfrac{\ln n + 1/n}{\ln n} = 1 + \dfrac{1}{n \ln n} < 1 + \dfrac{1}{n} \le a$

Thus $n^a > n + 1$

For any non-negative integer $i$ , represent it as base- $n$ positional notation:

$i = i_m n^m + i_{m-1} n^{m-1} + \cdots + i_2 n^2 + i_1 n + i_0$ , where $i_m, i_{m-1}, \cdots, i_2, i_1, i_0 \in \left\{ 0, 1, 2, \cdots, n - 1 \right\}$

We directly construct $x_i = n \left( i_0 + i_1 \left( n + 1 \right)^{-1} + i_2 \left( n + 1 \right)^{-2} + \cdots + i_m \left( n + 1 \right)^{-m} \right)$

We allow leading zeros for representing $i$ due to the leading zeros do not effect the value of $x_i$

Then $0 \le x_i \le n \left( \left( n - 1 \right) + \left( n - 1 \right) \left( n + 1 \right)^{-1} + \cdots + \left( n - 1 \right) \left( n + 1 \right)^{-m} \right) < n \left( n - 1 \right) \dfrac{1}{1 - \left( n + 1 \right)^{-1}} = n^2 - 1$

Thus $\left| x_i \right| < n^2 - 1$ , which is bounded

For any two distinct non-negative integers $i \neq j$ , represent them as base- $n$ positional notation:

$i = i_m n^m + i_{m-1} n^{m-1} + \cdots + i_2 n^2 + i_1 n + i_0$

$j = j_m n^m + j_{m-1} n^{m-1} + \cdots + j_2 n^2 + j_1 n + j_0$

where $i_m, i_{m-1}, \cdots, i_2, i_1, i_0, j_m, j_{m-1}, \cdots, j_2, j_1, j_0 \in \left\{ 0, 1, 2, \cdots, n - 1 \right\}$

Let $\ell$ be the minimum number such that $i_\ell \neq j_\ell$ , that is, $i_0 = j_0, i_1 = j_1, \cdots, i_{\ell - 1} = j_{\ell - 1}, i_\ell \neq j_\ell$

Then we have $\left| i - j \right| \ge n^\ell$

Without loss of generality, assume that $i_\ell > j_\ell$ , then we have $i_\ell - j_\ell \ge 1, j_{\ell + 1} - i_{\ell + 1}, j_{\ell + 2} - i_{\ell + 2}, \cdots, j_m - i_m \le n - 1$

$\left| x_i - x_j \right| = n \left( \left( i_\ell - j_\ell \right) \left( n + 1 \right)^{-\ell} - \left( j_{\ell+1} - i_{\ell+1} \right) \left( n + 1 \right)^{-\ell-1} - \left( j_{\ell+2} - i_{\ell+2} \right) \left( n + 1 \right)^{-\ell-2} - \cdots - \left( j_m - i_m \right) \left( n + 1 \right)^{-m} \right) \\~\\ \ge n \left( n + 1 \right)^{-\ell} - n \left( n - 1 \right) \left( \left( n + 1 \right)^{-\ell-1} + \left( n + 1 \right)^{-\ell-2} + \cdots + \left( n + 1 \right)^{-m} \right) \\~\\ > n \left( n + 1 \right)^{-\ell} - n \left( n - 1 \right) \left( n + 1 \right)^{-\ell-1} \dfrac{1}{1 - \left( n + 1 \right)^{-1}} = \left( n + 1 \right)^{-\ell}$

Thus we have $\left| x_i - x_j \right| \left| i - j \right|^a > \left( n + 1 \right)^{-\ell} n^{a \ell} > \left( n + 1 \right)^{-\ell} \left( n + 1 \right)^\ell = 1$

~Joseph Tsai, mgtsai@gmail.com

@@ Line 19: / Line 19: @@
 == Solution 2 ==
-The argument above would not work for <math>a=1</math>, since <math>{\textstyle\sum \frac{1}{k^a}}</math> only converges for <math>a>1</math>. But Osmun Nal argues [https://www.youtube.com/watch?v=3v3CMQS_5Cc in this video] that <math>x_k=k\sqrt{2}-\lfloor k\sqrt{2}\rfloor</math> satisfies the stronger inequality <math>|x_i-x_j|\cdot |i-j|\geq 1</math> for all distinct <math>i,j</math>; in other words, this sequence simultaneously solves the problem for all <math>a\geq 1</math> simultaneously.
+The argument above would not work for <math>a=1</math>, since <math>{\textstyle\sum \frac{1}{k^a}}</math> only converges for <math>a>1</math>. But Osmun Nal argues [https://www.youtube.com/watch?v=3v3CMQS_5Cc in this video] that <math>x_k=C\cdot\left(k\sqrt{2}-\lfloor k\sqrt{2}\rfloor\right), C=2\sqrt2+1</math> satisfies the stronger inequality <math>|x_i-x_j|\cdot |i-j|\geq 1</math> for all distinct <math>i,j</math>; in other words, this sequence simultaneously solves the problem for all <math>a\geq 1</math> simultaneously.
+== Solution 3 ==
+Let <math>n = \max \left( \left\lceil \dfrac{1}{a - 1} \right\rceil, 3 \right)</math>, then we have <math>\dfrac{\ln \left( n + 1 \right)}{\ln n} = \dfrac{\ln n + \ln \left( 1 + 1/n \right)}{\ln n} < \dfrac{\ln n + 1/n}{\ln n} = 1 + \dfrac{1}{n \ln n} < 1 + \dfrac{1}{n} \le a</math>
+Thus <math>n^a > n + 1</math>
+For any non-negative integer <math>i</math>, represent it as base-<math>n</math> positional notation:
+<math>i = i_m n^m + i_{m-1} n^{m-1} + \cdots + i_2 n^2 + i_1 n + i_0</math>, where <math>i_m, i_{m-1}, \cdots, i_2, i_1, i_0 \in \left\{ 0, 1, 2, \cdots, n - 1 \right\}</math>
+We directly construct <math>x_i = n \left( i_0 + i_1 \left( n + 1 \right)^{-1} + i_2 \left( n + 1 \right)^{-2} + \cdots + i_m \left( n + 1 \right)^{-m} \right)</math>
+We allow leading zeros for representing <math>i</math> due to the leading zeros do not effect the value of <math>x_i</math>
+Then <math>0 \le x_i \le n \left( \left( n - 1 \right) + \left( n - 1 \right) \left( n + 1 \right)^{-1} + \cdots + \left( n - 1 \right) \left( n + 1 \right)^{-m} \right) < n \left( n - 1 \right) \dfrac{1}{1 - \left( n + 1 \right)^{-1}} = n^2 - 1</math>
+Thus <math>\left| x_i \right| < n^2 - 1</math>, which is bounded
+For any two distinct non-negative integers <math>i \neq j</math>, represent them as base-<math>n</math> positional notation:
+<math>i = i_m n^m + i_{m-1} n^{m-1} + \cdots + i_2 n^2 + i_1 n + i_0</math>
+<math>j = j_m n^m + j_{m-1} n^{m-1} + \cdots + j_2 n^2 + j_1 n + j_0</math>
+where <math>i_m, i_{m-1}, \cdots, i_2, i_1, i_0, j_m, j_{m-1}, \cdots, j_2, j_1, j_0 \in \left\{ 0, 1, 2, \cdots, n - 1 \right\}</math>
+Let <math>\ell</math> be the minimum number such that <math>i_\ell \neq j_\ell</math>, that is, <math>i_0 = j_0, i_1 = j_1, \cdots, i_{\ell - 1} = j_{\ell - 1}, i_\ell \neq j_\ell</math>
+Then we have <math>\left| i - j \right| \ge n^\ell</math>
+Without loss of generality, assume that <math>i_\ell > j_\ell</math>, then we have <math>i_\ell - j_\ell \ge 1, j_{\ell + 1} - i_{\ell + 1}, j_{\ell + 2} - i_{\ell + 2}, \cdots, j_m - i_m \le n - 1</math>
+<math>\left| x_i - x_j \right| = n \left( \left( i_\ell - j_\ell \right) \left( n + 1 \right)^{-\ell} - \left( j_{\ell+1} - i_{\ell+1} \right) \left( n + 1 \right)^{-\ell-1} - \left( j_{\ell+2} - i_{\ell+2} \right) \left( n + 1 \right)^{-\ell-2} - \cdots - \left( j_m - i_m \right) \left( n + 1 \right)^{-m} \right) \\~\\ \ge n \left( n + 1 \right)^{-\ell} - n \left( n - 1 \right) \left( \left( n + 1 \right)^{-\ell-1} + \left( n + 1 \right)^{-\ell-2} + \cdots + \left( n + 1 \right)^{-m} \right) \\~\\ > n \left( n + 1 \right)^{-\ell} - n \left( n - 1 \right) \left( n + 1 \right)^{-\ell-1} \dfrac{1}{1 - \left( n + 1 \right)^{-1}} = \left( n + 1 \right)^{-\ell}</math>
+Thus we have <math>\left| x_i - x_j \right| \left| i - j \right|^a > \left( n + 1 \right)^{-\ell} n^{a \ell} > \left( n + 1 \right)^{-\ell} \left( n + 1 \right)^\ell = 1</math>
+~Joseph Tsai, mgtsai@gmail.com
 ==See Also==

1991 IMO (Problems) • Resources
Preceded by Problem 5	1 • 2 • 3 • 4 • 5 • 6	Followed by Last Question
All IMO Problems and Solutions

Page

Toolbox

Search