Difference between revisions of "1991 IMO Problems/Problem 6"
(→Solution 2) |
m (→Solution 2) |
||
(5 intermediate revisions by the same user not shown) | |||
Line 19: | Line 19: | ||
== Solution 2 == | == 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== | ==See Also== |
Latest revision as of 02:20, 24 January 2024
Contents
[hide]Problem
An infinite sequence of real numbers is said to be bounded if there is a constant such that for every .
Given any real number , construct a bounded infinite sequence such that for every pair of distinct nonnegative integers .
Solution 1
Since , the series is convergent; let be the sum of this convergent series. Let be the interval (or any bounded subset of measure ).
Suppose that we have chosen points satisfying
for all distinct . We show that we can choose such that holds for all distinct . The only new cases are when one number (WLOG ) is equal to , so we must guarantee that for all .
Let be the interval , of length . The points that are valid choices for are precisely the points of , so we must show that this set is nonempty. The total length is at most the sum of the lengths . This is .
Therefore the total measure of is , so has positive measure and thus is nonempty. Choosing any and continuing by induction constructs the desired sequence.
Solution 2
The argument above would not work for , since only converges for . But Osmun Nal argues in this video that satisfies the stronger inequality for all distinct ; in other words, this sequence simultaneously solves the problem for all simultaneously.
Solution 3
Let , then we have
Thus
For any non-negative integer , represent it as base- positional notation:
, where
We directly construct
We allow leading zeros for representing due to the leading zeros do not effect the value of
Then
Thus , which is bounded
For any two distinct non-negative integers , represent them as base- positional notation:
where
Let be the minimum number such that , that is,
Then we have
Without loss of generality, assume that , then we have
Thus we have
~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 |