# Constant such that $\max\left(\frac{5}{5-3c},\frac{5b}{5-3d}\right)\geq k\cdot\frac{2+3b}{5-c-2d}$

What is the greatest constant $k>0$ such that

$$\max\left(\frac{5}{5-3c},\frac{5b}{5-3d}\right)\geq k\cdot\frac{2+3b}{5-c-2d}$$

for all $0\leq b\leq 1$ and $0\leq c\leq d\leq 1$?

The right-hand side looks like a weighted sum of the two terms on the left-hand side, but not quite. If we plug in $b=1$ and $c=d$, then all three terms are equal, so $k\leq 1$.

On the other hand, we have $k\geq 3/5$. Indeed, we will show that $$\frac{5}{5-3c}\geq\frac35\cdot\frac{2+3b}{5-c-2d}.$$ Note that $d\leq 1$ and $2+3b\leq 5$, so it suffices to show $$\frac{1}{5-3c}\geq\frac35\cdot\frac{1}{3-c},$$ or $$5(3-c)\geq 3(5-3c)$$ or $$15-5c\geq 15-9c$$ which is true. But the bound is not tight here, since we must have $b=d=1$ and $c=0$, and we have $\max(5, 5/2)\geq 5/3$. (The term $\frac{5b}{5-3d}$, which we did not use at all, is large.)

Update: By dividing the cases into whether $b\leq 3/5$ (and compare with the first term in the $\max$ if so) or $b\geq 3/5$ (and compare with the second term in the $\max$ if so), we can show that $k\geq 15/19$. Moreover, as Aravind pointed out in the comments, we have $k\leq 15/16$. So the gap is now between $15/19$ and $15/16$.

Update 2: WolframAlpha confirms that $k=15/16$ is the right answer. The question is now how to prove it:

http://www.wolframalpha.com/input/?i=find+minimum+of+max(5%2F(5-3c),(5b)%2F(5-3d))*(5-c-2d)%2F(2%2B3b)+for+0%3C%3Db%3C%3D1+and+0%3C%3Dc%3C%3Dd%3C%3D1

• Does "max" just refer to the largest of the two terms? – Nathaniel B Jul 4 '16 at 18:20
• @NathanielB Yes, exactly. – pi66 Jul 4 '16 at 18:20
• If $b \leq \dfrac{2}{5}$, then $k=\dfrac{15}{16}$ works and is optimal. Tight is $b=\dfrac{2}{5}$, $c=0,d=1$. For proof, notice that in this case, the first term is the largest of the two and it is enough to set $b=\dfrac{2}{5}$; the rest is easy. – Aravind Jul 6 '16 at 3:38

The original problem is equivalent to finding the minimum value of $$\max (\frac{5}{5-3c}, \frac{5b}{5-3d}) \cdot \frac{5-c-2d}{2+3b}$$ in the region $\{(b, c, d) \mid 0 \leq b \leq 1 \wedge 0 \leq c \leq d \leq 1\}$. We consider two cases below, namely,

• Case 1: $\frac{5}{5-3c} \leq \frac{5b}{5-3d}$;

• Case 2: $\frac{5}{5-3c} \geq \frac{5b}{5-3d}$.

Case 1: The problem can be stated as \begin{align} \text{minimize}\quad & f(b, c, d) = \frac{5-c-2d}{5-3d}\cdot \frac{5b}{2+3b} \\ \text{subject to}\quad & b \geq \frac{5-3d}{5-3c} \quad\quad (\text{by the condition of Case 1}) \\ & 0 \leq b \leq 1 \\ & 0 \leq c \leq d \leq 1 \end{align} Note that the term $\frac{5b}{2+3b} = \frac{5}{3} - \frac{10}{6+9b}$ in $f(b, c, d)$ is a strictly increasing function of $b$. To minimize $f(b, c, d)$, $b$ should be minimized, for fixed $c$ and $d$. Therefore, $$b = \frac{5-3d}{5-3c} \tag{1}$$ Substituting $b$ with (1) in $f$, we obtain that $$f(b, c, d) = \frac{25-5c-10d}{25-6c-9d} = \frac{5}{6} + \frac{\frac{25}{6} - \frac{15}{6}d}{25 - 6c - 9d}$$ For fixed $d$, $f(b, c, d)$ is minimized when $c$ is minimized, i.e., $c = 0$. We further obtain that $$f(b, c, d) = \frac{5}{6} + \frac{\frac{25}{6} - \frac{15}{6}d}{25 - 9d} = \frac{5}{6} + \frac{5}{18} - \frac{\frac{50}{18}}{25-9d}$$ Setting $d = 1$, we obtain the minimum value $\frac{5}{6} + \frac{5}{18} - \frac{50}{18\cdot16} = \frac{15}{16}$.

Case 2: The problem can be stated as: \begin{align} \text{minimize}\quad & g(b, c, d) = \frac{5-c-2d}{5-3c}\cdot \frac{5}{2+3b} \\ \text{subject to}\quad & b \leq \frac{5-3d}{5-3c} \quad\quad (\text{by the condition of Case 2}) \\ & 0 \leq b \leq 1 \\ & 0 \leq c \leq d \leq 1 \end{align} and the solution is similar to that of Case 1. First, the term $\frac{5}{2+3b}$ is a strictly decreasing function of $b$. Thus, we set $b = \frac{5-3d}{5-3c}$ and obtain $$g(b, c, d) = \frac{25-5c-10d}{25-6c-9d}$$ which is the same function as that in Case 1. So the minimum value is still $\frac{15}{16}$.

Note: This is the pretty much the same solution as that of NP-hard.

Let $x=5-3c$, $y=5-3d$, $t=\dfrac{5}{3k}$.

Then we are looking for the minimum $t$ for which: $min(x,\dfrac{y}{b}) \leq t\dfrac{(x+2y)}{(3b+2)}$.

with $2 \leq y \leq x \leq 5$ and $0 \leq b \leq 1$.

Consider the case $x \leq \dfrac{y}{b}$. Then sufficient is: $t \geq \dfrac{(3b+2)x}{(x+2y)}$ and since $b \leq \dfrac{y}{x}$, it is sufficient that $t \geq \dfrac{2x+3y}{x+2y}$ and the max value of the expression on the right is $\dfrac{16}{9}$. Thus in this case, $t =\dfrac{16}{9}$ suffices which corresponds to $k=\dfrac{15}{16}$.

In the case when $\dfrac{y}{b} \leq x$, it is sufficient to have: $t \geq \dfrac{(3b+2)}{(x+2y)}y/b=(3+\dfrac{2}{b})\dfrac{y}{x+2y}$ and using $b \geq \dfrac{y}{x}$, we once again get the same calculation as above.