Solution

Let \(1 \leqslant a<b \leqslant n\) be such that \(2^{b-a} x_{a} x_{b}\) is maximal. This choice of \(a\) and \(b\) implies that \(x_{a+t} \leqslant 2^{t} x_{a}\) for all \(1-a \leqslant t \leqslant b-a-1\), and similarly \(x_{b-t} \leqslant 2^{t} x_{b}\) for all \(b-n \leqslant t \leqslant b-a+1\). Now, suppose that \(x_{a} \in\left(\frac{1}{2^{u+1}}, \frac{1}{2^{u}}\right]\) and \(x_{b} \in\left(\frac{1}{2^{v+1}}, \frac{1}{2^{v}}\right]\), and write \(x_{a}=2^{-\alpha}, x_{b}=2^{-\beta}\). Then

\[\sum_{i=1}^{a+u-1} x_{i} \leqslant 2^{u} x_{a}\left(\frac{1}{2}+\frac{1}{4}+\ldots+\frac{1}{2^{a+u-1}}\right) < 2^{u} x_{a} \leqslant 1\]

and similarly,

\[\sum_{i=b-v+1}^{n} x_{i} \leqslant 2^{v} x_{b}\left(\frac{1}{2}+\frac{1}{4}+\ldots+\frac{1}{2^{n-b+v}}\right) < 2^{v} x_{b} \leqslant 1\]

In other words, the sum of the \(x_{i}\) 's for \(i\) outside of the interval \([a+u, b-v]\) is strictly less than 2. Since the total sum is at least \(3\), and each term is at most \(1\), it follows that this interval must have at least two integers. i.e., \(a+u<b-v\). Thus, by bounding the sum of the \(x_{i}\) for \(i \in[1, a+u] \cup[b-v, n]\) like above, and trivially bounding each \(x_{i} \in(a+u, b-v)\) by 1 , we obtain

\[s<2^{u+1} x_{a}+2^{v+1} x_{b}+((b-v)-(a+u)-1)=b-a+\left(2^{u+1-\alpha}+2^{v+1-\beta}-(u+v+1)\right)\]

Now recall \(\alpha \in(u, u+1]\) and \(\beta \in(v, v+1]\), so applying Bernoulli's inequality yields \(\left.2^{u+1-\alpha}+2^{v+1-\beta}-u-v-1 \leqslant(1+(u+1-\alpha))\right)+(1+(v+1-\beta))-u-v-1=3-\alpha-\beta\). It follows that \(s-3<b-a-\alpha-\beta\), and so

\[2^{s-3}<2^{b-a-\alpha-\beta}=2^{b-a} x_{a} x_{b}\]

*Comment 1.* It is not hard to see that the inequality is tight. Suppose that \(n = 2k+1\), and we set \(x_{k+1}=1, x_{k}=x_{k+2}=\frac{1}{2}+\frac{1}{2^{k}}\), and \(x_{k+1-t}=x_{k+1+t}=\frac{1}{2^{t}}\). Then \(s=3\) (so the right hand side is 1), and

\[\max _{i<j} 2^{j-i} x_{i} x_{j}=2^{2}\left(\frac{1}{2}+\frac{1}{2^{k}}\right)^{2}\]

which can be made arbitrarily close to 1 . Note that \(s\) can be made larger by putting in more \(1\)s in the middle (and this accommodates even \(n\) as well). *Comment 2.* An alternative formulation of the problem is to show that there exists a positive constant \(c\) (or find the best such \(c\) ) such that

\[\max _{i<j} 2^{j-i} x_{i} x_{j}>c 2^{s}\]

The above shows that \(c=1 / 8\) is the best possible. A somewhat simpler ending to the proof can be given for \(c=1 / 32\). End of solution for \(c=1/32\). As in the original solution, we arrive at

\[s<2^{u+1} x_{a}+2^{v+1} x_{b}+((b-v)-(a+u)-1)=b-a+\left(2^{u+1-\alpha}+2^{v+1-\beta}-(u+v+1)\right)\]

Now \(2^{b-a} x_{a} x_{b} \geqslant 2^{b-a} 2^{-u-1} 2^{-v-1}\), so it is enough to show \(s-5<b-a-u-v-2\), or \(s<b-a-\) \(u-v+3\). The fact that \(u+1-\alpha<1\) and \(v+1-\beta<1\) implies \(2^{u+1-\alpha}+2^{v+1-\beta}<4\), and so \(s<b-a+(2+2-u-v-1)=b-a-u-v-3\).