Clever Counting & Logic

Study Sheet

Clever Counting & Logic

Complements, casework, and parity

Counting Without Listing

Tip
The complement trick

Sometimes the easiest way to count what you want is to count what you do NOT want: ∣A∣=∣total∣−∣not A∣|A| = |\text{total}| - |\text{not } A|.

In plain terms. Count everything, count the "bad" ones, subtract.

Example. How many 3-digit numbers contain at least one 7? Total: 900900. With no 7s: 8⋅9⋅9=6488 \cdot 9 \cdot 9 = 648. So 900−648=252900 - 648 = 252.

Concept
Casework that stays organized

Split the count into cases that do not overlap and together cover everything, then add the case counts.

In plain terms. Sort the possibilities into non-overlapping piles and count each pile.

Example. Two dice sum to 55: the cases are (1,4),(2,3),(3,2),(4,1)(1,4), (2,3), (3,2), (4,1) — exactly 44 ways.

Tip
Parity (odd/even) arguments

The parity of a sum depends only on how many ODD terms it has — an even number of odd terms gives an even sum.

In plain terms. You can often decide odd vs. even without computing anything.

Example. 1+2+⋯+9=451 + 2 + \cdots + 9 = 45 is odd because it contains five odd terms, and 55 is odd.