0

Find integers $x, y, z > 0$ where:

$xy - xz - 10z$ is maximal, and $2x + y + z = 110$

How would one solve something like this using just algebra? It would be trivial to solve with calculus, but that shouldn't be necessary here.

user341554
  • 113
  • In general, finding max/min with integrality conditions is a matter of searching near the max min absent those conditions. Here, absent positivity and integrality you'd want ${27.5,55,0}$, for which your function gives $1512.5$. So I would search near there. At ${27,55,1}$ you get $1448$ which looks like a strong candidate (but I didn't look very hard). – lulu Sep 02 '16 at 21:43

2 Answers2

3

$z = 0$ seems obvious. (or smaller is better). Since $z$ is strictly greater than $0.$ Set $z = 1$

That makes it maximize $xy$ constrained by $2x+y = 109$

$y = 109 - 2x\\ 109x - 2x^2$

$ax^2 + bx + c$ is (with $a<0$) is maximized when $x = -b/2a$ (vertex of a parabola) $x = 110/4$

the non-integer solution is $(27.25, 54.5, 1)$

The maximal integer solution will be

$(27, 55, 1)$

Doug M
  • 57,877
  • $xy - xz - 10z = 27*56=1512$ . I can get higher by letting $y = -160$ $x=-10$ and $z = 290$ then $2x + y + z = -20 - 160 + 290 = 110$ and $xy - xz - 10z = 1600 + 2900 - 2900 = 1600$. – fleablood Sep 02 '16 at 22:05
  • @fleablood you missed a constraint x,y,z >0. Otherwise it is unbounded. – Doug M Sep 02 '16 at 22:07
  • You forgot $z>0$ too. – egreg Sep 02 '16 at 22:08
  • oops...... But you missed $z > 0$. – fleablood Sep 02 '16 at 22:08
  • you are right, I wanted it to be $z\ge 0$! – Doug M Sep 02 '16 at 22:09
  • This is good. But I just don't like the "x = 0 is obvious". I had to convince myself by writing xy - xz - 10z = xy -z(10 + x)$ and if x decreased while x and/or y increase then result increases so max occurs when z is minimal. ... I don't know, maybe that's the same as "x =0 is obvious". – fleablood Sep 02 '16 at 23:05
  • $-xz<0, -10z<0$ if $(x > -10), xy - xz - 10 z$ decreases as $z$ increases. – Doug M Sep 02 '16 at 23:12
1

@Doug M @fleablood

First of all, due to the constraint:

$$\tag{0}2x+y+z=110,$$

we have the following range of integer values: $1 \leq x \leq 54$, $1 \leq y,z \leq 106$.

Taking into account (0), one can factor this expression into:

$$xy - (x+10)z = 2(x^2 + x y - 45 x + 5 y - 550 )=2(x + 5)(x + y - 50) - 600.$$

It is clear that this maximization is equivalent to the maximization of

$$\tag{1}P=(x + 5)(x + y - 50)$$

Let us give a fixed value to $z$.

$P$ is a product of factors whose sum ($2x+y-45$) is a constant equal to $155-z$ (using (0)).

It is well known in such a case that the maximum occurs if the two factors are equal, i.e., if

$$x+5=x+y-50 \ \ \Leftrightarrow \ \ y=55.$$

Remark: this value of $y$, due to constraint (0), has the consequence that $x \leq 27.$

Plugging this value of $y$ into (1), one gets:

$P=(x+5)^2$ which is maximized for the largest possible value of $x$ i.e., $x=27$.

Thus, due to (1), $z=110-2x-y=1$ ; the final solution is then:

$$(x,y,z)=(27,55,1).$$

Jean Marie
  • 81,803