The Principle of Classification

In one sentence

The principle of classification: let $M$ be the whole collection of objects you are studying. Split it into classes that are pairwise disjoint and whose union is $M$ (a partition of $M$ ), then deal with the classes one at a time.

Classifying is not hard in itself; the hard part is choosing the criterion. A good criterion passes one test: once you know which class an object is in, you can decide the question you are asking. The workbench above counts “pairs whose sum is a multiple of $3$ ”, and only one of the three criteria passes this test.

Count the pairs from 1–12 whose sum is a multiple of 3

Step 1 / 4

Brute force
There are $66$ pairs; checking them one by one gives $22$ . A computer can do this, a person cannot, and once $N$ is large it gets out of hand.
Classify by parity
Classify by remainder mod 3
Count class by class

Stop 1 · Divisibility: classify by remainder

In how many ways can you choose two numbers from $1 \sim 12$ whose product is a multiple of $4$ ? Classifying by parity seems natural, but in the “odd·even” cell $1 \times 2$ fails while $1 \times 4$ works. What should you classify by to make it clean?

Classify by remainder mod

4

, and every cell can be decided.

Classifying by remainder mod $4$ makes it clean. But there are so many ✓ cells that adding them up is tiring. It is easier to count the pairs that fail instead: the product is not a multiple of $4$ only for “two odd numbers” ( $C_{6}^{2} = 15$ pairs) or “an odd number with a number that leaves $2$ mod $4$ ” ( $6 \times 3 = 18$ pairs). So the answer is $66 - 15 - 18 = 33$ .

Stop 2 · Equations: classify by sign

Absolute value is defined piecewise, so equations with absolute values call for cases: the zeros cut the number line into pieces, and on each piece every absolute value can simply be removed.

Predict first

How many real solutions does $∣ x - 1∣ + ∣ x + 2∣ = 5$ have?

0

1

2

Infinitely many

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

The $x$ you find on each piece only counts if it lies in that piece. This is the check most often forgotten in case analysis.

Stop 3 · Counting: classify by the largest element

In how many ways can you choose $3$ numbers from $1 \sim 10$ ? The answer is of course $C_{10}^{3} = 120$ , but classifying by “what the largest number is” gives an identity:

Classify by the largest element

Step 1 / 3

Classify
The largest of the three numbers can only be one of $3, 4, \dots, 10$ . Splitting by it gives $8$ classes, with nothing left out and nothing counted twice.

$k = max \in {3, 4, \dots, 10}$
Each class
Add up

The same objects counted in two ways: this is the seed of “counting in two ways”. The largest element is chosen as the criterion precisely because, once it is fixed, the remaining choices no longer depend on each other.

Practice

Exercise 1Basic

In how many ways can you choose two different numbers from $1 \sim 20$ whose sum is a multiple of $3$ ?

Exercise 2Basic

Solve $∣ x + 1∣ - ∣ x - 3∣ = 2$ .

Exercise 3Advanced

In how many ways can you choose two different numbers $a, b$ from $1 \sim 15$ such that $a^{2} + b^{2}$ is a multiple of $5$ ?

Exercise 4Challenge

In how many ways can you choose $3$ different numbers from $1 \sim 12$ whose sum is a multiple of $3$ ?

In one sentence

Count the pairs from 1–12 whose sum is a multiple of 3

Stop 1 · Divisibility: classify by remainder

Stop 2 · Equations: classify by sign

Stop 3 · Counting: classify by the largest element

Classify by the largest element

Practice

Mistake Museum · Exhibits from this stop

Leaving out the boundary points in a case split

Mixing two criteria, so the classes overlap