Let $x_i\ (i = 1, 2, \cdots 22)$ be reals such that $x_i \in [2^{i-1},2^i]$. Find the maximum possible value of $$(x_1+x_2+\cdots +x_{22})(\frac{1}{x_1}+\frac{1}{x_2}+\cdots+\frac{1}{x_{22}})$$
Problem
Source: Chinese Girls Mathematical Olympiad 2023
Tags: algebra
Tintarn
13.08.2023 12:10
Clearly, there is a maximum possible value as the function is continuous and all intervals are bounded and closed.
Moreover, the expression is convex in each variable so the maximum occurs when each variable is at one of the boundaries i.e. $x_i \in \{2^{i-1},2^i\}$.
Next, let us show that no two variables are the same at the maximum value.
Indeed, otherwise $x_i=x_{i+1}=2^i$. But then both factors and hence the whole expression becomes strictly larger if we set $x_i=2^{i-1}$ and $x_{i+1}=2^{i+1}$ instead.
We are thus in a situation where each but one of the $23$ numbers $2^0,2^1,\dots,2^{22}$ is taken exactly once. Suppose that $2^k$ is missing. Then the expression equals
\[(2^{23}-1-2^k)(2-\frac{1}{2^{22}}-\frac{1}{2^k})=\left(2^{12}-\frac{1}{2^{11}}\right)^2+1-\left(2^{12}-\frac{1}{2^{11}}\right) \cdot \left(2^{k-11}+2^{11-k}\right)\]and it is clear that this maximized if $k=11$ so that the maximum value of the whole expression becomes $\left(2^{12}-1-\frac{1}{2^{11}}\right)^2$.
IAmTheHazard
14.08.2023 05:45
By compactness and continuity a unique maximum exists. Furthermore, it is easy to see that the expression is convex in each variable, hence the maximum occurs when each $x_i$ is either $2^{i-1}$ or $2^i$. If there are $i<j$ with $x_i=2^i$ and $x_j=2^{j-1}$ then setting $x_i=2^{i-1}$ and $x_j=2^j$ will increase both terms in the product: contradiction. Hence either all of the $x_i$ are $2^{i-1}$, all of the $x_i$ are $2^i$, or there exists some $1 \leq k \leq 21$ such that for $1 \leq i \leq k$, $x_i=2^{i-1}$, and for $k+1 \leq i \leq 22$, $x_i=2^i$. In the former two cases, the expression equals $\frac{(2^{22}-1)^2}{2^{21}} \approx 2^{23}$. Otherwise, the expression equals $$(2^{23}-2^k-1)(2-2^{-k}-2^{-22})=\frac{1}{2^{22}}((2^{23}-1)-2^k)((2^{23}-1)-2^{22-k})=\frac{(2^{23}-1)^2-(2^k+2^{22-k})(2^{23}-1)+2^{22}}{2^{22}}.$$Evidently this is maximized when $2^k+2^{22-k}$ is minimized, which occurs when $k=11$, in which case the expression is $\frac{(2^{23}-2^{11}-1)^2}{2^{22}} \approx 2^{24}$, which is clearly larger, so this is the maximum. $\blacksquare$ Remark: I think these 3 cases are unnecessary and we can combine everything into the third but I don't really want to think about it
Stranger8
14.08.2023 13:11
Quite a standard and old problem. We try to find a proper constant $c$ to use AM-GM inequality $(\sum_{i=1}^{22}x_i)(\sum_{i=1}^{22}\frac{c}{x_i})\le \frac{1}{4}(\sum_{i=1}^{22}x_i+\frac{c}{x_i})^2$ In order to reach the equality case (and also notice the symmetry) we choose constant $c=2^{22}$ then for all $1\le i\le 11$ the function $x_i+\frac{2^{22}}{x_i}$ reach maximum at $x_i=2^{i-1}$ and for all $12\le i\le 22$ the function $x_i+\frac{2^{22}}{x_i}$ reach maximum at $x_i=2^{i+1}$ so $(\sum_{i=1}^{22}x_i+\frac{2^{22}}{x_i})\le 2(2^{23}-1-2^{11})\Rightarrow (\sum_{i=1}^{22}x_i)(\sum_{i=1}^{22}\frac{1}{x_i})\le \frac{(2^{23}-1-2^{11})^2}{2^{22}}$. Original thought comes from this problem .https://artofproblemsolving.com/community/c6h1234376p6260511.
Scrutiny
14.08.2023 13:35
I will post a solution I saw on the Internet, which is basically similar to what @above wrote but written in another way: Note that $$\sum_{k=1}^{11}\frac{(x_k-2^{k-1})(x_k-2^{23-k})}{x_k}+\sum_{k=12}^{22}\frac{(x_k-2^k)(x_k-2^{22-k})}{x_k}\le 0$$which is equivalent to $$\sum_{k=1}^{22}x_k+\sum_{k=1}^{22}\frac{2^{22}}{x_k}\le 2^{24}-2^{12}-2$$Thus $$\left(\sum_{k=1}^{22}x_k\right)\left(\sum_{k=1}^{22}\frac{1}{x_k}\right)\le \frac {1}{4\cdot 2^{22}}\left(\sum_{k=1}^{22}x_k+\sum_{k=1}^{22}\frac{2^{22}}{x_k}\right)^2\le (2^{12}-1-2^{-11})^2$$and the maximum can be reached when $x_k=2^{k-1}$ for $k=1,2,\cdots,11$ and $x_k=2^k$ for $k=12,13,\cdots,22$.