Find the maximum value (to 3 decimal places) of
a
2
+
b
2
+
c
2
+
d
2
a
b
+
b
c
+
c
d
for reals
a
,
b
,
c
, and
d
which are not all zero.
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.
This is a great example of Applying AM-GM after rearranging creatively . When you first read the solution, you might think to yourself "I would never be able to create this". This note breaks down how one could come up with such a solution, by just thinking about what is it that we need.
Because the terms are not cyclic, the naive approach of a = b = c = d would likely not work (which is why the answer is not 3/4). Furthermore, if we naively used AM-GM: a b ≤ 2 1 a 2 + 2 1 b 2 , b c ≤ 2 1 b 2 + 2 1 c 2 , c d ≤ 2 1 c 2 + 2 1 d 2 , then all we obtain is a b + b c + c a ≤ 2 1 a 2 + b 2 + c 2 + 2 1 d 2 .
We have to relax this further to ≤ a 2 + b 2 + c 2 + d 2 , which tells us that 1 is an upper bound, but it's very likely that it's not achieved (unless a = d = 0 ).
Instead, what we want to end up with after summing the inequalities is
a b + b c + c d ≤ λ 1 a 2 + λ 1 b 2 + λ 1 c 2 + λ 1 d 2 ,
to conclude that the maximum is indeed λ 1 . To order to get there, we should instead use the inequalities
a b ≤ λ 1 a 2 + λ 2 b 2 , b c ≤ ( λ 1 − λ 2 ) b 2 + λ 3 c 2 , c d ≤ ( λ 1 − λ 3 ) c 2 + λ 1 d 2 .
From here, do you see how to determine the values of λ i using the equality conditions?
I am not being able to follow through your solution. Could you please explain these steps?
Log in to reply
@Agnishom Chattopadhyay @Pi Han Goh @Shourya Pandey
Having solved this problem in the past, I understand the frustration of trying to figure out what is going on / why this works. This is a good example of why it's helpful to consider how best to present a solution, especially if we consider the POV of a person who couldn't solve this problem.
A good way of explaining it is:
1. Quick explanation about why the naive AM-GM doesn't work (E.g. Vishal's comment). Maybe explain that it fails because the numerator isn't cyclic.
2. Explain what the modifications that we're making to AM-GM are. In fact, using 3 different lambda parameters would be best.
3. Explain how to choose the value of lambda. In particular, this would be a good time to explain why
λ
1
=
λ
3
(from the previous point).
Log in to reply
I do not really understand how one would actually go about trying the naive AM-GM. Would this be possible if the numerator actually were cyclic?
I agree with Agnishom. Can you explain why you partition the terms in such a way?
Forgive me if I'm wrong, but it seems to me that you have reversed engineered the ratio a : b : c : d = 5 − 1 : 2 + 3 : 2 + 3 : 5 − 1 (assuming I got the ratios right...) to get this approach.
Wondering if anybody noticed that 0.809... is half the golden ratio?
Is it the Maxima ??
If we consider A.M G.M for 'ab', 'bc','ca' individually and further divide by a 2 + b 2 + c 2 + d 2 . We see that setting b,c = 0, yields maximum value = 1.
I have a solution but couldn't find way to upload the image..
Log in to reply
With inequalities, as always you have to show that
1. This value is an upper bound.
2. This value can be achieved.
This then shows that we have a maximum, which is the lowest upper bound.
What you've done is only part 1, showing that 1 is an upper bound on the expression. In order for it to truly be the maximum, what you further need is to determine the equality condition, or explain why no lower value cannot be an upper bound.
As an explicit example, while it's obvious that − ( x + 1 ) 2 − ( x − 1 ) 2 ≤ − 0 − 0 = 0 , this only shows that 0 is an upper bound on the expression. It is not the maximium possible value of − ( x + 1 ) 2 − ( x − 1 ) 2 .
Note: Because this problem is featured in Problems of the Week, it is very unlikely that the equality condition occurs when all the variables are equal. You can read up on inequalities with strange equality conditions .
Log in to reply
Surely a partial derivative w.r.t a,b,c and d would demonstrate it as a maximum value.
Log in to reply
@Malcolm Rich – Not always, depends on how it is done. My comment is more targeted at those who "found an upper bound" but often have not demonstrated that it is the least upper bound. My claim is "There are no values of a , b , c , d such that a 2 + b 2 + c 2 + d 2 a b + b c + c a = 1 ". IE This value of 1 cannot be achieved. As such, we cannot talk about the properties of this non-existent point.
If we have a given point, we could check the partial derivatives to determine if we have a local extrema. Unfortunately, this doesn't tell us if it is a global extrema, and thus further work still needs to be done. To pursue this approach, one would (likely) take the lagrange multipliers approach and verify that the various conditions hold, esp boundary conditions.
Sorry my typo, it was setting a , d = 0
Log in to reply
I doubt that the max value is 1. Tell me what are your values of a,b,c,d...
I think I won't be ever able to split this up like this ,I don't know why I am never able to do this kind of sum.
Log in to reply
Maybe you can share your initial thoughts on the problem with us, then we could help you to move forward with them.
I've added a note to demystify what is happening, and how one could arrive at such a solution.
For those who are asking the reason behind √2x=2(1-x) the reason is to get maximum value all of the numbers must be equal.
Wrote a simple program to help convince myself. To make is simple I looped integers for a,b,c,d and output any new maximum is reached. I get this numbers <= 20:
1 | 1 | 1 | 1 | 7.5E-001 |
1 | 2 | 2 | 1 | 8.0000000000000004E-001 |
2 | 3 | 3 | 2 | 8.0769230769230771E-001 |
3 | 5 | 5 | 3 | 8.0882352941176472E-001 |
5 | 8 | 8 | 5 | 8.089887640449438E-001 |
8 | 13 | 13 | 8 | 8.0901287553648071E-001 |
What I find interesting, but not surprised, that it is the Fibonacci sequence. Conjecture restricting to integers and given a constrained limit the maxima will have two of the factors will be the largest Fibonacci number less then the limit and two will be next smaller Fibonacci number.
Log in to reply
So, this is a case where the observation is better explained by the solution, as opposed to offering a possible approach that we can understand. IE if you look at the solution, we require b a = λ = 2 5 − 1 . Then, the best way to approximate these using integers would be through the Fibonacci sequence .
This kind of trick is common in inequalities. Using a parameter lambda. It is difficult to get this idea. When people see this problem they think of using multivariable calculus.
Here is an alternative, linear-algebraic way to solve the problem, which does not involve any parameter tuning. Restated, the problem is to find the minimum value of 2 k 1 such that the following inequality holds, for all real x ′ = ( a , b , c , d ) , not all zero a 2 + b 2 + c 2 + d 2 ≥ 2 k ( a b + b c + c d ) . Transposing, we need the quadratic form x ′ M ( k ) x ≥ 0 , where the matrix M ( k ) is given by M ( k ) = ⎝ ⎜ ⎜ ⎛ 1 − k 0 0 − k 1 − k 0 0 − k 1 − k 0 0 − k 1 ⎠ ⎟ ⎟ ⎞ which is equivalent to requiring that its minimum eigenvalue be non-negative. Solving the characteristic equation, we readily obtain the minimum eigenvalue of M ( k ) as follows λ min ( k ) = 1 − k 2 3 + 5 , which is required to be non-negative. This yields, 2 k 1 ≥ 4 5 + 1 , with the lower-bound clearly attainable.
Very nice indeed. Turning quadratic inequalities into quadratic forms and representing them via matrices and then using he eigenvectors/values to help us complete the square.
this is clearly related with fibonacci and golden ratio
Log in to reply
I don't see the connection. How is Fibonacci/Golden Ratio related to this AMGM question?
Log in to reply
The answer resembles the golden ratio..☺☺
Log in to reply
@Spandan Senapati – Yeah, the answer is 2 ϕ , but that could be a coincidence right? It doesn't imply that it's related to the concept of golden ratios.
Problem Loading...
Note Loading...
Set Loading...
Relevant wiki: Arithmetic Mean - Geometric Mean
We split a 2 + b 2 + c 2 + d 2 as
( a 2 + λ b 2 ) + ( ( 1 − λ ) b 2 + ( 1 − λ ) c 2 ) + ( λ c 2 + d 2 ) , for some λ in ( 0 , 1 ) , and apply the AM-GM inequality to get
a 2 + b 2 + c 2 + d 2 ≥ 2 λ a b + 2 ( 1 − λ ) b c + 2 λ c d . Now we choose a lambda such that 2 λ = 2 ( 1 − λ ) , which simplifies to
λ 2 − 3 λ + 1 = 0 , and the root that lies in ( 0 , 1 ) is λ = 2 3 − 5 . For this value , we get 2 λ = 2 ( 1 − λ ) = 5 − 1 , so
a 2 + b 2 + c 2 + d 2 a b + b c + c d ≤ 5 − 1 1 = 4 5 + 1 = 0 . 8 0 9 .
Equality holds iff a = λ b , b = c and a = d , i.e. b = c = k and a = d = 2 ( 5 − 1 ) k for any positive real k .