Let $k$ be an arbitrary natural number. Let $\{m_1,m_2,\ldots{},m_k\}$ be a permutation of $\{1,2,\ldots{},k\}$ such that $a_{m_1} < a_{m_2} < \cdots{} < a_{m_k}$. Note that we can never have equality since $|a_{m_i} - a_{m_{i+1}}| \ge \frac{1}{m_i+m_{i+1}}$. Let $\overline{a_ia_j} = |a_i-a_j|$. By looking at the $a_i$ as a set of intervals on $[0,c]$, it makes sense that $\overline{a_{m_1}a_{m_k}} = \sum \limits_{i=1}^{k-1} \overline{a_{m_i}a_{m_{i+1}}}$. $\overline{a_{m_i}a_{m_k}} \ge \sum\limits_{i=1}^{k-1} \frac{1}{m_i+m_{i+1}}$. By the Arithmetic Mean Harmonic Mean Inequality, $\frac{(a_1+a_2) + (a_2+a_3) + \ldots{} + (m_{k-1}+m_k)}{k-1} \ge \frac{k-1}{\frac{1}{m_1+m_2} + \ldots{} + \frac{1}{m_{k-1}+m_k}}$. $(m_1+2m_2+\ldots{}+2m_{k-1}+2m_k)\left(\frac{1}{m_1+m_2} + \ldots{} + \frac{1}{m_{k-1}+m_k}\right) \ge (k-1)^2$. $(\overline{a_{m_1}a_{m_k}})(m_1+2m_2+\ldots{}+2m_{k-1}+m_k) \ge (k-1)^2$. The right term of the left-hand side is less than $2(m_1+m_2+\ldots{}+m_k)$: $2\overline{a_{m_1}a_{m_k}}(m_1+m_2+\ldots{}+m_k) > (k-1)^2$ Since $\{m_1,m_2,\ldots{},m_k\}$ is a permutation of $\{1,2,\ldots{},k\}$, $2\overline{a_{m_1}a_{m_k}} \cdot \frac{k(k+1)}{2} > (k-1)^2$. $\overline{a_{m_1}a_{m_k}} > \frac{(k-1)^2}{k(k+1)} = \frac{k-1}{k} \cdot \frac{k-1}{k+1} > \left(\frac{k-1}{k+1}\right)^2 = \left(1-\frac{2}{k+1}\right)^2$. If $\overline{a_{m_1}a_{m_k}} < 1$ for all $k \in \mathbb N$, we can easily find a $k$ such that $\left(1-\frac{2}{k+1}\right)^2 > \overline{a_{m_1}a_{m_k}}$, causing a contradiction. So $\overline{a_{m_1}a_{m_k}} \ge 1$ for some integers $m_1$, $m_k$. $|a_{m_1}-a_{m_k}| \ge 1$. Since both terms are positive, it is clear that at least one of them is greater than or equal to $1$. So $c \ge 1$, as desired.

I think this is a faster finish - it's basically the same solution. Let the first $ n$ terms be $ a_{1},a_{2},\ldots,a_{n}$, and let $ b_{1},b_{2},\ldots,b_{n}$ be the permutation of them such that $ b_{1}<b_{2}<\cdots<b_{n}$. Then, we need $ b_{n}-b_{1}\le c$. But we have $ b_{n}-b_{1}$; $ =(b_{n}-b_{n-1})+(b_{n-1}-b_{n-2})+\cdots+(b_{2}-b_{1})$; $ \ge\dfrac{1}{b_{n}+b_{n-1}}+\dfrac{1}{b_{n-1}+b_{n-2}}+\cdots+\dfrac{1}{b_{2}+b_{1}}$. By AM-HM, this is greater than $ \dfrac{(n-1)^{2}}{(b_{1}+b_{2})+(b_{2}+b_{3})+\cdots+(b_{n-1}+b_{n})}$; $ =\dfrac{(n-1)^{2}}{2(b_{1}+b_{2}+\cdots+b_{n})-(b_{1}+b_{2})}$; $ \ge\dfrac{(n-1)^{2}}{n(n+1)-3}$. Note that $ \lim_{n\rightarrow\infty}\dfrac{n^{2}-2n+1}{n^{2}+n-3}=1$. Thus, if $ c<1$, we can find sufficiently large $ n$ such that $ b_{n}-b_{1}>c$ (I guess by Epsilon-Delta?), contradiction. So $ c\ge1$.

Clarification on the above: $ b_{1},b_{2},\ldots,b_{n}$ should be a permutation of $ 1,2,\ldots,n$ such that $ a_{b_{1}}<a_{b_{2}}<\cdots<a_{b_{n}}$, and $ a_{b_{n}}-a_{b_{1}}\le c$. And the first two lines of equalities should read $ a_{b_{n}}$, etc.

orl wrote: Let $ a_1,a_2,\ldots$ be an infinite sequence of real numbers, for which there exists a real number $ c$ with $ 0\leq a_i\leq c$ for all $ i$, such that \[ \left|\,a_i - a_j\,\right|\geq{1\over i + j}{\rm \forall}i,j \quad \textnormal{with} \quad i\ne j.\] Prove that $ c\geq1$. Nice problem Anyone try solve this problem? Let $ c\geq 1$ such that there exists an infinite sequence $ a_1,a_2,\ldots$ of real numbers, such that $\lim_{n\to \infty} x_n = c$, and for all $ i\neq j$ to have $|\,a_i - a_j|\geq{1\over i + j}$. Find all such $ c$.

Consider $a_1,a_2,\cdots a_n$ and let $b_1,b_2,\cdots b_n$ be this sequence in sorted order, and suppose $b_{k}=a_{i_k}$. Note that \begin{align*} c&\ge b_n-b_1\\ &=\sum_{k=1}^{n-1} |b_{k+1}-b_{k}|\\ &\ge \sum_{k=1}^{n-1} \frac{1}{i_k+i_{k+1}}\\ &\ge \frac{(n-1)^2}{i_1+2i_2+\cdots + 2i_{n-1}+i_{n}}\\ &\ge \frac{(n-1)^2}{1+2+2(3+\cdots +n)}\\ &=\frac{(n-1)^2}{n^2+n-3} \end{align*}so as $n$ approaches infinity, we recover $c\ge 1$.

I have a question: What the limit of $\frac{1}{n+1}+\frac{1}{n+2}+...+\frac{1}{2n-1}$ wher approaches infinity?

K.titu wrote: I have a question: What the limit of $\frac{1}{n+1}+\frac{1}{n+2}+...+\frac{1}{2n-1}$ wher approaches infinity? $ln(2)$

Since $a_i \neq a_j$, for each natural $n$ there exist a permutation $(t_i)_{1 \le i \le n}$ of $(i)_{1 \le i \le n}$ for which $a_{t_{k+1}}-a_{t_k} \ge \frac{1}{t_k+t_{k+1}}, \forall 1 \le k \le n-1.$ Then $$c \ge a_{t_n}-a_{t_1} \ge \sum_{k=1}^{n-1} \frac{1}{t_k+t_{k+1}} \ge \frac{n^2}{2 \sum t_i - t_1 - t_n} > \frac{n^2}{n(n+1)} = \frac{n}{n+1}$$for all naturals $n$, then clearly $c \ge 1$.

This is much different from the other solutions, so I don't know if it's correct...

aops29 wrote: This is much different from the other solutions, so I don't know if it's correct...

The infinite subsequence could start at $a_{n+1}$ for all $n.$ The line "clearly there are distinct integers..." does not hold because of this.

Order $\{a_i\}_i$ as $0\leq a_{\pi(1)}\leq a_{\pi(2)}\leq \cdots \leq a_{\pi(n+1)}$ for some $n$. Then, \[a_{\pi(n+1)} \geq \sum_{i=1}^{n} \frac1{\pi(i) + \pi(i+1) }\]Which by Jensen's on the convexity of $\frac1x$, is \[\geq n \cdot \frac{1}{\frac1{n} \sum_{i=1}^{n} \pi(i) + \pi(i+1)}= \frac{n^2}{2\cdot (1+2+\cdots n) - \pi(1)-\pi(n+1)} \]\[\geq \frac{n^2}{n(n+1)} = \frac{n}{n+1}\]which as $n\to \infty$ converges to 1. Thus, if $c<1$, then selecting $n$ such that $\frac{n}{n+1} > c$ would yield a contradiction on some inequality for $i,j\leq n$, and we're done. $\blacksquare$. Addendum: Construction. I believe that the equality case is \[a_1, a_n, a_{3}, a_{n-2}, a_5 ,\cdots \]

What is IMO, lol?

I don't know if my method is correct but I gave it a try. We have the sequence a_1; a_2; a_3; ......., suppose we rearrange it to b_1; b_2; b_3;..... such that b_1>b_2>b_3>...... We know that |a_i-a_j|>1/(i+j) so we can also say that |b_i-b_j|>1/(i+j). If we let j>i we know that b_i>b_j so that gives b_i-b_j>1/(i+j), which gives b_i>1/(i+j) + b_j. Setting j=i+1 results in b_i>1/(2i+1) + b_(i+1). Filling in i=i+1 and j=i+2 gives b_(i+1)>1/(2i+3) + b_(i+2) so b_i>1/(2i+1) + b_(i+1)> 1/(2i+1) + 1/(2i+3) + b_(i+2). Doing this a few times shows us that: b_i> 1/(2i+1) + 1/(2i+3) + 1/(2i+5) + ...... + 1/(2i+1+2n) + b_(i+n+1) > 1/(2i+1) + 1/(2i+3) + 1/(2i+5) + ...... + 1/(2i+1+2n). If we plug in i=1 and n=6 we get that b_1 > 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/13 + 1/15 > 1. If c<1 we get that b_1 is less than 1 which is less than b_1, a contradiction. Therefore c>1 Q.E.D.

We do the dumbest possible thing. Assume, for the sake of contradiction, that there exists a valid ordering such that $c < 1$. Take some integer $k$, and say that the values $a_1,a_2,\ldots,a_k$ sorted are $a_{\sigma(1)}, a_{\sigma(2)}, \ldots, a_{\sigma(k)}$; i.e., $\sigma$ is a bijection from $[n] \rightarrow [n]$ and $a_{\sigma(1)} < a_{\sigma(2)} < \cdots < a_{\sigma(k)}$. Then, write: \[ c \geq \sum\limits_{i=1}^{k-1} \frac{1}{a_{\sigma(i)} + a_{\sigma(i+1)}} \]by applying the given equation to consecutive terms, and then by C-S we have \[ \left( \sum\limits_{i=1}^{k-1} \frac{1}{a_{\sigma(i)} + a_{\sigma(i+1)}}\right) \left(\sum\limits_{i=1}^{k-1} a_{\sigma(i)} + a_{\sigma(i+1)} \right) \geq \left(\sum\limits_{i=1}^{k-1} 1\right)^2 \]and note that the right hand side is equal to $(k-1)^2$. Furthermore, we have: \[ \sum\limits_{i=1}^{k-1} (a_{\sigma(i)} + a_{\sigma(i+1)}) < 2\sum\limits_{i=1}^{k} a_i = k(k+1) \]and therefore $c \geq \frac{(k-1)^2}{k(k+1)}$. However, the right hand side approaches $1$ as $k$ goes to infinity, so at some point the $\frac{(k-1)^2}{k(k+1)}$ will be larger than $c$, contradiction.

Let $b_1,b_1,\cdots ,b_n$ be a permutation of $1,2, \cdots ,n$ such that $$0\leq a_{b_1}\leq a_{b_2}\leq \cdots \leq a_{b_n}\leq c.$$Now we have \begin{align*} c\geq a_{b_n}\geq a_{b_n}-a_{b_1} &=(a_{b_n}-a_{b_{n-1}})+(a_{b_{n-1}}-a_{b_{n-2}})+...+(a_{b_2}-a_{b_1})\\ &\geq\sum^n_{i=1} \frac{1}{b_i+b_{i+1}}. \end{align*} Using the Cauchy-Schwarz Inequality we obtain $$\bigg(\sum^n_{i=1} \frac{1}{b_i+b_{i+1}}\bigg)[(b_1+b_2)+(b_2+b_3)+\cdots +(b_{n-1}+b_n)]\geq (n-1)^2.$$Hence \begin{align*} \sum^n_{i=1} \frac{1}{b_i+b_{i+1}} &\geq \frac{(n-1)^2}{b_1+b_n+2(b_2+b_3+\cdots+b_{n-1})}\\ &=\frac{(n-1)^2}{2(1+2+\cdots+n)-b_1-b_n}\\ &\geq\frac{(n-1)^2}{n(n+1)-3}=\frac{n^2-2n+1}{n^2+n-3} \end{align*} It follows that $$c\geq \lim_{n \to \infty} \frac{n^2-2n+1}{n^2+n-3}=1$$

Note that something stronger can be claimed. For every infinite sequence $\big( a_k\big)_{k=1}^{\infty}$ with $0\le a_k\le 1$ there exists sufficiently large $N$ and $i,j; N\le i<j\le 2N$ such that $$|a_i-a_j|>\frac{1}{2(j-i)}.$$This is stronger since $$\frac{1}{2(j-i)} \ge \frac{1}{2N}\ge \frac{1}{i+j}$$when $N\le i<j\le 2N$. One can see how it is done in this Miklos Schweitzer, 1980 problem.

Instructive

Suppose FTSOC that $c<1$. Then we can pick arbitrarily large $n$ such that $0\le a_i\le c$ for all $1\le i\le n$. Consider a nonincreasing sequence of numbers $a_{\sigma(1)},a_{\sigma(2)},\dots,a_{\sigma(n)}$. Note that \begin{align*} a_{\sigma(1)}-a_{\sigma(n)} &= (a_{\sigma(1)}-a_{\sigma(2)})+(a_{\sigma(2)}-a_{\sigma(3)})+\dots+(a_{\sigma(n-1)}-a_{\sigma(n)}) \\ &\ge \frac{1}{\sigma(1)+\sigma(2)}+\frac{1}{\sigma(2)+\sigma(3)}+\dots+\frac{1}{\sigma(n-1)+\sigma(n)} \\ &\ge \frac{(n-1)^2}{n(n+1)-\sigma(1)-\sigma(n)} \\ &\ge \frac{n^2-2n+1}{n^2+n-3} \\ &= 1-\frac{3n-4}{n^2+n-3} \end{align*}so that taking $n$ to be sufficiently large, we obtain a contradiction. $\blacksquare$

Great problem

Let $n$ be large and $\sigma$ be the permutation of $(1,2,\dots,n)$ for which $a_{\sigma(1)}<a_{\sigma(2)}<a_{\sigma(3)}<\dots<a_{\sigma(n)}.$ Note that \[c\ge a_{\sigma(n)}-a{\sigma(1)}=\sum_{k=1}^{n-1}{a_{\sigma(k+1)}-a{\sigma(k)}}\ge\sum_{k=1}^{n-1}{\frac{1}{\sigma(k+1)+\sigma(k)}}\]By AM-HM, \[c\ge \frac{(n-1)^2}{n(n+1)-\sigma(1)-\sigma(n)}\ge \frac{(n-1)^2}{n(n+1)-3}.\]Since the RHS approaches $1$ as $n$ approaches infinity, $c\ge 1.$ mihaig wrote: Great problem I concur

First thing to notice is that we can't assume $a_1 \geq a_2 ..... \geq a_n$ nor $a_n \geq a_{n-1} ..... \geq a_1$ for some $n$ due to the RHS. Now the trick is to Let $a_{p(1)},.......,a_{p(n)}$ be permutations of the set {$1,2,......,n$}. Now we can assume freely that $a_{p(1)} \leq a_{p(2)}.........\leq a_{p(n)}$. Since we can rewrite as the following: $c \geq a_{p(n)}-a_{p(1)}=a_{p(n)}-a_{p(n-1)}+a_{p(n-1)}-a_{p(n-2)}+.........+a_{p(2)}-a_{p(1)}$. And we have that $a_{p(n)}-a_{p(n-1)}+a_{p(n-1)}-a_{p(n-2)}+.........+a_{p(2)}-a_{p(1)}$ $\geq \sum_{i=1}^{n-2}\frac{1}{p(n-i)+p((n-1)-i)} $ It's only left to show that: $\sum_{i=1}^{n-2}\frac{1}{p(n-i)+p((n-1)-i)} \geq 1 $ Now by Titu lemma (consequence of Cauchy Shwarz theorem) which states: $\sum_{i=1}^{n} \frac{a_i^2}{b_i} \geq \frac{(a_1+....+a_n)^2}{b_1+.....+b_n}$ We have that $\sum_{i=1}^{n-2}\frac{1}{p(n-i)+p((n-1)-i)}$ $ \geq \frac{(n-1)^2}{a_{p(n)}+2a_{p(n-1)}+......+2a_{p(2)}+a_{p(1)}}$ $ \geq \frac{(n-1)^2}{2(1+2+....+n)-a_{p(n)}-a_{p(1)}} $ $\geq \frac{(n-1)^2}{2(1+2+....+n)-2-1} = \frac{(n-1)^2}{n^2+n-3}$ Which as $n$ approaches $\infty, $$ c \geq 1$

can we construct such a sequence for $c=1$?

Solved with a 25% hint. If I knew it was an inequality problem (and not an analysis one) then I probably could've done it without any hints. Even though I was trying to use telescoping, I didn't think something like this would work Suppose for the sake of contradiction that $c<1$, then $0\leq a_i<1$ for all $i$. Let $1-\varepsilon$ be the least upper bound of $\{a_1,a_2,\dots\}$. Take a number $k$ such that $\varepsilon>\frac{3k-1}{k(k+1)}$. Consider a permutation $(n_1,n_2,\dots,n_k)$ of $(1,2,\dots,k)$ such that $0\leq a_{n_1}<a_{n_2}<\dots<a_{n_k}$. Now telescoping and using AM-HM $$a_{n_k}-a_{n_1}=\sum_{i=1}^{k-1}(a_{n_{i+1}}-a_{n_i})\geq \sum_{i=1}^{k-1}\frac{1}{n_{i+1}+n_i}$$$$\geq \frac{(k-1)^2}{n_1+2n_2+\dots+2n_{k-1}+n_k}>\frac{(k-1)^2}{2(n_1+\dots+n_k)}=\frac{(k-1)^2}{k(k+1)}=1-\frac{3k-1}{k(k+1)}>1-\varepsilon.$$It follows that $a_{n_k}>1-\varepsilon$, and this is the desired contradiction.

Let $\sigma$ be a permutation of $\{1, 2, \dots, n\}$ such that $a_{\sigma(1)} < a_{\sigma(2)} < \dots < a_{\sigma(n)}$. By the conditions of the problem and by C-S we have that $$ C \geq a_{\sigma(n)} - a_{\sigma(1)}= (a_{\sigma(n)} - a_{\sigma(n-1)}) + (a_{\sigma(n-1)} - a_{\sigma(2)}) + \dots + (a_{\sigma(2)} - a_{\sigma(1)}) $$$$ \geq \frac{1}{\sigma(n) + \sigma(n-1)} + \frac{1}{\sigma(n-1) + \sigma(n-2)} + \dots + \frac{1}{\sigma(2) + \sigma(1)} $$$$ \geq \frac{n^2}{2(1 + 2 + \dots + n) - \sigma(n) - \sigma(1)} \geq \frac{n^2}{n(n+1)} $$ Thus $$ C \geq \lim_{n \to \infty} \frac{n^2}{n(n+1)} = 1 $$ and we are done.