Inequality x y z

If $x,y,z$ are positive numbers such that $x+y+z = 1$ show that: $$ \frac{1}{x+y} + \frac{1}{x+z}+ \frac{1}{y+z} + \frac{9}{2} \geq \frac{3}{1 - (\frac{x-y}{2})^2} + \frac{3}{1 - (\frac{y-z}{2})^2} + \frac{3}{1 - (\frac{x-z}{2})^2}$$

(Hopefully) Correct Solution

WLOG we may assume that $x \geq y \geq z$. And for now we assume that $2y \geq x+z$ (the case where $2y < x+z$ is handled later below).

By AM-HM: $$\frac{1}{y+z} + \frac{1}{y+z} + \frac{1}{x+z} \geq \frac{9}{(y+z)+(y+z)+(x+z)} = \frac{9}{1+y+2z} = \frac{9}{2+z-x}$$ $$\frac{1}{y+z} + \frac{1}{x+z} + \frac{1}{x+z} \geq \frac{9}{1+x+2z} = \frac{9}{2+z-y}$$ Adding the two inequalities: $$ \frac{1}{y+z} + \frac{1}{x+z} \geq \frac{3}{2+z-x} + \frac{3}{2+z-y} $$ (Call this inequality 1).

Incorrect Solution

WLOG we may assume that $x \geq y \geq z$. Suppose $a = x-z, b = x-y$ so $a+b = 2x-y-z = 3x-1$. If $a=b=0$ then $x=y=z=1/3$ and equality happens. Thus at least one of $a,b$ is positive, so $a+b > 0$. Now, by Cauchy: $$(\frac{a}{a+b} . \frac{1}{y+z} + \frac{b}{a+b} . \frac{3}{2})(\frac{a(y+z)}{a+b} + \frac{2b}{3(a+b)}) \geq (\frac{a}{a+b} + \frac{b}{a+b})^2 = 1$$ So: $$\frac{a}{a+b} . \frac{1}{y+z} + \frac{b}{a+b} . \frac{3}{2} \geq \frac{3(a+b)}{3a(y+z) + 2b} = \frac{3}{2+z-x}$$ The last equality is equivalent to: $$ \frac{1(a+b)}{3a(y+z) + 2b} = \frac{1}{2+z-x} $$ $$ \iff (a+b)(2+z-x) = 3a(y+z) + 2b $$ Because $2+z-x \iff 3-2x-y$ and $y+z = 1-x$ $$ \iff (3x-1)(3-2x-y) = 3(x-z)(1-z) + 2(x-y)$$ Upon expanding and rearranging: $$ \iff 0 = 3(x-1)(x+y+z - 1) $$ which is true. On the other hand, using the same definition of $a,b$, we can also show: $$\frac{b}{a+b} . \frac{1}{y+z} + \frac{a}{a+b} . \frac{3}{2} \geq \frac{3(a+b)}{3b(y+z) + 2a} = \frac{3}{2+y-x}$$ (Using similar identity as above) Adding the two inequalities, we have: $$ \frac{1}{y+z} + \frac{3}{2} \geq \frac{3}{2+z-x} + \frac{3}{2+y-x}$$ And similarly: $$ \frac{1}{x+z} + \frac{3}{2} \geq \frac{3}{2+x-y} + \frac{3}{2+z-y}$$ $$ \frac{1}{x+y} + \frac{3}{2} \geq \frac{3}{2+y-z} + \frac{3}{2+z-x}$$ Now all we need to show is that the sum of LHS is equal to the LHS of the given problem. Indeed it is so because: $$ \frac{3}{2+y-x} + \frac{3}{2+x-y} = \frac{3(2+x-y) + 3(2+y-x)}{2^2 - (x-y)^2} = \frac{12}{4 - (x-y)^2} = \frac{3}{1 - (\frac{x-y}{2})^2}$$ Edit: what is wrong with this proof?

maximum minimum of function

For $A,B,C$ non-negative angles such that $A+B+C = \pi / 2$, find the maximum and minimum of: $$ f = \sin A + \sin B + \sin C + \sin^2 A + \sin^2 B + \sin^2 C$$ and $$g = \cos A (\sin A -1) + \cos B (\sin B - 1) + \cos C (\sin C - 1)$$

Paintings and colors

In a museum there are $n$ paintings, each of which was painted with at least 3 colors. The total number of colors from all paintings is $m << n$. The average number of colors per painting is $s$.

If we choose $k$ paintings at random, what's the expected number of colors that we get? What's the maximum and minimum value of this expectation, for a fixed color-painting configuration, but for varying choices of paintings?

If we choose $l$ colors at random, what's the expected number of paintings that can be replicated with those colors? (It means each painting is painted only with those colors). Again, what's the maximum and minimum value of this expectation?

Remark: by choosing $m,n,s,k,l$ judiciously we can write problems such as: show that we can choose $k$ paintings such that the number of colors among those paintings is at most / at least $x$.

Solution

There are $N = {n \choose k}$ ways to choose paintings. For each choice of paintings, we tally up the total number of colors produced, and then we sum it over all possible choice of paintings. Let $S$ be this sum of total number of colors. The expected number of colors is then $S / N$.

Suppose the color $c$ is used by $p_c$ paintings. We wish to count the contribution of $c$ towards $S$. The color contributes one point to $S$ for each choice of paintings that includes at least one of the $p_c$, and zero otherwise. That means now the question is, how many ways can we choose $k$ out of $n$ paintings such that at least one of them comes from the $p_c$ paintings? There are $N$ ways total to choose, and there are ${n-p_c \choose k}$ ways to choose such that none of the $p_c$ paintings are chosen, so the total number is: $${n \choose k} - {n-p_c \choose k}$$ So: $$S = \sum_c {n \choose k} - {n-p_c \choose k}$$ where the sum runs over all $m$ colors. This expression is exact. What follows from this point on is an attempted to upper/lower bound $S$, and it may not be exact, although we will give examples to show that the bound is tight.

Now consider the function $f(t) = {n \choose k} - {n-t \choose k}$, defined over $t \in [1,m]$ (the color must be used in at least 1 painting, and at most $m$ paintings obviously). We are given that $m << n$ so it's safe to assume that ${n-m \choose k} > 0$. The convexity and concavity analysis depends on if $k$ is even or odd. For now, assume $k$ is odd. The analysis if $k$ is even is very similar.

The function $(n-t)(n-t-1)\dots (n-t-k+1)$ is convex in the interval $(0,n-k-1)$, and since $m << n$, it is convex in the interval $[1,m]$. That means $f(t)$ is concave. On the other hand, we know that the average number of colors per painting is $s$, so there are $sn$ distinct painting-color pairs, so $\sum_c p_c = sn$.

By Jensen, the maximum of $\sum_c f(p_c)$ is achieved if all the $p_c$ is the same, that is $sn/m$. In that case, $$\frac{S}{N} \leq \frac{\sum_c {n \choose k} - {n-p_c \choose k}}{n \choose k} = \frac{ m({n \choose k} - {n-\frac{sn}{m} \choose k}) }{n \choose k}$$ For example, for $n=50,k=3,m=25,s=10$, we have $S/N = 19.8$. So we can write a problem such as: show that we can choose 3 paintings such that between them we get at most 19 colors.

In order to find the lower bound, by majorization theorem, the minimum of $\sum_c f(p_c)$ is achieved by $[p_c] = [m,m,m,\dots,m,r,1,\dots,1]$ because that's the configuration that majorizes everything else. The number of $m$s, and $1$s and the value of $r$ (if needed) will have to depend on the particular problem setup, to make sure the following two conditions are met:

1. $\sum_c p_c = sn$ 2. The number of elements in $[p_c]$ is $m$.

For example, in the $n=50,k=3,m=25,s=10$ case above, we would have $[p_c] = [25,25,\dots,25,20,1,1,\dots,1]$ where there are 19 25s and 6 1s. Then: $$S \geq 25 \times {50 \choose 3} - 19 \times {50-25 \choose 3} - 1 \times {50-20 \choose 3} - 6 \times {50-1 \choose 3}$$ $$\frac{S}{N} \geq 16.9$$ So we can say: show that we can choose 3 paintings such that between them we get at least 17 colors.

Inverse distances to points

Let $P$ and $Q$ be two distinct points on a plane. For any given point $X \neq P,Q$, define two functions $f(X)$ and $g(X)$ as follows: $$f(X) = \frac{1}{PX} + \frac{2}{QX}$$ $$g(X) = \frac{2}{PX} + \frac{1}{QX}$$ Now for any positive number $t$, let $S(t)$ be the set of all points $Y$ such that $f(Y) \leq tg(Y)$.

Prove that $S(t)$ is bounded

Prove that $S(t)$ is convex. That is, if $A,B$ are in $S(t)$ then $AB$ is in $S(t)$.

Identify all points $X$ on $S(t)$ such that $PX+QX$ is minimum.

Prove that the area of $S(t)$ is a convex function of $t$.

Powered distances

Let $p$ and $q$ be two infinitely long non-parallel lines on a plane. For any point $X$, let $d_p(X), d_q(X)$ denote distances from $X$ to $p$ and $q$ respectively. For any positive number $r$, let $S(r)$ be the set of all points $Y$ such that $d_p(Y)^{2015} + d_q(Y)^{2015} \leq r$.

Prove that $S(r)$ is bounded.

Prove that $S(r)$ is convex. That is, if $A$ and $B$ are in $S(r)$ then $AB$ is in $S(r)$.

Identify all points in $S$ such that $d_p(X)^{2014} + d_q(X)^{2014}$ is maximum.

Prove that the area of $S(r)$ is a convex function of $r$.

Inequality

If $x_1,\dots,x_n$ are real numbers such that $0 \leq x_i \leq 1 \forall i$, and satisfies $x_1 + \dots + x_n = m+r$ where $m$ is an integer and $0 \leq r < 1$, show that:

$$(1+x_1)(1+x_2)\dots(1+x_n) \geq (1+r)2^m$$

Determine the conditions under which equality is achieved.

Solution

For each $i$ such that $x_i = 0$ or $x_i = 1$, we can safely eliminate them from the problem without changing neither the condition nor the inequality. So without loss of generality, we can assume that $0 < x_i < 1$ for all $i$.

Now, we prove by induction on $n$. It is trivial for $n=1$. For $n=2$, we have two cases:
1. The simple case, $x_1 + x_2 = r < 1$ then the inequality also holds trivially
2. The overflowing case, where $1 < x_1 + x_2 = 1 + r$, then:
$$(1-x_1)(1-x_2) \geq 0$$
$$\iff 1+x_1x_2 \geq x_1+x_2 = 1+r$$
$$\iff 1+x_1+x_2+x_1x_2 \geq 2+2r$$
$$\iff (1+x_1)(1+x_2) \geq 2(1+r)$$

Now, for a larger value of $n$, suppose that the inequality is established for $n-1$, and suppose that $x_1 + \dots + x_{n-1} = m + r$. Again we have two cases,

1. The simple case, if $x_n + r < 1$ then $x_1 + \dots + x_n = m+ (r+x_n) < m+1$
$$(1+x_1)\dots(1+x_{n-1})(1+x_n) \geq (1+x_n)(1+r)2^m \geq (1+r+x_n)2^m$$
which follows from the simple case for $n=2$ above.

2. The overflowing case, if $1 < x_n + r = 1 + r_2$ then $x_1 + \dots + x_n = (m+1) + r_2$

$$(1+x_1) \dots (1+x_{n-1})(1+x_n) \geq (1+x_n)(1+r)2^m$$
$$ \geq (1+r_2)2^{m+1}$$
which is similar to the overflowing case from $n=2$ above.

The equality cases can be determined as follows:
If all $x_i$s are zeros or ones, then the equality follows trivially. We assert then at most one of the $x_i$s are strictly between zero and one. Because if there are two of them, then both the simple case and the overflowing case in $n=2$ will never reach equality. The inductive step in the proof also depends on these two cases.

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.

a b c sides of a triangle, perimeter less than 2

If $a,b,c$ are sides of a triangle whose perimeter is less than 2, prove that:

$\displaystyle \frac{(1+a)(1+b)(1+c)}{(1-a)(1-b)(1-c)} < \frac{(2+a+b+c)^2}{(2-(a+b+c))^2}$