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
30.03.2022 08:59
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.