Basic Math Problem of the Week 12/05/2017

[PF PotW Robot]

Here is this week's basic math problem. We also encourage finding different methods to the solution. If one has been found, see if there is another way. Using spoiler tags is optional. Occasionally there will be prizes for extraordinary or clever methods.

Find the minimum value of $\dfrac{1}{a-b}+\dfrac{1}{b-c}+\dfrac{1}{a-c}$ for all reals $a>b>c$, given $(a-b)(b-c)(a-c)=17$

(PotW thanks to our friends at http://www.mathhelpboards.com/)

 

[StoneTemplePython]

a favorite inequality at work here.

Spoiler

step 1: solve easier problem, i.e. minimize

$\frac{1}{3}\big(\dfrac{1}{a-b}+\dfrac{1}{b-c}+\dfrac{1}{a-c}\big)$

then multiply by 3 at the end
- - - -
notice $(a-b)\gt 0$, $(b-c) \gt 0$, $(a-c) \gt 0$

We can directly interpret this in terms of Harmonic Mean vs Geometric Mean inequalities, or do a change of variables (shown below).

change of variables:

$\gamma_1 = \frac{1}{a-b}$
$\gamma_2 = \frac{1}{b-c}$
$\gamma_3 = \frac{1}{a-c}$our constraint
$(a-b)(b-c)(a-c)=17$
is equivalent to

$\big((a-b)(b-c)(a-c)\big)^{-1}= (a-b)^{-1}(b-c)^{-1}(a-c)^{-1}= \frac{1}{17} = 17^{-1}$

giving us:

$\gamma_1 \gamma_2 \gamma_3 = \frac{1}{17}$

apply key inequality: by $GM \leq AM$

$\frac{1}{17} ^{\frac{1}{3}} = \big(\gamma_1 \gamma_2 \gamma_3\big)^{\frac{1}{3}} \leq \frac{1}{3}\big(\gamma_1 + \gamma_2 + \gamma_3\big)$

Thus the minimum possible expected value is

$\frac{1}{17} ^{\frac{1}{3}}$

which occurs iff

$\gamma_1 = \gamma_2 = \gamma_3 = \frac{1}{17} ^{\frac{1}{3}}$

and the minimum possible value for our expression is that multiplied by 3, giving us:

$\min: \gamma_1 + \gamma_2 + \gamma_3 = 3 \big(\frac{1}{17} ^{\frac{1}{3}}\big)$

'
= = =
edit: a bit of surgery is needed here, as the above approach indicates

(a-b) = (a-c), which is impossible because $b \gt c$
surgery:

by $GM \leq AM$ or convexity arguments, we know:

the expression $(\frac{1}{a-b} + \frac{1}{b-c})$ given a constraint about the product of $(a-b)(b-c)$

is minimized when we have $(a-b) = (b-c)$.

supposing we multiply by some arbitrary $\lambda \gt 0$, consider

$\lambda(\frac{1}{a-b} + \frac{1}{b-c})$ where the constraint is $(a-b)(b-c)\lambda$, and the prescription is the same.

The optimization problem doesn't change if we increase our expression by some additive constant (affine shift), so the prescription is the same where

$\text{Payoff} = \lambda(\frac{1}{a-b} + \frac{1}{b-c}) + 1$

let $\lambda := (a - c) = (a-b) + (b-c) = 2(a-b)$

equivalently $\frac{1}{2}\lambda = a-b = b- c$

our expression is thus

$\lambda(\frac{1}{a-b} + \frac{1}{b-c}) + 1 = \big(\frac{a-c}{a-b} + \frac{a-c}{b-c} + \frac{a-c}{a-c}\big) = (\frac{\lambda}{\frac{1}{2}\lambda} + \frac{\lambda}{\frac{1}{2}\lambda} + \frac{\lambda}{\lambda}\big) = 2 + 2+ 1 = 5$

thus we know $\lambda \text{MinPayoff} = 5$

our product constraint tells us that we have

$(a-b)(b-c)(a-c) = \big(\frac{1}{2}\lambda\big)\big(\frac{1}{2}\lambda\big) \big(\lambda\big) = 17$

thus we know that

$\lambda^3 = 68 \to \lambda = 68^\frac{1}{3}$

plugging back into our expression: $\lambda \text{MinPayoff} = 5$

$\text{MinPayoff} = \frac{5}{\lambda} = \frac{5}{68^\frac{1}{3}} \approx 1.224993$

 

[StoneTemplePython]

a more traditional approach would be to re-write the product constraint as

$(a-b)(b-c)(a-c) = \big(p \lambda\big)\big((1-p)\lambda\big)\big(\lambda\big) = 17$

for some unknown $0 \lt p \lt 1$

solve for

$\lambda = \big(\frac{17}{p(1-p)}\big)^{\frac{1}{3}}$

now consider the payoff function

$\text{ObjectiveFunction} = \frac{1}{p \lambda} + \frac{1}{(1-p) \lambda} + \frac{1}{ \lambda} = \Big( \frac{1}{p} + \frac{1}{(1-p) } + \frac{1}{ 1}\Big)\frac{1}{\lambda} = \Big(\frac{1}{p} + \frac{1}{1-p} + \frac{1}{1}\Big) \big(\frac{p(1-p)}{17}\big)^{\frac{1}{3}}$

we may guess that $p = 0.5$ by symmetry, and we recover the answer above $= \frac{5}{68^\frac{1}{3}} \approx 1.224993$.

Alternatively, we can differentiate $\text{ObjectiveFunction}$ once and get something ugly, but it is easy to plug in $p = \frac{1}{2}$ and confirm that the derivative is zero there.

And we can verify that the second derivative is continuously positive for $p \in (0,1)$ via plotting it. The actual equation is rather horrific. The prior posting under "surgery" is probably a cleaner, albeit indirect, approach.

 

[Delta2]

let $x=a-b , y=b-c$ then $a-c=x+y$ so the problem transforms to $min (\frac{1}{x}+\frac{1}{y}+\frac{1}{x+y})$ given that $xy(x+y)=17$.

Doing some algebra on the function f(x,y) that we want to be minimized we obtain

$min f=min \frac{(x+y)^2+xy}{xy(x+y)}=min \frac{(x+y)^2+xy}{17}$ with the constraints $xy(x+y)=17 , x>0,y>0$

We can plug this directly at wolfram and get the minimum fast and easy as $min f\approx 1.22499$ at $x=y\approx 2.04083$. http://www.wolframalpha.com/input/?i=minimize+((x+y)^2+xy)/17,+xy(x+y)=17

If we are not allowed to use wolfram at all,

we let $z=(x+y)$ then we have

$min (\frac{z^2+\frac{17}{z}}{17})$ with constraint $zx(z-x)=17$ and $z>x>0$,

solving the constraint(quadratic to z) for z>x we get $z=\frac{1}{2}(x+\sqrt\frac{x^3+68}{x})$ so

$min (\frac{z^2+\frac{17}{z}}{17})=min (\frac{\sqrt{x(x^3+68)}}{17}+\frac{1}{x})$ , x>0.
So far we have reduced a minimizing problem with 3 variables to a minimizing problem of 1 variable but still the first derivative is quite ugly, hmm any ideas on finding the minimum of that?

I wonder if using Kuhn-Tucker in the form of f(x,y) or f(z) will work...

 

[Delta2]

OR (since I can't edit my previous post)

I am not sure if i can invoke a symmetry argument, we can see that the objective function $f(x,y)=\frac{(x+y)^2+xy}{17}$ and the constraint $xy(x+y)=17$ are both symmetric in x and y so we can claim that the minimum is at $x=y$ such that $2x^3=17$, $x=(\frac{17}{2})^\frac{1}{3}$ and $min f=\frac{5}{17}x^2$

 

[Buzz Bloom]

so we can claim that the minimum is at x=yx=y

Hi Della:

Could not symmetry also imply that x=y could be a max or a min?

Regards,
Buzz

 

[Delta2]

Hi Della:

Could not symmetry also imply that x=y could be a max or a min?

Regards,
Buzz

Well, it could have been a max instead of a min, but if we plug some other values for x and y that satisfy the constraint, we will see that $f(x,y)>\frac{5}{17}(\frac{17}{2})^{\frac{2}{3}}$

besides, the existence of the minimum is given implicitly as it says "Find the minimum". Otherwise it would say "Prove that a minimum exists and find it".

 

[StoneTemplePython]

This is a sneaky problem that I spent a bit too much time thinking about -- there's a lot of nice structure, with a couple of wrenches that seem to have deliberately been thrown in by the creator.

The case we were given is for $n=2$. Here is a look at the general $n$ case, with particular emphasis on large $n$.
- - - - - - -

The constraint can be written as

$\big(\prod_{j=1}^n x_j\big)\big( \sum_{j=1}^n x_j\big) = c$

where c is some constant --equal to 17 in our problem.

But if we divide each side by $n$ we get

$\gamma^n \mu = \big(\prod_{j=1}^n x_j^\frac{1}{n}\big)^n\big(\frac{1}{n} \sum_{j=1}^n x_j\big) = \big(\prod_{j=1}^n x_j\big)\frac{1}{n}\big( \sum_{j=1}^n x_j\big)= \frac{c}{n}$

where

$\gamma = \prod_{j=1}^n x_j^\frac{1}{n} = \text{GeometricMean}$

$\mu = \frac{1}{n} \sum_{j=1}^n x_j = \text{ArithmeticMean}$

and by $GM \leq AM$, we know

$\gamma \leq \mu$

Key idea: the mismatch in exponents between the geometric mean and the arithmetic mean is what makes the problem interesting.

from here we can repeatedly apply $GM \leq AM$ to get the below relationship:

$\gamma^{n+1} \leq \gamma^n \mu = \frac{c}{n} \leq \gamma^{n-1} \mu^{2} \leq \gamma^{n-2} \mu^{3} \leq ... \leq \mu^{n+1}$

(note this shows a progression one natural number at a time -- there are lots of other ways to show the progression.)

Taking the n+1 root, we get

$\gamma \leq \gamma^{\frac{n}{n+1}} \mu^{\frac{1}{n+1}} = \big(\frac{c}{n}\big)^{\frac{1}{n+1}} \leq \gamma^{\frac{n-1}{n+1}} \mu^{\frac{2}{n+1}} \leq \gamma^{\frac{n-2}{n+1}} \mu^{\frac{3}{n+1}} \leq ... \leq \mu$

and if we invert this, we have

$\prod_{j=1}^n \frac{1}{x_j}^\frac{1}{n} = \frac{1}{\prod_{j=1}^n x_j^\frac{1}{n}} = \frac{1}{\gamma} \geq \big(\frac{n}{c}\big)^{\frac{1}{n+1}} \geq... \geq \frac{1}{\mu} = \frac{1}{\frac{1}{n} \sum_{j=1}^n x_j}$

by one more application of $AM \geq GM$, and multiplying everything by $n$, we get

$\sum_{j=1}^n \frac{1}{x_j} \geq n\prod_{j=1}^n \frac{1}{x_j}^\frac{1}{n} \geq n\big(\frac{n}{c}\big)^{\frac{1}{n+1}} \geq \frac{n^2}{\sum_{j=1}^n x_j}$

While the upper and lower bound are flexible, it's worth pointing out that the $n\big(\frac{n}{c}\big)^{\frac{1}{n+1}}$, which is sandwhiched in between, is constant because any given problem has some fixed $n$ number of terms, and some constant $c$ supplied. Additionally, we know that the equality case occurs iff $x_1 = x_2 = ... = x_n$.

It gets difficult, because the problem then asks us to minimize

$\text{ObjectiveFunction} = \big(\frac{1}{x_1} + \frac{1}{x_2} + ... + \frac{1}{x_n}\big) + \big(\frac{1}{x_1 + x_2 + ... + x_n}\big) = \text{UpperBound} + \frac{1}{n^2} \text{LowerBound}$

which is quite awkward as getting rid of the $\text{LowerBound}$ term here is not easily done. We can of course re-write this as

$\frac{n^2 + 1}{n^2}\text{UpperBound} = \text{UpperBound} + \frac{1}{n^2} \text{UpperBound} \geq \text{ObjectiveFunction} = \text{UpperBound} + \frac{1}{n^2} \text{LowerBound}$

A lazy way out that I'd use in computing is to note that for large $n$, we see

$1 \geq \frac{n^2}{n^2 + 1}\frac{ \text{ObjectiveFunction}}{\text{UpperBound}} = \frac{n^2}{n^2 + 1} + \frac{1}{n^2 + 1} \frac{\text{LowerBound}}{\text{UpperBound}}$

recalling that $0 \leq \frac{\text{LowerBound}}{\text{UpperBound}} \leq 1$

That is our $\text{ObjectiveFunction}$ essentially is the upper bound for large $n$ and we cannot possibly hope to minimize the $\text{ObjectiveFunction}$ unless $\text{UpperBound}$ is minimized which occurs iff $x_1 = x_2 = ... = x_n$

 

[StoneTemplePython]

Here is the closed form, general solution to this problem
- - - - -
edit:
skip to the "edit" comment at the very end for a much more slick solution that takes the prior posting, and in 5 lines gets to a general closed form solution

- - - - -
The minimum value of

$\big(\frac{1}{x_1} + \frac{1}{x_2} + ... + \frac{1}{x_n}\big) + \big(\frac{1}{x_1 + x_2 + ... + x_n}\big)$

given a constraint $\big(\prod_{j=1}^n x_j\big)\big( \sum_{j=1}^n x_j\big) = c$, where each $x_j \gt 0$ and $c \gt 0$

is

$\frac{n^2 + 1}{n} \big(\frac{n}{c}\big)^\frac{1}{n+1}$

for any natural number n

this occurs iff $x_1 = x_2 = ... = x_n$
- - - - -
in our specific problem that gives us

$\frac{5}{2} \big(\frac{2}{17}\big)^\frac{1}{3} = 5 \big(\frac{2}{8*17}\big)^\frac{1}{3} = 5\big(\frac{1}{4*17}\big)^\frac{1}{3} = \frac{5}{68^\frac{1}{3}}$
- - - - -
Full derivation is below. (Long story short, it's just repeated application of $AM \geq GM$ with some extra care to preserve the equality case at each invocation of an upper bound.
- - - - -
the constraint can be written as

$\Big(\prod_{j=1}^n\big(\frac{1}{ x_j}\big)^\frac{1}{n} \Big)^n \frac{1}{ \frac{1}{n}\sum_{j=1}^n x_j} = \Big(\frac{1}{\prod_{j=1}^n x_j}\Big) \Big(\frac{1}{ \frac{1}{n}\sum_{j=1}^n x_j }\Big) = \frac{n}{c}$

take $n + 1$ root and apply $AM \geq GM$
- - - - -
and note that there is equality iff

$\frac{1}{AM} = \frac{1}{ \frac{1}{n}\sum_{j=1}^n x_j} = \prod_{j=1}^n\big(\frac{1}{ x_j}\big)^\frac{1}{n}=\frac{1}{GM}$ which occurs iff $x_1 = x_2 = ... = x_n$
- - - - -

we now have

$\frac{n}{n+1} \Big(\prod_{j=1}^n\big(\frac{1}{ x_j}\big)^\frac{1}{n} + \frac{1}{ \sum_{j=1}^n x_j}\Big) = \frac{n}{n+1} \Big(\prod_{j=1}^n\big(\frac{1}{ x_j}\big)^\frac{1}{n} \Big)+ \frac{1}{n+1}\frac{1}{ \frac{1}{n}\sum_{j=1}^n x_j} \geq \Big(\prod_{j=1}^n\big(\frac{1}{ x_j}\big)^\frac{1}{n} \Big)^\frac{n}{n+1}\Big( \frac{1}{ \frac{1}{n}\sum_{j=1}^n x_j}\Big)^\frac{1}{n+1} = \big(\frac{n}{c}\big)^\frac{1}{n+1}$

apply $AM \geq GM$

$\frac{n}{n+1} \Big(\frac{1}{n}\sum_{j=1}^n\big(\frac{1}{ x_j}\big) + \frac{1}{ \sum_{j=1}^n x_j}\Big) \geq \frac{n}{n+1} \Big(\prod_{j=1}^n\big(\frac{1}{ x_j}\big)^\frac{1}{n} + \frac{1}{ \sum_{j=1}^n x_j}\Big) \geq \big(\frac{n}{c}\big)^\frac{1}{n+1}$

multiply each side by $n+1$ and we get the below

$\sum_{j=1}^n\big(\frac{1}{ x_j}\big) + \frac{n}{ \sum_{j=1}^n x_j} \geq (n+1)\big(\frac{n}{c}\big)^\frac{1}{n+1}$
- - - -
from prior writeup, (post #8) make use of

$(n-1)\sum_{j=1}^n\big(\frac{1}{ x_j}\big) \geq (n-1)n\big(\frac{n}{c}\big)^\frac{1}{n+1}$

still with equality iff $x_1 = x_2 = ... = x_n$
- - - -
add $(n-1)n\big(\frac{n}{c}\big)^\frac{1}{n+1}$ to each side of our main inequality

$(n-1) \sum_{j=1}^n\big(\frac{1}{ x_j}\big)+ \sum_{j=1}^n\big(\frac{1}{ x_j}\big) + \frac{n}{ \sum_{j=1}^n x_j} \geq (n-1)n\big(\frac{n}{c}\big)^\frac{1}{n+1} + \sum_{j=1}^n\big(\frac{1}{ x_j}\big) + \frac{n}{ \sum_{j=1}^n x_j} \geq (n-1)n\big(\frac{n}{c}\big)^\frac{1}{n+1} + (n+1)\big(\frac{n}{c}\big)^\frac{1}{n+1}$

which simplifies to

$n \sum_{j=1}^n\big(\frac{1}{ x_j}\big) + \frac{n}{ \sum_{j=1}^n x_j} \geq (n-1)n\big(\frac{n}{c}\big)^\frac{1}{n+1} + (n+1)\big(\frac{n}{c}\big)^\frac{1}{n+1}$

this gives us
$n\text{ObjectiveFunction} = n\sum_{j=1}^n\big(\frac{1}{ x_j}\big) + n\frac{1}{ \sum_{j=1}^n x_j}\geq n(n-1)\big(\frac{n}{c}\big)^\frac{1}{n+1} + (n+1)\big(\frac{n}{c}\big)^\frac{1}{n+1} = \Big(n^2 -n + n + 1 \Big)\Big(\big(\frac{n}{c}\big)^\frac{1}{n+1}\Big)$

which simplifies to
$\text{ObjectiveFunction} \geq \frac{n^2 + 1}{n} \big(\frac{n}{c}\big)^\frac{1}{n+1}$

with equality iff $x_1 = x_2 = ... = x_n$
- - - - -
edit:

there's a nice self-generalizing approach in my prior post #8 that I missed.

In the prior post, we had

(a)
$\sum_{j=1}^n \frac{1}{x_j} \geq n\prod_{j=1}^n \frac{1}{x_j}^\frac{1}{n} \geq n\big(\frac{n}{c}\big)^{\frac{1}{n+1}}$

(b)
now also consider the $n+1$ case where we carefully select $x_{n+1}$. In particular:

$x_{n+1} := \frac{1}{n}\sum_{j=1 }^n x_j = E\big[X\big]$

$\sum_{j=1}^n \frac{1}{x_j} + \frac{n}{\sum_{j=1}^n x_j} = \sum_{j=1}^n \frac{1}{x_j} + \frac{1}{\frac{1}{n}\sum_{j=1 }^n x_j} = \sum_{j=1}^{n+1} \frac{1}{x_j} \geq (n+1)\prod_{j=1}^{n+1} \frac{1}{x_j}^\frac{1}{n+1} = (n+1)\big(\frac{n}{c}\big)^\frac{1}{n+1}$

combine $(n-1)a$ with $b$ and you get the solution, as before.

 

[PetSounds]

Will there be a problem for the week of December 12?