Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am given a triple of positive integers $a,b,c$ such that $a \geq 1$ and $b,c \geq 2$.

I would like to find an upper bound for $a+b+c$ in terms of $n = ab+bc+ac$. Clearly $a+b+c < ab+bc+ac = n$.

Is there any sharper upper bound that could be obtained (perhaps asimptotically)?

share|improve this question

2 Answers 2

up vote 12 down vote accepted

This is (mostly) a pretty routine optimization problem. The methods of (for example) a standard calculus class are enough to tell you that $a+b+c$ will be largest when two of $a,b,c$ are as small as possible and the third is whatever it has to be. So if you don't care whether the variables are integers, take $a=1,b=2,c=(n-2)/3$.

Thus if $n$ has the form $3k+2$, the optimum is achieved in integers. Take $a=1,b=2,c=k$, and then we have $a+b+c=3+\frac{n-2}{3}=\frac{n+7}{3}$.

So $\frac{n+7}{3}$ is an upper bound, and it actually gives the correct answer infinitely often.

share|improve this answer

The bound $n/2 + 1$ is tight. First, it is a bound because

$a + b + c \leq a b/2 + b c /2 + a c \leq n/2 + a c / 2 \leq n/2 + 1$

Equality is achieved when $a = 1$ and $b = c = 2$, since then we get $a + b + c = 5$ and $n/2 + 1 = (2+4+2)/2 + 1 = 5$.

Note that there might be other tight bounds that are also functions of $n$.

share|improve this answer

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.