19. Min/max and optimization
Push everything else to its extreme to bound the target. Integers vs reals matters.
Core ideas
- To maximize one quantity under a fixed total, push everything else to its minimum (and vice versa).
- Read the constraints literally: positive vs nonnegative, distinct vs repeatable, integer vs real each change the extreme.
- For a fixed sum, a product of two quantities is largest when they are as equal as allowed.
- Always ask whether the extreme you built actually satisfies every constraint.
Worked example 1
x, y, and z are distinct positive integers with x + y + z = 30. What is the greatest possible value of z?
Show solution
To maximize z, minimize x + y. The smallest distinct positive integers are 1 and 2, so x + y = 3 at minimum and z = 30 - 3 = 27. Check the constraints: 1, 2, 27 are distinct positive integers summing to 30. If the problem had said nonnegative instead of positive, we could use 0 and 1 and get z = 29; if it had dropped distinct, 1 and 1 would give z = 28. The constraints set the answer.
Worked example 2
If x + y = 11, what is the maximum value of xy (a) if x and y are real, and (b) if x and y are integers?
Show solution
For a fixed sum, the product is maximized when the numbers are as equal as possible. (a) Reals: x = y = 5.5 gives xy = 5.5^2 = 30.25. (b) Integers: they cannot both be 5.5, so take the closest pair, 5 and 6, giving xy = 30. The one-word difference between real and integer moves the answer from 30.25 to 30, and on harder problems it can change it dramatically.
Practice set
Question 1
If 2 <= x <= 5 and 1 <= y <= 3, what is the greatest possible value of x - y?
To maximize a difference, push the first quantity up and the second one down.
Maximize x at 5 and minimize y at 1, giving x - y = 5 - 1 = 4. Answer 2 comes from pairing the maximums (5 - 3), which maximizes neither the gap nor the difference.
Question 2
If x and y are numbers such that 2x + y = 10, what is the least possible value of x^2 + y^2?
Substitute for y and minimize the resulting quadratic in x; x and y need not be integers.
Substitute y = 10 - 2x, so x^2 + y^2 = x^2 + (10 - 2x)^2 = 5x^2 - 40x + 100. This quadratic is minimized at x = 40/10 = 4, giving 5(16) - 160 + 100 = 20, with y = 2. Answer 50 comes from assuming x = y, which is only optimal when the coefficients match.
Question 3
Seven positive integers have an average of 15, and their median is 15. What is the greatest possible value of the largest of these integers?
The median pins the middle value and forces a floor on the three values above it as well as the three below.
The sum is 7 x 15 = 105. The median 15 is the fourth value in order. To maximize the largest, minimize everything else: the three smallest can each be 1, the median is 15, and the fifth and sixth values must be at least 15 each. That uses 1 + 1 + 1 + 15 + 15 + 15 = 48, leaving 105 - 48 = 57 for the largest. Answer 75 ignores that the two values above the median must be at least 15.
Question 4
If x and y are positive integers and x + y = 20, what is the greatest possible value of the product xy?
For a fixed sum, think about how close together the two numbers should be.
For a fixed sum, the product is largest when the numbers are as close as possible. With x + y = 20, take x = y = 10, giving xy = 100. Answer 19 is the minimum product (1 x 19), the opposite extreme.