Self-Assessment Quiz: The Basics of Counting

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+. The recurring theme is not the arithmetic but the proviso: every rule is valid only under a condition you must verify.

Question 1

The product rule applies to a sequence of $k$ steps only when:

A) every step has the same number of options B) the number of options at each step does not depend on the earlier choices C) the steps are mutually exclusive D) there are exactly two steps

Question 2

A meal is one of 3 appetizers and one of 4 mains. The number of distinct meals is:

A) $3 + 4 = 7$ B) $3 \times 4 = 12$ C) $4^3 = 64$ D) $3! \cdot 4! = 144$

Question 3

The sum rule, $\lvert A_1 \cup \cdots \cup A_k \rvert = \lvert A_1 \rvert + \cdots + \lvert A_k \rvert$, requires that the sets be:

A) all the same size B) pairwise disjoint (mutually exclusive) C) subsets of one another D) nonempty

Question 4

How many 8-character strings over the 26 lowercase letters are there, repeats allowed?

A) $26 \times 8$ B) $8^{26}$ C) $26^8$ D) $26!/18!$

Question 5

How many 8-character strings over the 26 lowercase letters use all distinct letters?

A) $26^8$ B) $26 \times 25 \times 24 \times 23 \times 22 \times 21 \times 20 \times 19$ C) $26 \times 8$ D) $8^{26}$

Question 6

"Choose a 2-letter string whose two letters are in alphabetical order." Why is this not counted by the product rule as $26 \times 25$?

A) repeats are not allowed B) the number of valid second letters depends on which first letter was chosen C) the two steps are not mutually exclusive D) it is actually $26 \times 26$

Question 7

For finite sets, $\lvert A \cup B \rvert$ equals:

A) $\lvert A \rvert + \lvert B \rvert$ B) $\lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert$ C) $\lvert A \rvert \times \lvert B \rvert$ D) $\lvert A \rvert + \lvert B \rvert + \lvert A \cap B \rvert$

Question 8

How many integers from 1 to 100 are divisible by 2 or by 5?

A) $50 + 20 = 70$ B) $50 + 20 - 10 = 60$ C) $50 + 20 - 25 = 45$ D) $\lfloor 100/10 \rfloor = 10$

Question 9

In the three-set formula, the triple intersection $\lvert A \cap B \cap C \rvert$ is added back because:

A) it makes the formula symmetric B) each of its elements is added 3 times (singles) and subtracted 3 times (pairs), netting to zero C) it was never counted at all D) the signs must always alternate starting with $+$

Question 10

The number of multiples of $d$ in the range $1$ to $N$ is:

A) $N / d$ exactly B) $\lfloor N/d \rfloor$ C) $\lceil N/d \rceil$ D) $N - d$

Question 11

"Divisible by both $a$ and $b$" is the same as "divisible by":

A) $a + b$ B) $a \times b$ always C) $\operatorname{lcm}(a, b)$ D) $\gcd(a, b)$

Question 12

Four people are seated around a circular table; rotations are considered the same seating. The number of distinct seatings is:

A) $4! = 24$ B) $4!/4 = 6$ C) $4^4 = 256$ D) $4!/2 = 12$

Question 13

The division rule, "true count $= N/d$," is valid only when:

A) $N$ is divisible by $d$ by coincidence B) every object is over-counted by the same number $d$ of copies C) the objects form a Cartesian product D) $d = 2$

Question 14

You want the number of 8-character passwords (over some alphabet) with at least one digit. The easiest correct approach is usually:

A) add up the cases "exactly 1 digit," "exactly 2 digits," … B) (all strings) − (strings with no digit) C) $8 \times (\text{number of digits}) \times (\text{remaining})$ D) the product rule directly

Question 15

A keyspace of size $K$ is searched at $r$ guesses per second. The worst-case brute-force time is approximately:

A) $K \times r$ B) $K / r$ C) $r / K$ D) $\log_2 K$

Question 16 (True/False, justify)

True or false: If two sets $A$ and $B$ are disjoint, then two-set inclusion-exclusion gives the same answer as the sum rule. Justify in one sentence.

Question 17 (True/False, justify)

True or false: The number of bit strings of length 8 that start with 1 or end with 00 is $2^7 + 2^6 = 192$. Justify in one sentence.

Question 18 (True/False, justify)

True or false: Adding one independent 32-bit field to a configuration multiplies the size of its state space by $2^{32}$. Justify in one sentence.

Question 19 (Short answer)

State the "fatal proviso" — the condition that, if violated, makes the rule give a wrong answer — for each of: (a) the product rule, (b) the sum rule, (c) the division rule.

Question 20 (Short answer)

In one sentence each, give the trigger that should make you reach for (a) the product rule, (b) the sum rule, (c) inclusion-exclusion, (d) the subtraction principle.

Answer Key

Topics to review by question