Prove that $\sum\limits_{i=1}^n x_i <\frac{5}{3}$ for $x_i\ge 0, \forall i$ with $x_{i}x_{j}\le 4^{-|i-j|}, \forall i, j$ Question:

Let $x_{1},x_{2},\cdots,x_{n}\ge 0$ with
  $$x_{i}x_{j}\le 4^{-|i-j|}$$
  for  all $i, j = 1, \dots, n.$ Show that
  $$x_{1}+x_{2}+\cdots+x_{n}<\dfrac{5}{3}.$$

This problem is  from
South East Mathematical Olympiad yesterday.maybe can use matrix or integral  inequality?
I found the constant $\dfrac{5}{3}$ is best ,because we let
$$x_{n}=\dfrac{1}{4^k},x_{n-1}=\dfrac{1}{4^{k-1}},\cdots,x_{[n/2]+1}=\dfrac{1}{4},x_{[n/2]}=1,x_{[n/2]-1}=\dfrac{1}{4},\cdots,x_{2}=\dfrac{1}{4^{k-1}},x_{1}=\dfrac{1}{4^k}$$
it is clear this example such this condition,and we have
$$\lim_{k\to\infty}[x_{1}+x_{2}+\cdots+x_{n}]=\dfrac{1/4}{1-1/4}+1+\dfrac{1/4}{1-1/4}=\dfrac{5}{3}$$
if this inequlity to prove 
$$x_{1}+x_{2}+\cdots+x_{n}<2$$
we can use Mathematical induction $x_{1},x_{2},\cdots,x_{n}$ is less than 
$$1,\dfrac{1}{2},\dfrac{1}{2^2},\cdots,\dfrac{1}{2^{n-1}}$$
because Assmue that $n=k$ is true,Note 
$$x_{1}x_{k+1}\le \dfrac{1}{4^k}$$
since
$$x_{1}\le\dfrac{1}{2^{k}}$$
so
$$x_{k+1}<\dfrac{1}{2^{k}}$$
so
$$x_{1}+x_{2}+\cdots+x_{n}=\sum_{k=1}^{n}\dfrac{1}{2^{k-1}}<2$$
Thank you 
 A: We make a couple of observations:


*

*If the constraints of the form $x_ix_j \leq 4^{-|i-j|}$ always remain in the form of inequalities, then we can always increase some of the entries without violating the conditions while increasing the sum. In particular, suppose there is an index i such that $x_ix_j \lt 4^{-|i-j|}$ for all j. Then we can keep increasing $x_i$ until one of these becomes an equality. Therefore, we can assume for now that for all i, there exists a j such that $x_ix_j = 4^{-|i-j|}$

*Suppose $x_ix_j = 4^{-|i-j|}$. For now, wlog assume that $i < j$. Then for all $k>j$, $x_ix_k \leq 4^{-|i-k|}$ means that $x_k 4^{-|i-j|} / x_j\leq 4^{-|i-k|}$ and so $x_k \leq 4^{-|j-k|}x_j$. This leads to a geometric series, summing which we get that the sum of all the elements starting from $x_j$ and continuing to the right cannot exceed $4x_j$/3. In general if an element a is constrained by another element on one side of it, then the sum of all elements on the other side including itself cannot exceed 4a/3.

*Take a maximum element in the set, call it x. Now, we have shown that all elements must satisfy some constraint in a candidate for a maximal sum. Therefore, x too must satisfy some constraint. wlog assume that the constraining variable lies on the left. So the sum of all elements on the right of x including x itself cannot exceed 4x/3.

*We call the element on the left of x as y (if x is the leftmost element, then the sum described in this point just becomes 0. So the rest of the argument is unaffected). Observe that as x is no less than y, the elements constraining y must lie to the right of y (if any constraining element lied on the left of y, then x would be at most y/4. But we have taken x to be a maximum element). So sum of y + all elements to the left of y cannot exceed 4y/3.

*The sums described in the last two points cover the whole array. So total sum cannot exceed 4x/3 + 4y/3 = 4(x+y)/3.

*Under the constraints, x and y are less than 1 with $xy \leq 1/4$. So x + y cannot exceed 1 + 1/4 = 5/4 (by considering the function f(x) = x + 1/4x in [0,1]).

*Therefore, the total sum, $S \leq 4(x+y)/3 \leq (4/3)(5/4) = 5/3$.
