0
$\begingroup$

If $x_1+x_2+x_3+x_4+x_5+x_6+x_7+x_8 = 1$ and $x_1,x_2,x_3,x_4,x_5,x_6,x_7 \text{ and }x_8$ are non-negative, then what is the minimum value of $\max(x_1+x_2+x_3, x_2+x_3+x_4, x_3+x_4+x_5, x_4+x_5+x_6, x_5+x_6+x_7, x_6+x_7+x_8)$?

I was not able to solve this problem but when I saw the hint that was provided for this problem mentioned that the minimum occurs when $x_1=x_2=x_3=x_4=x_5=x_6=x_7=x_8$ which makes all values equal to $\frac{1}{8}$ and thus the minimum of the maximum function will be $\frac{3}{8}$.

But I am not able to derive or understand the concept as to why only at this condition. Please help me on this !!! Is there any way we can prove this that indeed the minimum will occur when all the values will be equal.

Thanks in advance !!!

$\endgroup$
5
  • $\begingroup$ The flawed reasoning might be that without loss of generality, $x_1 \geq x_2 \geq \cdots \geq x_8$, and therefore the max of all the terms is $(x_1 + x_2 + x_3) \geq (3/8)$. The flaw is that although the $8$ variables can be ranked in descending order, the constraints are not symmetric with respect to the $8$ variables. As demonstrated by the answer of Rob Pratt, the assumption that the $3$ largest variables are $x_1, x_4, x_8$ refutes my flawed analysis. ...see next comment $\endgroup$ Commented Sep 18, 2021 at 17:56
  • $\begingroup$ Did you maybe leave out $x_7+x_8+x_1$ and $x_8+x_1+x_2$? Making that change would indeed yield $3/8$ as the minimum. $\endgroup$
    – RobPratt
    Commented Sep 18, 2021 at 17:57
  • $\begingroup$ @RobPratt Re my previous comment, what I was going to say is that there are $\binom{8}{3} = 56$ trinomials that can be formed. If the problem had been to minimize the maximum of all $56$ trinomials, then the reasoning in my previous comment would have been valid. Rob Pratt's comment (above) might also be valid, but I think that it would take some proving. $\endgroup$ Commented Sep 18, 2021 at 17:59
  • $\begingroup$ The proof that $3/8$ is optimal if you include all $8$ consecutive trinomials (with wrapround) is to multiply constraint $(1)$ by $3/8$ and each constraint $(2)$ by $1/8$. Equivalently, apply the principle that the maximum is at least the average and substitute $\sum_j x_j = 1$. $\endgroup$
    – RobPratt
    Commented Sep 18, 2021 at 18:20
  • $\begingroup$ @RobPratt Nice touch. If it were me, I would add your last comment (et al) to the end of your answer. $\endgroup$ Commented Sep 18, 2021 at 19:01

3 Answers 3

4
$\begingroup$

The minimum is $1/3$, attained by $x=(1/3,0,0,1/3,0,0,0,1/3)$. To prove that $1/3$ is a lower bound, consider the following linear programming formulation. The problem is to minimize $z$ subject to \begin{align} \sum_j x_j &= 1 \tag1\\ z - (x_j + x_{j+1} + x_{j+2}) &\ge 0 &&\text{for $j \le 6$} \tag2\\ x_j &\ge 0 &&\text{for all $j$} \tag3 \end{align} Multiply constraint $(1)$, the first, third, and sixth of constraint $(2)$, and the third of constraint $(3)$ by $1/3$ to obtain $$\frac{x_1+x_2+x_3+x_4+x_5+x_6+x_7+x_8}{3}+\frac{z-(x_1+x_2+x_3)}{3}+\frac{z-(x_3+x_4+x_5)}{3}+\frac{z-(x_6+x_7+x_8)}{3}+\frac{x_3}{3} \ge \frac{1}{3},$$ which simplifies to $$z \ge \frac{1}{3}.$$

$\endgroup$
2
$\begingroup$

Since $(x_1 + x_2 + x_3 ) + (x_4 + x_5 + x_6) + (x_6 + x_7 + x_8) = 1 + x_6$, hence the maximum of these 3 terms is at least $ \frac{ 1+x_6 } { 3} \geq \frac{1}{3}$.
Hence the maximum of all the 6 terms is at least $ \frac{1}{3}$.

Since we can find a sequence with $ x_ 1 = x_4 = x_7 = 1/3, x_i = 0 $ otherwise which gives us a maximum of 1/3, hence the minimum of the maximum is indeed $1/3$.

$\endgroup$
0
$\begingroup$

It is not true.
To balance, the six sums might all be equally large. So $x_1+x_2+x_3=x_2+x_3+x_4$, so $x_1=x_4$. Similarly, $x_1=x_4=x_7$, $x_2=x_5=x_8$, and $x_3=x_6$. By left-right symmetry, I expect $x_1=x_8$.
Now the 8 numbers are $y,y,z,y,y,z,y,y$. All sums are $2y+z$ subject to $6y+2z=1$, $2y+z=(1+z)/3$, which is minimized when $y=1/6,z=0$.
I have made a couple of guesses, but ended with a lower answer than $3/8$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .