Optimization Techniques and Functional Equations
Pillar: FIX — "Fix specific input values to extract the function's structure."
Part 1: Optimization Without Calculus
Many competition problems ask you to find the maximum or minimum of some expression. Calculus gives derivatives; we don't need them. Algebra gives us three powerful tools:
- Completing the square — turns a quadratic into vertex form
- AM-GM — bounds an expression given a constraint
- Geometric intuition — the extremum often occurs at a "balanced" point
Completing the Square
Any quadratic \(ax^2 + bx + c\) can be rewritten as:
This is called vertex form \(a(x - h)^2 + k\), where:
- The vertex is at \(x = h = -\frac{b}{2a}\)
- The minimum (if \(a > 0\)) or maximum (if \(a < 0\)) value is \(k = c - \frac{b^2}{4a}\)
Worked Example
Minimize \(f(x) = x^2 + 6x + 13\).
Since \((x+3)^2 \ge 0\) always, the minimum of \(f\) is \(\boxed{4}\), achieved at \(x = -3\).
Multi-Variable Completion
You can complete the square one variable at a time.
Example. Minimize \(f(x, y) = x^2 + y^2 - 4x + 6y + 20\).
Complete \(x\): \(x^2 - 4x = (x-2)^2 - 4\).
Complete \(y\): \(y^2 + 6y = (y+3)^2 - 9\).
Minimum is \(7\) at \((x, y) = (2, -3)\).
AM-GM for Optimization
Recall from the previous lesson:
This means: if the product \(ab\) is fixed, the sum \(a + b\) is minimized when \(a = b\).
The Standard Trick
Problem. For \(x > 0\), minimize \(f(x) = x + \frac{9}{x}\).
Apply AM-GM directly to \(x\) and \(\frac{9}{x}\):
Equality when \(x = \frac{9}{x}\), i.e., \(x = 3\).
Minimum value is \(\boxed{6}\).
The Strategy
- Identify two (or more) terms whose product is constant (or whose product simplifies nicely).
- Apply AM-GM to bound their sum.
- Find where equality holds.
Example with a Constraint
Problem. Given \(x, y > 0\) with \(x + y = 10\), maximize \(xy\).
AM-GM: \(\frac{x+y}{2} \ge \sqrt{xy}\), so \(5 \ge \sqrt{xy}\), so \(xy \le 25\).
Equality when \(x = y = 5\). Maximum of \(xy\) is \(\boxed{25}\).
Weighted AM-GM
Sometimes you need to split a term to create the right number of equal pieces.
Problem. Minimize \(2x + \frac{3}{x}\) for \(x > 0\).
Direct AM-GM on \(2x\) and \(\frac{3}{x}\):
Equality when \(2x = \frac{3}{x}\), i.e., \(x = \sqrt{3/2}\).
Lagrange Multiplier Intuition (No Calculus)
The geometric idea behind constrained optimization is simple:
- You have a surface defined by \(f(x, y)\) (the thing to optimize).
- You have a curve defined by \(g(x, y) = c\) (the constraint).
- The extremum occurs where the level curves of \(f\) are tangent to the constraint curve.
In competition math, this translates to: at the optimum, the variables are as balanced as possible given the constraint. When \(a + b + c\) is fixed and you're optimizing a symmetric expression, try \(a = b = c\) first.
Part 2: Functional Equations
A functional equation is an equation where the unknown is a function, not a number.
Example. Find all functions \(f : \mathbb{R} \to \mathbb{R}\) such that \(f(x + y) = f(x) + f(y)\) for all \(x, y\).
This is Cauchy's functional equation, and (under reasonable assumptions) the only solution is \(f(x) = cx\) for some constant \(c\).
The Substitution Method
The key technique: substitute specific values for the variables to extract information about \(f\).
Example 1: Cauchy's Equation
\(f(x + y) = f(x) + f(y)\) for all \(x, y \in \mathbb{R}\).
Step 1: Set \(x = y = 0\): \(f(0) = f(0) + f(0) = 2f(0)\), so \(f(0) = 0\).
Step 2: Set \(y = -x\): \(f(0) = f(x) + f(-x)\), so \(f(-x) = -f(x)\) (odd function).
Step 3: Set \(y = x\): \(f(2x) = 2f(x)\). By induction: \(f(nx) = nf(x)\) for all integers \(n\).
Step 4: Let \(c = f(1)\). Then \(f(n) = nc\) for all integers. For rationals: \(f(p/q) = (p/q)c\). Assuming continuity: \(f(x) = cx\) for all real \(x\).
Example 2: Multiplicative → Logarithmic
\(f(xy) = f(x) + f(y)\) for all \(x, y > 0\).
Step 1: Set \(x = y = 1\): \(f(1) = 2f(1)\), so \(f(1) = 0\).
Step 2: Set \(y = x\): \(f(x^2) = 2f(x)\). By induction: \(f(x^n) = nf(x)\).
Step 3: Let \(b > 0\) be arbitrary and set \(c = f(b)\). Then \(f(b^n) = nc\), which matches \(c \cdot \log_b(b^n) = cn\).
Under continuity: \(f(x) = c \cdot \log_b x\) for some base \(b\) and constant \(c\), or equivalently \(f(x) = k \ln x\).
Example 3: A Competition Classic
\(f(x + y) = f(x) \cdot f(y)\) for all \(x, y\), with \(f(0) \ne 0\).
Step 1: Set \(x = y = 0\): \(f(0) = f(0)^2\), so \(f(0) = 1\) (since \(f(0) \ne 0\)).
Step 2: Set \(y = -x\): \(1 = f(x) \cdot f(-x)\), so \(f(-x) = 1/f(x)\). This means \(f(x) > 0\) always.
Step 3: Set \(y = x\): \(f(2x) = f(x)^2\). Inductively: \(f(nx) = f(x)^n\).
Step 4: Let \(a = f(1) > 0\). Then \(f(n) = a^n\). Extending to rationals and reals: \(f(x) = a^x\) for some \(a > 0\).
Catalog of Standard Functional Equations
| Equation | Solution (continuous) |
|---|---|
| \(f(x+y) = f(x) + f(y)\) | \(f(x) = cx\) |
| \(f(xy) = f(x) + f(y)\) | \(f(x) = c \ln x\) |
| \(f(x+y) = f(x) \cdot f(y)\) | \(f(x) = a^x\) |
| \(f(xy) = f(x) \cdot f(y)\) | \(f(x) = x^c\) |
Solving More Complex Functional Equations
Technique: Find \(f\) at Special Points
Always try \(x = 0\), \(y = 0\), \(x = y\), and \(y = -x\) first. These often give you \(f(0)\), symmetry properties, and recursive relationships.
Technique: Guess and Verify
If substitutions suggest \(f\) is a polynomial, guess its degree and solve for coefficients.
Example. \(f(x + 1) - f(x) = 2x + 1\) with \(f(0) = 3\).
Compute a few values: \(f(1) = f(0) + 1 = 4\), \(f(2) = f(1) + 3 = 7\), \(f(3) = f(2) + 5 = 12\).
The differences \(1, 3, 5, 7, \ldots\) are linear in \(x\), so \(f\) should be quadratic. Guess \(f(x) = ax^2 + bx + c\).
- \(f(0) = 3 \Rightarrow c = 3\)
- \(f(x+1) - f(x) = a(2x+1) + b = 2x + 1 \Rightarrow a = 1, b = 0\)
So \(f(x) = x^2 + 3\). Verify: \(f(x+1) - f(x) = (x+1)^2 + 3 - x^2 - 3 = 2x + 1\) ✓.
Technique: Exploit Symmetry
If the equation is symmetric in \(x\) and \(y\), the function is likely symmetric too. If swapping \(x\) and \(y\) gives a different equation, combine the two to eliminate unknowns.
Practice Problems
Problem 1. Find the minimum value of \(3x^2 - 18x + 30\).
Solution
\(3(x^2 - 6x) + 30 = 3(x-3)^2 - 27 + 30 = 3(x-3)^2 + 3\).
Minimum is \(3\) at \(x = 3\).
Problem 2. For \(x > 0\), minimize \(x + \frac{16}{x}\).
Solution
AM-GM: \(x + \frac{16}{x} \ge 2\sqrt{16} = 8\), equality at \(x = 4\).
Minimum is \(8\).
Problem 3. Given \(a, b, c > 0\) with \(abc = 8\), minimize \(a + b + c\).
Solution
By AM-GM for three variables: \(\frac{a+b+c}{3} \ge \sqrt[3]{abc} = 2\).
So \(a + b + c \ge 6\), equality when \(a = b = c = 2\).
Problem 4. Find all functions \(f : \mathbb{R} \to \mathbb{R}\) with \(f(2x + 1) = 4x + 3\).
Solution
Let \(u = 2x + 1\), so \(x = \frac{u-1}{2}\).
\(f(u) = 4 \cdot \frac{u-1}{2} + 3 = 2(u-1) + 3 = 2u + 1\).
So \(f(x) = 2x + 1\).
Problem 5. Find all functions \(f : \mathbb{R}^+ \to \mathbb{R}\) with \(f(xy) = f(x) + f(y)\) and \(f(2) = 1\).
Solution
From the standard catalog, \(f(x) = c \ln x\). Since \(f(2) = 1\), we get \(c = \frac{1}{\ln 2}\).
So \(f(x) = \frac{\ln x}{\ln 2} = \log_2 x\).
Problem 6. Minimize \(f(x,y) = x^2 + 4y^2 + 2x - 8y + 10\).
Solution
Complete the square:
\((x^2 + 2x + 1) + 4(y^2 - 2y + 1) + 10 - 1 - 4 = (x+1)^2 + 4(y-1)^2 + 5\)
Minimum is \(5\) at \((x, y) = (-1, 1)\).