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 $ \, \vert x_{i} \vert \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 \[ \vert x_{i} - x_{j} \vert \vert i - j \vert^{a}\geq 1 \] for every pair of distinct nonnegative integers $ i, j$.
Problem
Source: IMO 1991, Day 2, Problem 6, IMO ShortList 1991, Problem 28 (NET 2)
Tags: algebra, Sequence, bounded, construction, IMO, imo 1991, Harm Derksen
alkjash
15.08.2009 21:53
I'm not sure if this works: After we have found $ x_0, x_1, ... x_{n-1}$ satisfying the conditions, we now choose an $ x_n$ as follows. Draw open intervals of lengths $ 2/1^a, 2/2^a, 2/3^a, ... , 2/n^a$ around $ x_{n-1}, x_{n-2}, ... x_1, x_0$ (so that each of these points are the midpoints of the intervals. It is clear that if $ x_n$ does not lie in any of these intervals, it satisfies the conditions of the problem. Thus we choose the $ x_n$ with smallest absolute value that does not lie in these $ n$ open intervals. Now, because the series $ 1/1^a + 1/2^a + ...$ converges for all real $ a > 1$, these intervals cover a total area that approaches a limit, say c. Then, we can always find $ x_n$ with absolute value less than c, so the sequence is bounded.
scythe33
17.08.2009 10:14
Could you not simply do x_i = -1 ^ i? It doesn't seem like a very interesting problem unless you're looking for a monotonic bounded infinite sequence, in which case x_i = [sum from 1 to i] 2/k^{1 + epsilon} would suffice, where epsilon is small.
Swistak
12.11.2011 15:10
Yesterday I was solving this problem and I thought about exactly the same solution as alkjash's solution. But I don't know if it's really correct, beacuse we should "construct" such a sequence and I don't know if we could say it's construction. What's your opinion?
randomusername
21.06.2015 00:04
Of course, in the IMO problem, the interval $[-C;C]$ can be dilated into interval $[0;1]$, hence such a sequence exists for some $a$ if and only if there is a sequence $x_1,x_2,\dots\in[0;1]$ satisfying $|x_i-x_j|\ge \frac{c}{|i-j|^a}$ for all $i,j\ge 1$ ($i\neq j$) with a suitable constant $c$.
Part b) in the Kömal (or CIIM) problem is in fact equivalent to giving a sequence satisfying $|x_i-x_j|\ge \frac c{|i-j|}$ for some suitable small $c$ - if we give a sequence $x_1,x_2,\dots\in[0;1]$ satisfying the conditions in part b), then we can simply take $y_i=x_{ri}$. (The converse is also true, but takes a bit more effort to prove.)
Part a) in the Kömal problem says that if $x_1,x_2,\dots\in[0;1]$, then for suitable $K>0$, and any positive integer $r$, we can find $i,j$ with $|i-j|\ge r$ and $|x_i-x_j|<\frac{K}{|i-j|}$. Suppose that we have a sequence $x_1,x_2,\dots\in[0;1]$ that satisfies $|x_i-x_j|\ge \frac{c}{|i-j|^a}$ $\forall i,j\ge 1$ ($i\neq j$) for some $c>0$ and $a<1$, and let's take the appropriate $K$. Then if $|i-j|\ge r$ and $|x_i-x_j|<\frac{K}{|i-j|}$, then from the condition we get
$$\frac{K}{|i-j|}\ge \frac{c}{|i-j|^a}\implies \frac{K}{c}\ge |i-j|^{1-a}\ge r^{1-a},$$
which gives a contradiction for $r>(K/c)^{1/(1-a)}$.
) I have posted a solution to the Kömal/CIIM problem here. There's an easy construction for the IMO problem as well, in the case $a=1$ actually. Just let $x_n=\{n\sqrt 2\}$ and use the well-known estimate $$|a\sqrt 2-b|=\frac{|2a^2-b^2|}{|a\sqrt 2+b|}\ge \max\left(1,\frac1{a\sqrt 2+(a\sqrt 2+1)}\right)\ge \frac1{4a}$$ for positive integer $a,b$. (This is a Liouville-type estimate such as here.)
dgrozev
21.06.2015 13:21
http://artofproblemsolving.com/community/c7h551121