Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Question: For positive real numbers $a,b,c$ and $d$, find the smallest possible value of the following expression: $$\large{\left \lfloor{\frac{b+c+d}{a}} \right \rfloor+ \left \lfloor{\frac{a+c+d}{b}} \right \rfloor+\left \lfloor{\frac{a+b+d}{c}} \right \rfloor+\left \lfloor{\frac{a+b+c}{d}} \right \rfloor}$$


Note: For this question, the expression $\lfloor x \rfloor $ stands for the greatest integer function of x. For example, $\lfloor 2.5 \rfloor=2$, while $\lfloor -2.5 \rfloor=-3$

Bonus: Generalise the problem to $n$ numbers $a_1,a_2,\ldots,a_n$.

share|improve this question
up vote 16 down vote accepted

We use the following two tools:

  • Tool 1: Every real number $x$ satisfies $\lfloor x\rfloor>x-1$ (with strict inequality).
  • Tool 2: All positive real numbers $y$ and $z$ satisfy $\frac{x}{y}+\frac{y}{x}\ge2$; indeed this inequality is equivalent to $y^2+z^2\ge2yz$ and $(y-z)^2\ge0$.

Now the expression $E$ that is to be minimized can be estimated (by using these two tools) as follows: \begin{eqnarray*} E &=& \left\lfloor\frac{b+c+d}{a} \right\rfloor+ \left\lfloor\frac{a+c+d}{b} \right\rfloor+ \left\lfloor\frac{a+b+d}{c} \right\rfloor+ \left\lfloor\frac{a+b+c}{d} \right\rfloor \\ &>& \left(\frac{b+c+d}{a}-1\right)+ \left(\frac{a+c+d}{b}-1\right) + \left(\frac{a+b+d}{c}-1\right) + \left(\frac{a+b+c}{d}-1\right) \\ &=& \left(\frac{a}{b}+\frac{b}{a}\right)+ \left(\frac{a}{c}+\frac{c}{a}\right)+ \left(\frac{a}{d}+\frac{d}{a}\right)+ \left(\frac{b}{c}+\frac{c}{b}\right)+ \left(\frac{b}{d}+\frac{d}{b}\right)+ \left(\frac{c}{d}+\frac{d}{c}\right) -4 \\ &\ge& ~6\cdot2-4 ~~=~~ 8. \end{eqnarray*} We get $E>8$. Since $E$ is the sum of four integers and hence integer itself, this actually implies the lower bound $E\ge9$. Finally, for $a=4$ and $b=c=d=5$ the expression attains the value $9$.

Hence the smallest possible value of the above expression is

$~~~9~$ (nine)


For the Bonus question, the above argument easily generalizes. The resulting lower bound is $$ E ~>~ {n\choose 2}\cdot 2 -n, $$ which implies $E\ge(n-1)^2$. By setting $a_1=n$ and $a_2=a_3=\cdots=a_n=n+1$, we get $$\left\lfloor\frac{a_2+a_3+\cdots+a_n}{a_1} \right\rfloor = \left\lfloor\frac{(n-1)(n+1)}{n} \right\rfloor = \left\lfloor n-\frac{1}{n} \right\rfloor = n-1,$$ and $$\left\lfloor\frac{a_1+a_3+\cdots+a_n}{a_2} \right\rfloor = \left\lfloor\frac{(n-2)(n+1)+n}{n+1} \right\rfloor = \left\lfloor (n-2)+\frac{n}{n+1} \right\rfloor = n-2.$$ The resulting value of the expression is $(n-1)+(n-1)(n-2)=(n-1)^2$, and hence coincides with the lower bound.

Summarizing, the smallest possible value of the expression in the Bonus question

$~~~(n-1)^2$

share|improve this answer
    
That's it.You nailed it. – Roby5 Mar 19 at 17:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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