## Thursday, May 13, 2010

### Largest k for arbitrary function

Find the largest number $k$ that satisfies the following property:

For every real-valued function $f$ defined over $[0,1]$, there exist $a,b,c \in [0,1]$ such that:
$$|f(ab) + f(bc) + f(ca) - abc | \geq k$$

Solution

First we show that $k = 1/6$ satisfies the condition of the problem.

For $k=1/6$, suppose to the contrary that for all $a,b,c$ chosen in the interval $[0,1]$ we have:
$$|f(ab) + f(bc) + f(ca) - abc | < \frac{1}{6}$$

Let $y = f(0),y=f(1)$.
Plugging in $a=b=c=0$ we have $|3x| < 1/6 \iff |x| < 1/18$
Plugging in $a=b=c=1$ we have $|3y-1| < 1/6$
Plugging in $a=b=1, c=0$ we have $2x+y| < 1/6$

That means $y = (2x+y) - 2x < 1/6 + 2/18 = 5/18$
But also $3y-1 > -1/6 \iff y > 5/18$, a contradiction.

Thus $k= \frac{1}{6}$ satisfies the condition of the problem.

Now we show that it is the largest such constant. We choose a function $f(x) = \frac{6x^\frac{3}{2} - 1}{18}$ and prove that
$$-\frac{1}{6} \leq f(ab)+f(bc)+f(ca) - abc \leq \frac{1}{6}$$
for all $a,b,c \in [0,1]$

Indeed, the first inequality is equivalent to
$$(ab)^\frac{3}{2} + (bc)^\frac{3}{2} + (ca)^\frac{3}{2} \geq 3abc$$ which is true by AM-GM.

The second inequality is equivalent to
$$(ab)^\frac{3}{2} + (bc)^\frac{3}{2} + (ca)^\frac{3}{2} - 3abc \leq 1$$

Now consider the LHS, and try to find its maximum value over $a,b,c \in [0,1]$
First, we try a substitution $x = \sqrt{ab}, y = \sqrt{ac}, z = \sqrt{bc}, x,y,z \in [0,1]$ and WLOG, we may assume that $x \geq y \geq z$ (which corresponds to $a \geq b \geq c$)
So now our objective function becomes $x^3 + y^3 + z^3 - 3xyz$.

Let $g(x) = x^3 + y^3 + z^3 - 3xyz$, and fix $y,z$.
$$g(1) - g(x) = (1-x^3) - 3yx(1-x) = (1-x)(1 + x + x^2 - 3yz)$$
Because $x \leq 1$, then $1-x \geq 0$
$1+x+x^2-3yz \geq 1 + 2x^2-3yz = (1-yz) + 2(x^2 - yz) \geq 0$
So $g(1) \geq g(x)$.

So the maximum happens when the largest of 3 variables equals to 1. But this means that $ab = 1$ which implies $a=b=1$. Then $y = z = \sqrt{c}$. Our objective function now becomes:
$$x^3 + y^3 + z^3 - 3xyz = 2y^3 - 3y^2 +1$$
Let $h(y) = 2y^3 - 3y^2 + 1$, then $h(y) - h(0) = y^2(2y-3) < 0$ because $y \geq 1$. So the maximum happens when $y = 0$

In conclusion, our maximum happens when $x = 1, y=z=0$ and that's when $a=b=1, c= 0$. At this point, the maximum value is 1, thus proving our assertion.

Another way to determine the maximum value of the function above is by observing that it is a convex function on each of its variable, and all three variables are freely chosen from the interval $[0,1]$. Thus, the maximum must happen when all of its variables are zero or one. Plugging in all permutations of $(0,0,0), (0,0,1), (0,1,1), (1,1,1)$, we find that the maximum is indeed 1.