Minimum Sum Value
Let y 1 , y 2 , y 3 , … , y 8 be a permutation of the numbers 1 , 2 , 3 , … , 8 . What is the minimum value of i = 1 ∑ 8 ( y i + i ) 2 ?
The answer is 648.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
7 solutions
Equality holds for y 1 + 1 = y 2 + 2 = ⋯ = y 8 + 8 ⇒ y i = 9 − i for i ∈ { 1 , 2 , ⋯ , 8 } .
The same can be achieved using rearrangement inequality
What are y's I do get the idea of permutations of the numbers ?
I used the Root-Mean Square-Arithmetic Mean Inequality. I think it is simpler. The inequality rule gives that:
8 ∑ i = 1 8 ( y i + i ) 2 ≥ 8 ∑ i = 1 8 ( y i + i )
Squaring both sides, 8 ∑ i = 1 8 ( y i + i ) 2 ≥ ( 8 ∑ i = 1 8 ( y i + i ) ) 2 = ( 9 ) 2 = 8 1
⇒ ∑ i = 1 8 ( y i + i ) 2 ≥ 8 1 × 8 = 6 4 8
In fact equality happens when the terms on both sides of the inequality are the same, that is RMS=AM. This happens when y i + i = 9 .
When 8 ∑ i = 1 8 9 2 = 9 = 8 ∑ i = 1 8 9 and ∑ i = 1 8 ( y i + i ) 2 = 6 4 8
Rearrangement or titu's lemma will strike easily, but this won't. Great solution, as always.
Did in this way only.A good approach.
My solution is not as elegant as others. By rearrangement inequality ,we can see that the sum is minimal when we set y1=8 .........y8=1 And then we can see the magic happen.as the sum would be S= 8×9^2=648
No other theorems are necessary for this problem! Hint: i = 1 ∑ 8 ( y i + i ) 2 = ∑ y i 2 + ∑ i 2 + 2 ∑ ( y i ⋅ i ) Observe that the first two sums are equal, and independent of the permutation, sum of squares from 1 to 8. So we are left trying to minimize i = 1 ∑ 8 ( y i ⋅ i ) , and here we can apply rearragement inequality.
Responding to your first sentence: Isn't the rearrangement inequality a theorem?
My bad, I saw this problem on the Rearrangment Inequality page, so I assumed it was an exercise for that section. I was confused why more complicated theorems were used in other commenter's solutions.
Log in to reply
Ah. The problems could appear in any wiki, so there could be multiple ways of approaching them (esp for inequalities).
This solution uses the AM-GM Inequality.
By AM-GM Inequality, 8 ∑ i = 1 8 ( y i + i ) 2 ≥ 8 ∏ i = 1 8 ( y i + i ) 2 .
From this, we derive ∑ i = 1 8 ( y i + i ) 2 ≥ 8 4 ∏ i = 1 8 ( y i + i ) .
Equality is achieved when all y i + i = 9 .
Hence, min ( ∑ i = 1 8 ( y i + i ) 2 ) = 8 4 ∏ i = 1 8 9 = 8 × 9 8 / 4 = 6 4 8 .
There is a flaw.
Just because equality occurs when all are 9 does not mean it gives the minimum. For example what is the minimum value of x + y + y when x y = 1 ? If we say that since
x + y + y ≥ 3 ( x y z ) 3 1 and equality thus occurs at x=y then the answer will be wrong. Also the value of the geometric mean has a loose lower bound which will not give the answer.
Using rearrangement inequality.
( 8 + 1 ) 2 + ( 7 + 2 ) 2 + ( 6 + 3 ) 2 + . . . + ( 1 + 8 ) 2 = 8 ∗ 9 2 = 6 4 8
In your own words, why do you think that gives us the minimum?
Log in to reply
I think if yi=1,2,3,4,5,6,7,8 such that
(
1
+
1
)
2
+
(
2
+
2
)
2
+
(
3
+
3
)
2
+
.
.
.
+
(
8
+
8
)
2
=
4
∗
(
1
/
6
)
∗
(
8
+
1
)
(
2
∗
8
+
1
)
=
8
1
6
is the maximum .
It follows by Rearrangement inequality or Greediness algorithm doesn't it? Pairing the maximum of one series and the minimum of another series gives us the least summation than all other permutations possible.
Log in to reply
Not necessarily so, further justification is required.
For example, the proper justification relies on the concaveness of the quadratic function. E.g. if we were minimizing ∑ sin ( y i + i ) , we do not necessarily want to pair up "max with min".
We use Titu's lemma. ( y 1 + 1 ) 2 + ( y 2 + 2 ) 2 + . . . + ( y 8 + 8 ) 2 = 1 ( y 1 + 1 ) 2 + 1 ( y 2 + 2 ) 2 + . . . + 1 ( y 8 + 8 ) 2
≥ 1 + 1 + . . . + 1 ( y 1 + 1 + y 2 + 2 + . . . + y 8 + 8 ) 2
= 8 [ 2 ( 1 + 2 + . . . + 8 ) ] 2 = 8 7 2 2 = 6 4 8
Q.E.D.