Given a positive integer $n$, find all $n$-tuples of real number $(x_1,x_2,\ldots,x_n)$ such that \[ f(x_1,x_2,\cdots,x_n)=\sum_{k_1=0}^{2} \sum_{k_2=0}^{2} \cdots \sum_{k_n=0}^{2} \big| k_1x_1+k_2x_2+\cdots+k_nx_n-1 \big| \]attains its minimum.
Problem
Source: 2022 China TST, Test 2, P4
Tags: algebra, inequalities, function, absolute value
CANBANKAN
30.03.2022 08:59
The answer is $x_1=\cdots=x_n=\frac{1}{n+1}$ only.
Claim: minimum holds when and only when $x_i$'s are equal.
Proof: Let $y=\frac{x_1+x_2}{2}$. I will prove that $f(x_1,x_2,x_3,\cdots,x_n)\ge f(y,y,x_3,\cdots,x_n)$
Note for any $k,m,c\in \mathbb{R}$, $|kx_1+mx_2+c|+|mx_1+kx_2+c|\ge |(k+m)(x_1+x_2)+2c|=|ky+my+c|+|my+ky+c|$ by triangular inequality.
Applying the above inequality, letting $c=\sum\limits_{j=3}^n k_jx_j-1$ and summing over all $c$ for all $(k_3,\cdots,k_n) \in \{0,1,2\}^{n-2}$ where $k_1\ne k_2$ gives the desired result.
Now, let $x_1=\cdots=x_n=x$, and we need to minimize $g(x)=f(x,x,x,\cdots,x)$. Let $H(n,t)$ be the number of solutions to $k_1+\cdots+k_n=t$ where $k_j\in \{0,1,2\}$ for $j=1,\cdots,n$. Observe that $H(n,t)\le H(n,n)$ and $H(n,t)=H(n,2n-t)$.
Therefore, $g(x)=\sum\limits_{j=0}^{2n} H(n,j) |jx-1|=\sum\limits_{j=0}^{2n} jH(n,j) |x-\frac 1j|$
Claim: $g(x)$ is minimized at $x=\frac{1}{n+1}$
Proof: Will do later.
It remains to show $x_1=x_2$ is forced. In the smoothing process, I cannot make any moves that produce a smaller sum. If $x_1=x_2$ we get there exists $k_1\ne k_2, k_1x_1+\cdots+k_nx_n=1$. Now, let $y_1,y_2$ st $y_1+y_2=2x_1$. Then $|k_1y_1+k_2y_2+k_3x_3+\cdots+k_nx_n-1| + |k_2y_1+k_1y_2+k_3x_3+\cdots+k_nx_n-1| > 2|k_1x_1+k_2x_2+k_3x_3+\cdots+k_nx_n-1|$, so the $x_i$'s must be constant.
naman12
14.04.2022 11:52
Good problem. We claim that the minimum happens only when $x_k=\frac 1{n+1}$ for all $1\leq k\leq n$. For the rest of the proof, assume $(x_1,x_2,\ldots,x_n)$ is a triple achieving the minimum. We get rid of the case $n=1$, where $f(x)=1+|x-1|+|2x-1|$. Writing it out as a piece wise function, we easily see that the minimum is at $\frac 12$. For the rest, we assume $n\geq 2$. First, we reduce the problem to having all of the $x_k$ equal. Indeed, we know \begin{align*} f(x_1,x_2,\cdots,x_n)&=\sum_{k_1=0}^{2} \sum_{k_2=0}^{2} \cdots \sum_{k_n=0}^{2} \big| k_1x_1+k_2x_2+\cdots+k_nx_n-1 \big|\\ &= \frac 12\sum_{k_1=0}^{2} \sum_{k_2=0}^{2} \cdots \sum_{k_n=0}^{2} \left(\big| k_1x_1+k_2x_2+\cdots+k_nx_n-1 \big|+ \big| k_2x_1+k_1x_2+\cdots+k_nx_n-1 \big|\right)\\ &\geq \sum_{k_1=0}^{2} \sum_{k_2=0}^{2} \cdots \sum_{k_n=0}^{2} \left| k_1\cdot\frac{x_1+x_2}2+ k_1\cdot\frac{x_1+x_2}2+k_3x_3\cdots+k_nx_n-1 \right|\quad(1)\\ &=f\left(\frac{x_1+x_2}2, \frac{x_1+x_2}2,x_3,x_n\right) \end{align*}so if $nx=\sum\limits_{k=1}^n x_k$, then \[f(x_1,x_2,\ldots,x_n)\geq f(x,x,\ldots,x)\tag{2}\] Now, assuming all of the $x_k$ are equal, this problem is equivalent to minimizing \[\sum_{k_1=0}^{2} \sum_{k_2=0}^{2} \cdots \sum_{k_n=0}^{2} \left| x\sum_{j=1}^n k_j-1 \right|\]For $0\leq j\leq 2n$, let $t_j$ be the number of ordered $n$-tuples $(k_1,\ldots,k_n)\in\{0,1,2\}^n$ with \[\sum_{m=1}^n k_m=j\]Note that by definition, \[\sum t_jx^j=(1+x+x^2)^n\] Now, to find the minimum, we can note that $f$ is a piece wise function of $x$, and each part is linear. In addition, the slope is clearly increasing (as a single term $t_j|jx-1|$ goes from $-t_jjx$ to $t_jjx$). Thus, we look for where the slope changes from negative to positive (say at $j$), and then $x=\frac 1j$ is our minimum. We claim $j=n+1$. This requires us to show that \[\sum_{m=0}^nmt_m<\sum_{m=n+1}^{2n}mt_m\qquad \sum_{m=0}^{n+1}mt_m>\sum_{m=n+2}^{2n}mt_m\tag{3}\]First, we note $mt_m$ are the coefficients of $x^{m-1}$ in $\frac{\mathrm d}{\mathrm dx}(1+x+x^2)$, which is $n$ times \[g_n(x)=(2x+1)(1+x+x^2)^{n-1}\]We shall prove the following claim: Claim. Let $u_{n,j}$ be the coefficient of $x^j$ in $g(x)$. Then \[u_{n,j}<u_{n,2n-1-j}\qquad 0\leq j\leq n-1\]and \[u_{n,j}>u_{n,2n-j}\qquad 1\leq j\leq n\]Proof. We proceed by induction on $n$: Base Case. $n=2$. Then $g_2(x)=2+6x+6x^2+4x^3$ which satisfies our claim. Induction Hypothesis. Assume the claim is true for some $n=m\geq 1$. We show it for $n=m+1$. Induction Step. We know $g_{m+1}(x)=(1+x+x^2)g_m(x)$, so \[u_{m+1,j}=u_{m,j-2}+u_{m,j-1}+u_{m,j}\]Thus, the first inequality is true as \begin{align*} u_{m+1,j}&=u_{m,j-2}+u_{m,j-1}+u_{m,j}\\ &< u_{m,2m-j-1}+u_{m,2m-j}+u_{m,2m-j+1}=u_{m+1,2(m+1)-j-1} \end{align*}which follows by just applying the induction hypothesis and checking bounds to make sure that at least one of the equalities fail. The similar idea works for the second. $\square$ $(3)$ follows by adding our claim until it is satisfied. Thus, we must have equality at $x=\frac 1{n+1}$. Now, this means that all the numbers sum to $\frac n{n+1}$. This means if $x_1\leq x_2\leq\cdots\leq x_n$, we have $x_1\leq \frac 1{n+1}$. First, suppose $n=2$. Then because $(1)$ needs to hold, we know $x_1+2x_2-1$ and $x_2+2x_1-1$ have the same sign, but they sum to $0$, so they are $0$, as desired. We now write down the chain of equalities in the form of $(2)$ in the form of \begin{align*} f(x_1,\ldots,x_n)&\geq f\left(x_1,\ldots,x_{n-2},x,\frac 1{n+1}\right)\\ &\geq f\left(x_1,\ldots,x_{n-3},x,\frac 1{n+1}, \frac 1{n+1}\right)\\ &\vdots\\ &\geq f\left(x_1,x,\frac 1{n+1}, \ldots,\frac 1{n+1}\right)\\ &\geq f\left(\frac 1{n+1},\ldots,\frac 1{n+1}\right) \end{align*}where $x$ is arbitrary to make the average $\frac 1{n+1}$. We know all of these are equalities, and thus must the last one. However, we know that this means all the inequalities in the form $(1)$ are true, so for all $(k_1,\ldots,k_n)\in\{0,1,2\}^n$, \[k_1x_1+k_2x_2+\cdots+k_nx_n\qquad k_2x_1+k_1x_2+\cdots+k_nx_n\]have the same sign. Taking $k_2=\cdots k_{n-1}=1$ and $k_1=k_n=2$ gives the numbers $\frac 1{n+1}-x_1,\frac 1{n+1}-x$, but as these sum to 0, they must be 0. Thus $x_1$ is the average, so all numbers are the average This completes the proof.