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:


  • $\begingroup$ Does "max" just refer to the largest of the two terms? $\endgroup$ – Nathaniel B Jul 4 '16 at 18:20
  • $\begingroup$ @NathanielB Yes, exactly. $\endgroup$ – pi66 Jul 4 '16 at 18:20
  • $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.