What is the maximum value of the expression?

Algebra Level 4

Find the maximum value (to 3 decimal places) of
a b + b c + c d a 2 + b 2 + c 2 + d 2 \frac {ab + bc + cd}{a^2 + b^2 + c^2 + d^2} for reals a a , b b , c c , and d d which are not all zero.


The answer is 0.809.

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.

2 solutions

Shourya Pandey
Mar 12, 2017

Relevant wiki: Arithmetic Mean - Geometric Mean

We split a 2 + b 2 + c 2 + d 2 a^2+b^2+c^2+d^2 as

( a 2 + λ b 2 ) + ( ( 1 λ ) b 2 + ( 1 λ ) c 2 ) + ( λ c 2 + d 2 ) (a^2+ \lambda b^2) +((1-\lambda)b^2 + (1-\lambda)c^2)+(\lambda c^2 + d^2) , for some λ \lambda in ( 0 , 1 ) (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 a^{2} + b^{2} + c^{2} + d^{2} \geq 2\sqrt{\lambda} ab + 2(1-\lambda) bc + 2\sqrt{\lambda} cd . Now we choose a lambda such that 2 λ = 2 ( 1 λ ) 2\sqrt{\lambda} = 2(1-\lambda) , which simplifies to

λ 2 3 λ + 1 = 0 \lambda^{2} -3\lambda + 1 =0 , and the root that lies in ( 0 , 1 ) (0,1) is λ = 3 5 2 \lambda = \frac{3-\sqrt{5}}{2} . For this value , we get 2 λ = 2 ( 1 λ ) = 5 1 2\sqrt{\lambda} = 2(1-\lambda) = \sqrt{5} -1 , so

a b + b c + c d a 2 + b 2 + c 2 + d 2 1 5 1 = 5 + 1 4 = 0.809 \frac{ab+bc+cd}{a^2+b^2+c^2+d^2} \leq \frac{1}{\sqrt{5} -1} = \frac {\sqrt{5} +1}{4} = 0.809 .

Equality holds iff a = λ b a= \sqrt{\lambda }b , b = c b=c and a = d a=d , i.e. b = c = k b=c=k and a = d = ( 5 1 ) k 2 a= d= \frac{(\sqrt{5}-1)k}{2} for any positive real k k .

Moderator note:

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 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 1 2 a 2 + 1 2 b 2 , b c 1 2 b 2 + 1 2 c 2 , c d 1 2 c 2 + 1 2 d 2 , ab \leq \frac{1}{2} a^2 + \frac{1}{2}b^2, \quad bc \leq \frac{1}{2} b^2 + \frac{1}{2} c^2, \quad cd \leq \frac{1}{2} c^2 + \frac{1}{2} d^2 , then all we obtain is a b + b c + c a 1 2 a 2 + b 2 + c 2 + 1 2 d 2 . ab + bc + ca \leq \frac{1}{2} a^2 + b^2 + c^2 + \frac{1}{2} d^2.

We have to relax this further to a 2 + b 2 + c 2 + d 2 \leq 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 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 , ab + bc + cd \leq \lambda_1 a^2 + \lambda_1 b^2 + \lambda_1 c^2 + \lambda_1 d^2 ,

to conclude that the maximum is indeed λ 1 \lambda_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 . ab \leq \lambda_1 a^2 + \lambda_2 b^2, \quad bc \leq (\lambda_1 - \lambda_2) b^2 + \lambda_3 c^2, \quad cd\leq ( \lambda_1 - \lambda_3) c^2 + \lambda_1 d^2 .

From here, do you see how to determine the values of λ i \lambda_i using the equality conditions?

I am not being able to follow through your solution. Could you please explain these steps?

  • Why are we splitting up a 2 + b 2 + c 2 + d 2 a^2 + b^2 + c^2 + d^2 as ( a 2 + λ b 2 ) + ( ( 1 λ ) b 2 + ( 1 λ ) c 2 ) + ( λ c 2 + d 2 ) (a^2+ \lambda b^2) +((1-\lambda)b^2 + (1-\lambda)c^2)+(\lambda c^2 + d^2) ? Could you please explain the motivation here?
  • How are we applying the applying the arithmetic mean geometric mean inequality here?
  • Why are we choosing a λ \lambda satisfying 2 λ = 2 ( 1 λ ) 2\sqrt{\lambda} = 2(1-\lambda) ?

Agnishom Chattopadhyay - 4 years, 3 months ago

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 \lambda_1 = \lambda_3 (from the previous point).


Calvin Lin Staff - 4 years, 3 months ago

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?

Agnishom Chattopadhyay - 4 years, 2 months ago

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 a:b:c:d = \sqrt5 - 1 : 2 + \sqrt 3 : 2 + \sqrt 3 : \sqrt 5 - 1 (assuming I got the ratios right...) to get this approach.

Pi Han Goh - 4 years, 3 months ago

Wondering if anybody noticed that 0.809... is half the golden ratio?

Terence Rudkin - 4 years, 2 months ago

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 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..

Vishal Yadav - 4 years, 3 months ago

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 - (x+1)^2 - (x-1)^2 \leq - 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 - (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 .

Calvin Lin Staff - 4 years, 3 months ago

Log in to reply

Surely a partial derivative w.r.t a,b,c and d would demonstrate it as a maximum value.

Malcolm Rich - 4 years, 2 months ago

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 a, b, c, d such that a b + b c + c a a 2 + b 2 + c 2 + d 2 = 1 \frac{ ab+bc+ca} { a^2+b^2+c^2 + d^2 } = 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.

Calvin Lin Staff - 4 years, 2 months ago

Sorry my typo, it was setting a , d = 0 a,d =0

Vishal Yadav - 4 years, 3 months ago

Log in to reply

I doubt that the max value is 1. Tell me what are your values of a,b,c,d...

Pi Han Goh - 4 years, 2 months ago

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.

subh mandal - 4 years, 2 months ago

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.

Agnishom Chattopadhyay - 4 years, 2 months ago

I've added a note to demystify what is happening, and how one could arrive at such a solution.

Calvin Lin Staff - 4 years, 2 months ago

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.

Utkarsh Kulshrestha - 4 years, 2 months ago

Log in to reply

Why must the numbers be equal?

Pi Han Goh - 4 years, 2 months ago

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.

Terence Rudkin - 4 years, 2 months ago

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 a b = λ = 5 1 2 \frac{a} {b}= \sqrt{\lambda} = \frac{ \sqrt{5}-1}{2} . Then, the best way to approximate these using integers would be through the Fibonacci sequence .

Calvin Lin Staff - 4 years, 2 months ago

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.

Srikanth Tupurani - 2 years, 1 month ago
Abhishek Sinha
Mar 18, 2017

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 1 2 k \frac{1}{2k} such that the following inequality holds, for all real x = ( a , b , c , d ) \mathbf{x}'=(a,b,c,d) , not all zero a 2 + b 2 + c 2 + d 2 2 k ( a b + b c + c d ) . a^2+b^2+c^2+d^2 \geq 2k(ab+bc+cd). Transposing, we need the quadratic form x M ( k ) x 0 , \mathbf{x}' \mathbf{M(k)} \mathbf{x} \geq 0, where the matrix M ( k ) \mathbf{M(k)} is given by M ( k ) = ( 1 k 0 0 k 1 k 0 0 k 1 k 0 0 k 1 ) \mathbf{M}(k)=\begin{pmatrix} 1 & -k & 0 & 0 \\ -k & 1 & -k & 0 \\ 0 & -k & 1 & -k \\ 0 & 0 & -k & 1 \end{pmatrix} 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 ) \mathbf{M}(k) as follows λ min ( k ) = 1 k 3 + 5 2 , \lambda_{\textrm{min}}(k)= 1- k\sqrt{\frac{3+\sqrt{5}}{2}}, which is required to be non-negative. This yields, 1 2 k 5 + 1 4 , \frac{1}{2k} \geq \frac{\sqrt{5}+1}{4}, 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.

Calvin Lin Staff - 4 years, 2 months ago

this is clearly related with fibonacci and golden ratio

aaaaaaa aaaaaa - 4 years, 2 months ago

Log in to reply

I don't see the connection. How is Fibonacci/Golden Ratio related to this AMGM question?

Pi Han Goh - 4 years, 2 months ago

Log in to reply

The answer resembles the golden ratio..☺☺

Spandan Senapati - 4 years, 2 months ago

Log in to reply

@Spandan Senapati Yeah, the answer is ϕ 2 \frac \phi 2 , but that could be a coincidence right? It doesn't imply that it's related to the concept of golden ratios.

Pi Han Goh - 4 years, 2 months ago

Log in to reply

@Pi Han Goh Yes I agree with you..

Spandan Senapati - 4 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...