Cyclic Expressions Often Have Obvious Solutions. This One Doesn't.
What is the maximum possible value of the expression i = 1 ∑ 2 0 0 ∣ a i − 2 a i + 1 ∣ , where a 1 , a 2 , … , a 2 0 1 are real numbers such that 1 ≤ a i ≤ 4 for i = 1 to 201?
The answer is 902.
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.
3 solutions
Can you please clarify how you used the assumption that maximum is attained at a i = 1 or 4 ? f here is a convex function of ...? All a i ? Thanks.
Log in to reply
Fix i . Assume that all other a j values are fixed (for j = i ). Then, we want to maximize ∣ A − 2 a i ∣ + ∣ a i − 2 B ∣ . From what we know of this graph, it achieves the maximum at the endpoints. Hence to maximize the function, we must have a i = 1 , 4 .
The place that I used it, was in the induction step. The only cases that I needed to consider was when a 1 , a 2 = 1 or 4.
a
o
d
d
t
o
1
9
9
=1.
a
e
v
e
n
=4.
a
2
0
1
=4.
sum = 100(1-8)+99(2)+4= 902
Why must this be the maximum?
A1-2a2 will be max only when a1 gets the min number and a2 the max . So we get the sum as |-7| i.e 7.. Since a2 is 4 we keep a3 as 1 so that it doesn't affect our next term. When we reach the last term a200 gets 4 , since there is no term next to it we give the value 4 to a201 thus giving us--- 9*100-2+4=902
m a x ( ∣ a i − 2 a i + 1 ∣ ) = ∣ 1 − 4 ∗ 2 ∣ = ∣ 4 ∗ 2 − 1 ∣ = 7 With a group of (1,4,1) can make maximum number in each group. So with sequence of numbers: (1,4),(1,4),...., (1,4), 4 get the maximum value: 9 ∗ 9 9 + 7 + 4 = 9 0 2 .
The solution set is somewhat easy to guess, but it is hard to prove that it is indeed the maximum. We cannot simply attempt to maximize most of the terms, and then hope for the best. (If there were an even number of terms, then this would be much easier.)
Since ∑ i = 1 2 0 0 ∣ a i − 2 a i + 1 ∣ is a convex function, hence the maximum is attained at the endpoints. This implies that a i = 1 or 4.
Define f ( a 1 , a 2 , … , a 2 k + 1 ) = ∑ i = 1 2 k ∣ a i − 2 a i + 1 ∣ .
We can show by induction that if b 1 , b 2 , … b 2 k ∈ { 1 , 4 } then
1. f ( 1 , 1 , b 1 , … , b 2 k − 1 ) ≤ 9 k − 1 .
2. f ( 1 , 4 , b 1 , … , b 2 k − 1 ) ≤ 9 k + 2 .
3. f ( 4 , 1 , b 1 , … , b 2 k − 1 ) ≤ 9 k .
4. f ( 4 , 4 , b 1 , … , b 2 k − 1 ) ≤ 9 k − 2 .
Hence, taking k = 1 0 0 , we get that f ( a 1 , a 2 , … , a 2 k + 1 ) ≤ 9 0 2 .