Systems of Equations and Inequalities
Pillar: FIX — "Fix one variable via one equation, substitute into the other."
Why Systems of Equations Matter
Many competition problems boil down to: "Here are several constraints relating several unknowns. Find the unknowns." That is a system of equations. When a problem says "Alice has twice as many apples as Bob, and together they have 30," you have two equations in two unknowns. When a problem gives you \(n\) congruences and asks you to find \(x\), that is a system (and the Chinese Remainder Theorem from Chapter 12 is the tool).
Inequalities arise whenever a problem says "at most," "at least," or "within range." Bounding the search space, checking feasibility, and proving that a greedy approach works all involve reasoning about inequalities.
Solving 2-Variable Systems: Substitution
The substitution method embodies the FIX pillar directly: solve one equation for one variable, substitute into the other.
Example: Solve the system:
Step 1: Solve equation (1) for \(y\): \(y = 10 - x\).
Step 2: Substitute into equation (2): \(3x - (10 - x) = 6\).
Step 3: Solve: \(3x - 10 + x = 6 \Rightarrow 4x = 16 \Rightarrow x = 4\).
Step 4: Back-substitute: \(y = 10 - 4 = 6\).
Solution: \((x, y) = (4, 6)\).
Substitution is the go-to method when one equation is already solved for a variable, or when one coefficient is 1 (easy to isolate).
Solving 2-Variable Systems: Elimination
The elimination method adds or subtracts equations to cancel one variable.
Example: Solve:
The \(y\)-coefficients are \(+3\) and \(-3\) — they cancel if we add:
Substitute back: \(2(2) + 3y = 13 \Rightarrow 3y = 9 \Rightarrow y = 3\).
When coefficients don't cancel directly, multiply one or both equations first:
Example: Solve:
Multiply (1) by 5 and (2) by 4 to match \(y\)-coefficients:
Subtract: \(7x = 21\), so \(x = 3\). Then \(y = \frac{25 - 9}{4} = 4\).
Substitution vs. Elimination: When to Use Which
| Situation | Preferred method |
|---|---|
| One variable has coefficient 1 | Substitution (easy isolation) |
| Coefficients align nicely for cancellation | Elimination |
| One equation is nonlinear (e.g., \(xy = 12\)) | Substitution (isolate then plug in) |
| Three or more variables | Elimination (systematically reduce) |
Word Problems with Two Variables
The challenge is always translation. Define variables, write equations, solve.
Example: A movie theater sells adult tickets for $9 and child tickets for $5. On a particular day, 200 tickets were sold for a total of $1,340. How many adult and child tickets were sold?
Let \(a\) = adult tickets, \(c\) = child tickets.
From (1): \(c = 200 - a\). Substitute into (2):
Sanity check: \(85 \times 9 + 115 \times 5 = 765 + 575 = 1340\) ✓. Always verify — if you get a non-integer answer for a counting problem, either the equation setup is wrong or the problem has no solution.
Systems of 3+ Variables
With three variables, you need three equations. The strategy is systematic elimination: use pairs of equations to eliminate one variable, reducing to a 2-variable system.
Example: Solve:
Step 1: Eliminate variables pairwise.
Subtract (2) from (1): \((x + y + z) - (x - y + z) = 6 - 2\), so \(2y = 4\), giving \(y = 2\).
Add (1) and (3): \((x + y + z) + (2x + y - z) = 6 + 1\), so \(3x + 2y = 7\).
Step 2: Solve. Since \(y = 2\): \(3x + 4 = 7\), so \(x = 1\).
From (1): \(1 + 2 + z = 6\), so \(z = 3\).
Solution: \((x, y, z) = (1, 2, 3)\).
Gaussian Elimination
The systematic approach for \(n\) equations in \(n\) unknowns is Gaussian elimination: use row operations to reduce to triangular form, then back-substitute. This is exactly what you do for 2 or 3 variables, just formalized. In Chapter 10 (linear algebra), you will implement this in code for large systems.
Linear Inequalities
An inequality uses \(<\), \(>\), \(\leq\), or \(\geq\) instead of \(=\). Solving works like equations with one critical difference:
Multiplying or dividing by a negative number reverses the inequality sign.
Example: Solve \(-3x + 7 \geq 1\).
The solution is all \(x \leq 2\), which on a number line is a ray going left from 2 (including 2).
Compound Inequalities
Example: Solve \(-1 < 2x + 3 \leq 9\).
Subtract 3 from all parts: \(-4 < 2x \leq 6\).
Divide by 2: \(-2 < x \leq 3\).
The solution is the interval \((-2, 3]\).
Two-Variable Linear Inequalities
The inequality \(2x + 3y \leq 12\) defines a half-plane — the region on one side of the line \(2x + 3y = 12\). To determine which side, test a point (usually the origin):
\(2(0) + 3(0) = 0 \leq 12\). True. So the origin is in the solution region.
In competition problems, you often need to count integer lattice points satisfying a system of linear inequalities. This is equivalent to counting grid points inside a polygon — a common task.
Quadratic Inequalities
To solve \(x^2 - 5x + 6 > 0\):
Step 1: Factor. \(x^2 - 5x + 6 = (x - 2)(x - 3)\).
Step 2: Find the roots. \(x = 2\) and \(x = 3\).
Step 3: Sign analysis. The roots divide the number line into three intervals. Test one point in each:
| Interval | Test point | \((x-2)\) | \((x-3)\) | Product | Sign |
|---|---|---|---|---|---|
| \(x < 2\) | \(x = 0\) | \(-\) | \(-\) | \(+\) | Positive |
| \(2 < x < 3\) | \(x = 2.5\) | \(+\) | \(-\) | \(-\) | Negative |
| \(x > 3\) | \(x = 4\) | \(+\) | \(+\) | \(+\) | Positive |
Solution: \(x < 2\) or \(x > 3\), i.e., \(x \in (-\infty, 2) \cup (3, \infty)\).
The Sign Analysis Pattern
For any factored polynomial inequality:
- Find the roots.
- Place them on a number line.
- In the rightmost interval, the sign is positive (for a monic polynomial with positive leading coefficient).
- The sign alternates at each simple root.
- The sign does not alternate at a repeated (even multiplicity) root.
This works for any degree, not just quadratics.
Absolute Value Equations and Inequalities
The absolute value \(|x|\) is defined as:
Absolute Value Equations
To solve \(|f(x)| = k\) (where \(k \geq 0\)): split into two cases.
Example: Solve \(|2x - 5| = 3\).
Case 1: \(2x - 5 = 3 \Rightarrow x = 4\).
Case 2: \(2x - 5 = -3 \Rightarrow x = 1\).
Solutions: \(x = 1\) and \(x = 4\).
Absolute Value Inequalities
Two key patterns:
The first keeps you close to zero (within distance \(k\)). The second pushes you far from zero.
Example: Solve \(|3x - 1| \leq 5\).
Example: Solve \(|x + 2| > 7\).
Why Absolute Values Matter in CP
The distance between two numbers on a number line is \(|a - b|\). Problems that ask "minimize the maximum distance" or "find all points within distance \(d\) of a target" are absolute value problems. The Manhattan distance \(|x_1 - x_2| + |y_1 - y_2|\) shows up in countless geometry problems.
The triangle inequality \(|a + b| \leq |a| + |b|\) is one of the most frequently used inequalities in competition math.
Connecting It All: Systems of Inequalities
In many CP problems, you need to find values satisfying multiple inequalities simultaneously.
Example: Find all integers \(x\) satisfying:
First inequality: \(x > 2\).
Second inequality: \(x < 6\).
Combined: \(2 < x < 6\), so \(x \in \{3, 4, 5\}\).
In competitive programming, this often looks like: "find the range of valid answers." Binary search on the answer often reduces to finding the boundary of a system of inequalities — "what is the largest \(x\) such that all constraints are satisfied?"
Practice Problems
Problem 1. Solve the system: \(4x + y = 14\) and \(x - y = 1\).
Solution
Add the equations: \(5x = 15\), so \(x = 3\).
Then \(y = 14 - 4(3) = 2\).
Solution: \((3, 2)\).
Problem 2. Solve \(x^2 - 4x - 5 \leq 0\).
Solution
Factor: \((x - 5)(x + 1) \leq 0\).
Roots: \(x = -1\) and \(x = 5\).
Sign analysis: the product is negative (or zero) between the roots.
Solution: \(-1 \leq x \leq 5\).
Problem 3. Solve \(|4x - 3| = |2x + 5|\).
Solution
Square both sides (valid since both sides are non-negative):
\((4x - 3)^2 = (2x + 5)^2\)
\(16x^2 - 24x + 9 = 4x^2 + 20x + 25\)
\(12x^2 - 44x - 16 = 0\)
\(3x^2 - 11x - 4 = 0\)
\((3x + 1)(x - 4) = 0\)
\(x = -\frac{1}{3}\) or \(x = 4\).
Check \(x = -\frac{1}{3}\): \(|{-\frac{4}{3} - 3}| = \frac{13}{3}\) and \(|{-\frac{2}{3} + 5}| = \frac{13}{3}\). Correct.
Check \(x = 4\): \(|16 - 3| = 13\) and \(|8 + 5| = 13\). Correct.
Problem 4. Find all integer solutions to the system:
Solution
From the first equation: \(y = 7 - x\). Substitute:
\(x(7 - x) = 10\)
\(7x - x^2 = 10\)
\(x^2 - 7x + 10 = 0\)
\((x - 2)(x - 5) = 0\)
\(x = 2, y = 5\) or \(x = 5, y = 2\).
Notice: \(x\) and \(y\) are roots of the quadratic \(t^2 - 7t + 10 = 0\). This is Vieta's in reverse — given sum and product, construct the quadratic whose roots are the unknowns. This technique appears often in competition math.
Problem 5. How many integers \(n\) satisfy \(|n - 3| + |n - 7| \leq 10\)?
Solution
Consider three cases based on the critical points \(n = 3\) and \(n = 7\):
Case 1: \(n \leq 3\). \(|n-3| + |n-7| = (3-n) + (7-n) = 10 - 2n \leq 10\). Always true for \(n \leq 3\) since \(-2n \leq 0\) when... wait, \(10 - 2n \leq 10\) means \(-2n \leq 0\) means \(n \geq 0\). So \(0 \leq n \leq 3\).
Case 2: \(3 < n < 7\). \(|n-3| + |n-7| = (n-3) + (7-n) = 4 \leq 10\). Always true. So \(4 \leq n \leq 6\).
Case 3: \(n \geq 7\). \(|n-3| + |n-7| = (n-3) + (n-7) = 2n - 10 \leq 10\). So \(n \leq 10\). Thus \(7 \leq n \leq 10\).
Combined: \(0 \leq n \leq 10\), giving 11 integers.
Problem 6 (Competition Style). Find all pairs of positive integers \((x, y)\) with \(x \leq y\) such that \(\frac{1}{x} + \frac{1}{y} = \frac{1}{4}\).
Solution
Multiply through by \(4xy\): \(4y + 4x = xy\).
Rearrange: \(xy - 4x - 4y = 0\).
Add 16 to both sides: \(xy - 4x - 4y + 16 = 16\).
Factor: \((x - 4)(y - 4) = 16\).
Since \(x, y > 4\) (if \(x \leq 4\), then \(\frac{1}{x} \geq \frac{1}{4}\), leaving no room for \(\frac{1}{y} > 0\)), we need \(x - 4\) and \(y - 4\) to be positive integers.
Factor pairs of 16 with \(x - 4 \leq y - 4\): \((1, 16), (2, 8), (4, 4)\).
Solutions: \((x, y) = (5, 20), (6, 12), (8, 8)\).
This used Simon's Favorite Factoring Trick — adding a constant to both sides to make the left side factorable. We cover this in depth in the next lesson!