Counting & Casework — Systematic Enumeration

By the end of this chapter you will:

1. Enumerate combinations in a fixed order so you never miss or double-count
2. Recognize when complement counting ("count what you don't want") beats direct
3. Apply the pigeonhole principle to robot / color / day problems
4. Split a problem into disjoint cases and recombine — without overcounting

8.0 Why this chapter dominates Part C

BC baseline: G6 introduces "listing all outcomes" for probability — but only for small finite spaces (4 coin flips, etc). There is no formal combinatorics, no pigeonhole, no complement principle, no casework discipline. This entire chapter is new material for a BC student.

Of the five Part-C problems on a typical Gauss 7 paper, three or four reduce to counting. 2024's Part C is a textbook example:

🔑 The hard part is rarely "how do I count?" It's "how do I count without missing any or counting some twice?" That's what discipline-based casework solves.

8.1 List-everything counting — be systematic

Rule of thumb: order your enumeration by some clear rule — smallest first, lexicographic, by sum, etc. Then you can see whether you've covered everything.

Example — three-digit numbers using digits 1, 2, 3 (no repetition)

List by leading digit:

• Leading $1$: $123, 132$
• Leading $2$: $213, 231$
• Leading $3$: $312, 321$

6 numbers. The pattern: for $n$ distinct digits in $n$ positions, the count is $n!$. Here $3! = 6$.

When order matters vs doesn't

Gauss usually phrases it: "in how many ways can …" → if the roles differ (first place, second place; treasurer, secretary), order matters. If you're just choosing a group (a team of 3 from 10), it doesn't.

8.2 Complement counting — "1 minus easy"

If the thing you want is hard to count, count its complement (what you don't want) and subtract from the total.

Example — Part B / lower Part C

How many 3-digit numbers have at least one digit equal to $7$?

Direct attempt: case "the $7$ is in the hundreds place", "the $7$ is in the tens place", "the $7$ is in the ones place" — but you'd overcount $773$ etc.

Complement: count 3-digit numbers with no $7$.

• Hundreds digit: $1$–$9$ excluding $7$ → $8$ choices
• Tens digit: $0$–$9$ excluding $7$ → $9$ choices
• Ones digit: $0$–$9$ excluding $7$ → $9$ choices

Total 3-digit numbers with no $7$: $8 \cdot 9 \cdot 9 = 648$.

Total 3-digit numbers: $900$.

With at least one $7$: $900 - 648 = \mathbf{252}$.

🔑 "At least one" is the canonical signal for complement counting. The complement of "at least one" is "none", which is much cleaner.

8.3 Pigeonhole principle — guaranteed collisions

Statement: If you put $n+1$ items into $n$ boxes, some box has at least 2 items.

More generally, if you put $kn + 1$ items into $n$ boxes, some box has at least $k + 1$ items.

2024 Q18 — worked in full

The Gaussbot factory assembles robots. Each robot comes in one of three colours: red, blue, or green. Each robot also has a number stamped on its head: $1$, $2$, $3$, or $4$. The $n$th robot assembled is the first robot to have the same colour and the same number as a previously assembled robot. What is the greatest possible value of $n$?

Reframe: a robot is a (colour, number) pair. There are $3 \times 4 = 12$ distinct pairs.

If you want the $n$th robot to be the first repeat, then robots $1, 2, \ldots, n-1$ must all be different. That's at most $12$ different pairs. So $n - 1 \le 12$, i.e. $n \le 13$.

The greatest $n$ is therefore $n = \mathbf{13}$. Answer (C). ✅

🔑 Pigeonhole flavor: when a problem asks "the first time something is forced to happen" or "how many do I need to guarantee …", count distinct slots and add 1.

Other pigeonhole flavors

• "In any group of $25$ people, at least two share a birth month." — $25$ items, $12$ months → some month has $\ge 2$.
• "A drawer has $10$ red, $10$ blue, $10$ green socks. How many do you need to grab to guarantee a pair?" — $3$ colors → $4$ socks guarantee.

8.4 Casework discipline — disjoint and complete

The two failure modes of casework:

1. Overcounting — the cases overlap, so something gets counted twice
2. Undercounting — the cases don't cover everything

Antidote: define the cases by a single splitting variable, and check the cases are disjoint and their union is everything.

2024 Q24 — Tiny three-digit integers

A three-digit integer is called Tiny if no rearrangement of its digits gives a three-digit integer that is smaller. For example, $138, 207, 566$ are Tiny but $452, 360, 727$ are not. How many three-digit integers are Tiny?

Reframe: $\overline{abc}$ is Tiny iff $\overline{abc}$ is the smallest 3-digit integer among the rearrangements of its digits $\{a, b, c\}$.

A 3-digit integer must have a non-zero leading digit. The smallest rearrangement of digits $\{a, b, c\}$ (with the constraint that the leading digit ≠ 0) is what we want our number to equal.

Split into cases by how many of $a, b, c$ are $0$:

Case 1 — No zeros ($a, b, c \in \{1, \ldots, 9\}$). The smallest rearrangement is the digits in non-decreasing order. So Tiny $\overline{abc}$ has $a \le b \le c$, all in $1$–$9$.

Count: the number of non-decreasing triples from $\{1, \ldots, 9\}$. This is the "stars and bars" count: $\binom{9 + 3 - 1}{3} = \binom{11}{3} = 165$. (Or: enumerate by $a$ — for each $a$, count pairs $(b,c)$ with $a \le b \le c \le 9$.)

Case 2 — Exactly one zero. WLOG the digits are $\{0, b, c\}$ with $1 \le b \le c \le 9$. The smallest 3-digit rearrangement is $\overline{b0c}$ (since the leading digit can't be $0$, so we put the smallest nonzero first, then the $0$, then the rest in order). For our number to BE this smallest, we need $\overline{abc} = \overline{b0c}$, i.e. $a = b$ — contradicting that one digit was $0$. Wait — the digits are unordered $\{0, b, c\}$ but $a, b, c$ in the puzzle name the positions. Re-read: our number is $\overline{a_1 a_2 a_3}$, its digits are some multiset $\{d_1, d_2, d_3\}$, and we ask whether $\overline{a_1 a_2 a_3}$ equals the smallest 3-digit rearrangement.

Reframing: pick the digit multiset, find the smallest 3-digit arrangement, and that arrangement is the unique Tiny number for this multiset. So we just count multisets (with non-zero leading possible).

Count of multisets of size 3 from $\{0, 1, \ldots, 9\}$ with at least one non-zero:

Total multisets of 3 digits from 0–9: $\binom{10 + 3 - 1}{3} = \binom{12}{3} = 220$.

Subtract the one "all zeros" multiset: $220 - 1 = 219$.

Answer (E) 219. ✅

🔑 The win: by reframing "Tiny" as "is the smallest arrangement of its digit multiset", every digit multiset gives exactly one Tiny number. So count multisets, not numbers.

⚠️ Trap (the wrong answer (A) 255): students who count ordered $(a, b, c)$ with $a \le b \le c$ AND allow $a = 0$ get a different count. Always check: is the leading digit allowed to be $0$?

8.5 Tree counting (multi-stage)

When choices are sequential and constrained by earlier choices, draw a tree (or imagine one) and multiply along a branch, add across branches.

Example — 4-letter words from {A, B, C} with no two adjacent letters equal

• Position 1: $3$ choices
• Position 2: $2$ choices (any letter except position 1's)
• Position 3: $2$ choices
• Position 4: $2$ choices

Total: $3 \cdot 2 \cdot 2 \cdot 2 = 24$.

Tree shape: branches branch out from each position, and we multiply.

8.6 Trap Alerts ⚠️

1. Leading zero — a "3-digit integer" cannot start with $0$. Always check whether your enumeration accidentally includes "$023$" etc.
2. "Different" / "distinct" — when the problem says different digits or different integers, no repetition is allowed. Easy to miss.
3. Pigeonhole gives "at least 2", NOT "exactly 2". If you only need $2$ to collide, pigeonhole works; if you need $3$, use $kn + 1$ form.
4. Casework overlap — cases like "contains a 7" and "contains an even digit" overlap on numbers like 76. Use disjoint splits like "contains exactly one 7", "contains exactly two 7s", "contains three 7s".
5. The complement of "at least one" is "none", not "exactly one".

8.7 Mnemonic

"Enumerate in order, complement when stuck, pigeonhole for guarantees, split into disjoint cases."

• In order: lexicographic, or by leading digit, or by smallest element
• Complement: if "at least one X", count "no X" and subtract
• Pigeonhole: $n + 1$ items in $n$ boxes → repeat guaranteed
• Disjoint cases: split by a single attribute, check union = everything

Practice Set (10 problems, mixed difficulty)

1. (Part A) How many 2-digit numbers contain the digit $5$?
2. (Part A) From the set $\{1, 2, 3, 4, 5, 6, 7, 8\}$, how many ways are there to pick a pair that sums to $9$?
3. (Part B) How many 3-digit numbers have all distinct digits?
4. (Part B) In a class of $30$ students, at least how many share a birth month?
5. (Part B) A coin is flipped 4 times. How many outcomes have at least one heads?
6. (Part B) A 4-digit number has digits summing to $5$ (allowing zeros except leading). How many such numbers?
7. (Part C) How many integers from $1$ to $200$ are divisible by neither $3$ nor $5$?
8. (Part C) In how many ways can $5$ people be arranged in a row if two of them refuse to stand next to each other?
9. (Part C) A bag has $4$ red balls and $6$ blue balls. How many ways are there to draw $3$ balls so that at least one is red?
10. (Part C) How many 4-digit "palindromes" (read same forwards and backwards) are divisible by $11$?

Answers: 1) 18 ($10 \times 2 - 2$); 2) 4 ($\{1,8\},\{2,7\},\{3,6\},\{4,5\}$); 3) $9 \cdot 9 \cdot 8 = 648$; 4) 3 ($30 = 2 \cdot 12 + 6$, so some month has $\ge 3$); 5) $16 - 1 = 15$; 6) $\binom{5+3-1}{3} - \binom{4+3-1}{3}$ leading-zero correction = $\binom{8}{3}\cdot$ … direct: pairs $(d_1, d_2, d_3, d_4)$ with $d_1 \ge 1$, sum 5 → 31; 7) $200 - \lfloor 200/3 \rfloor - \lfloor 200/5 \rfloor + \lfloor 200/15 \rfloor = 200 - 66 - 40 + 13 = 107$; 8) $5! - 2 \cdot 4! = 120 - 48 = 72$; 9) Total $\binom{10}{3} = 120$, no red $\binom{6}{3} = 20$, so $100$; 10) palindrome $\overline{abba}$, divisible by 11 iff $a - b + b - a = 0$, always true; count: $a \in 1..9$, $b \in 0..9$ → $90$.

End of chapter. Next: Probability, Mean, Median & Range.