Cases and Enumeration

In one sentence

Use one ruler all the way through: no overlaps, no gaps.

Some problems cannot be done in one go, because “different situations need different methods”. So do them separately. Case analysis has just three rules:

One rule for splitting: split by one thing at a time (by the longest side, by the remainder, by where the axis of symmetry is…).
No overlaps: every situation falls into exactly one case.
No gaps: all the cases together cover every situation.

Once you have split, each case knows one more fact than the original problem, so it becomes easier.

Predict first

The parabola $y = x^{2} - 2 x - 3$ has axis of symmetry $x = 1$ . To find its minimum on the interval $[p, p + 3]$ , how many cases do you need when you split by “where the axis is relative to the interval”?

2

3

4

Choose an answer first; then you can see the result.

Stop 1 · Maxima and minima of quadratic functions (Vol. 3)

Example: find the minimum of y = x² − 2x − 3 on [p, p + 3]

Step 1 / 5

First choose the rule
Complete the square: $y = (x - 1)^{2} - 4$ , axis $x = 1$ , opening upward. Where the minimum is reached depends only on which side of the interval the axis is on.

$y = (x - 1)^{2} - 4$
Case 1: axis to the right of the interval
Case 2: axis inside the interval
Case 3: axis to the left of the interval
Check: no overlaps, no gaps

A boundary point may go into either case, but only into one. The values from the two sides should agree at the boundary: a good way to check that your cases are right.

Stop 2 · Equations with letter coefficients (Vol. 2)

When solving $a x = b$ , the step “divide by $a$ ” is only allowed when $a \neq = 0$ . An equation with letter coefficients needs case analysis from the start.

Example: solve m²x − 1 = x + m for x

Step 1 / 5

Rearrange to ax = b
Move the terms with $x$ to the left and the rest to the right, then factor both sides.

$(m^{2} - 1) x = m + 1 ⟺ (m - 1) (m + 1) x = m + 1$
The rule: is the coefficient of x zero?
Case 1: m ≠ ±1
Case 2: m = −1
Case 3: m = 1

Both have “coefficient $0$ ”, but one has infinitely many solutions and the other has none. That is why they cannot be merged into one case.

Stop 3 · Counting (Vol. 7)

The worst way to count is to count in a muddle. Line the objects up by one rule, and each case can be counted at a glance.

How many triangles have integer side lengths and perimeter $15$ ? (Triangles with the same three sides count as one.)

Example: integer-sided triangles with perimeter 15

Step 1 / 6

Sort first, so nothing repeats
Agree that $a \leq b \leq c$ . Then $(3, 5, 7)$ and $(7, 3, 5)$ are counted only once: that is “no overlaps”.

$a \leq b \leq c, a + b + c = 15$
The rule: the longest side c
c = 5
c = 6
c = 7
Add them up

Stop 4 · Diophantine equations (Vol. 6)

There are infinitely many integers, so you cannot try them one by one. But split by the remainder on division by $5$ , and all integers fall into just $5$ cases: infinitely many situations become five.

Example: prove that n² + n + 1 is never a multiple of 5

Step 1 / 4

The rule: the remainder of n on division by 5
Every integer $n$ can be written as $5 k + r$ with $r = 0, 1, 2, 3, 4$ . No overlaps, no gaps: exactly five cases.

$n = 5 k + r$
The remainder is all you need
Work out the five cases
Conclusion

Practice

Exercise 1Basic

How many triangles have integer side lengths and perimeter $13$ ?

Exercise 2Advanced

The equation $(m^{2} - 4) x = m + 2$ in $x$ has no solution. Find $m$ .

Exercise 3Challenge

The minimum of $y = x^{2} - 4 x + 5$ on the interval $[t, t + 1]$ is $2$ . Find all possible values of $t$ (separated by commas).

Mistake Museum · Exhibits from this stop

Before you leave, look at the traps other people fell into here.See every exhibit in the museum →

Exhibit

Dividing without checking for zero

Solve

(m - 1) x = m - 1

for

x

: divide both sides by

m - 1

to get

x = 1

What went wrong? Think first, then open

Diagnosis When $m = 1$ , $m - 1 = 0$ , and you cannot divide by $0$ . The equation is then $0 \cdot x = 0$ , and every number is a solution, not just $x = 1$ .

Split into cases first: if

m \neq = 1

x = 1

; if

m = 1

x

can be any number. Whenever you divide by an expression with letters in it, first ask whether it can be

0

“Before dividing by a letter, ask whether it can be zero”

Exhibit

Forgetting each case’s own conditions

An isosceles triangle has perimeter

12

and integer sides. Sorting by the length of the equal sides, they can be

1, 2, 3, 4, 5

, so there are

5

triangles.

What went wrong? Think first, then open

Diagnosis Each case has to pass two tests. The base $12 - 2 a$ must be positive, so $a \leq 5$ ; the two equal sides must add up to more than the base, $2 a > 12 - 2 a$ , so $a > 3$ . With equal sides $1, 2, 3$ there is no triangle at all (for example $3, 3, 6$ ).

The equal sides can only be

4

5

(4, 4, 4)

and

(5, 5, 2)

, so

2

triangles. Splitting into cases only cuts the problem into pieces; the conditions inside each piece still have to be checked one by one.

“After working out each case, go back and check that case’s conditions”

In one sentence

Stop 1 · Maxima and minima of quadratic functions (Vol. 3)

Stop 2 · Equations with letter coefficients (Vol. 2)

Stop 3 · Counting (Vol. 7)

Stop 4 · Diophantine equations (Vol. 6)

Practice

Mistake Museum · Exhibits from this stop

Stops on this line