Clever Counting & Logic

Why "not" is so often easier: a condition like "contains at least one $7$" can be met in many overlapping ways (the $7$ could be in any position, or in several), but its opposite, "contains no $7$", is one restriction applied to every digit separately — and independent restrictions multiply. Parity arguments are the same kind of shortcut: they replace a computation by a count of odd terms.

Step 1 — pad with zeros so every number has three digits, $000$ to $999$.

Step 2 — each digit avoids $5$ in $9$ ways, independently: $9^3 = 729$ strings.

Step 3 — that includes $000$, which is not in the range: $729 - 1 = 728$. Padding makes the positions independent; removing $000$ is the price.

Step 1 — add up the handshakes each person makes: $7\cdot3 = 21$.

Step 2 — every handshake involves two people, so this total counts each handshake twice and must be even.

Step 3 — $21$ is odd. Impossible. Parity settled it without trying a single arrangement.

From $(0,0)$ to $(4,3)$ there are $\dbinom73 = 35$ paths. Blocked squares are handled by subtraction: count all paths, then subtract those through the blocked point, which is a product of two smaller path counts. That "through a point" factorisation — paths to it, times paths from it — is the whole technique.

Ten people make $45$ handshakes; a decagon has $\dfrac{10\cdot7}{2} = 35$ diagonals. The trap is the factor of two: counting "each of $10$ people shakes $9$ hands" gives $90$, which counts every handshake from both ends. Whenever a count seems to be exactly twice what it should be, look for an ordered/unordered mismatch.

Step 1 — all paths: $\dbinom73 = 35$.

Step 2 — paths through $(2,1)$: $\dbinom31\cdot\dbinom42 = 3\cdot6 = 18$.

Step 3 — subtract: $35 - 18 = 17$. The middle step is the product rule: a path through $(2,1)$ is a path to it followed by a path from it, chosen independently.

Step 1 — the diagonal count is $\dfrac{n(n - 3)}{2}$: each vertex joins to the $n - 3$ vertices that are not itself or its neighbors, and each diagonal is counted from both ends.

Step 2 — $n(n - 3) = 40$; try values: $n = 8$ gives $8\cdot5 = 40$.

Step 3 — an octagon.

Why the corrections: $|A| + |B|$ counts everything in the overlap twice, once in each set, so the overlap is subtracted once. With three sets, a point in all three is added three times and subtracted three times, leaving it uncounted — so it is added back once. The Venn diagram shows the same bookkeeping region by region, and filling it from the INSIDE out (triple overlap first) avoids every sign error.

Step 1 — at least one sport: $18 + 14 - 7 = 25$.

Step 2 — neither: $30 - 25 = 5$. In the diagram: both $7$, soccer only $18 - 7 = 11$, basketball only $14 - 7 = 7$, and $11 + 7 + 7 = 25$.

Step 1 — multiples of $3$: $\lfloor 100/3\rfloor = 33$; of $5$: $20$.

Step 2 — both means divisible by $15$: $6$ of them.

Step 3 — $33 + 20 - 6 = 47$.

Step 1 — singles: $50 + 33 + 20 = 103$.

Step 2 — pairs: divisible by $6$: $16$; by $10$: $10$; by $15$: $6$; subtract $32$.

Step 3 — all three, divisible by $30$: $3$; add back.

Step 4 — $103 - 32 + 3 = 74$. So $26$ numbers from $1$ to $100$ are divisible by none of $2$, $3$, $5$.

Step 1 — complement: count those divisible by $2$ or $3$ and subtract from $60$.

Step 2 — inclusion–exclusion: $30 + 20 - 10 = 40$ (the $10$ are multiples of $6$).

Step 3 — $60 - 40 = 20$. These are the numbers leaving remainder $1$ or $5$ on division by $6$: two in every block of six, and $60$ is ten blocks.