PR-3: Solutions — Counting Techniques

Problem 1 — Fundamental Counting Principle (Variants 0–4)

The FCP multiplies the number of choices at each independent stage — the options at each stage must not depend on earlier choices. Adding stage counts gives only the total number of single-stage options, not complete multi-stage outcomes.

• Variant 0 (breakfast: 3 eggs × 4 toast × 2 drinks): breakfasts.
• Variant 1 (locker dials, repetition allowed): settings — each dial’s 6 options are independent.
• Variant 2 (essay: 5 topics × 3 formats × 4 fonts): .
• Variant 3 (plate: 2 letters × 3 digits, repetition allowed): .
• Variant 4 (pizza: 2 sizes × 3 sauces × 5 toppings): .

Problem 2 — Permutation Calculation (Generator)

When order matters and selection is without replacement:

Example (, — top 3 finishers): . The stages are dependent — each placement removes one runner.

Problem 3 — Combination Calculation and Symmetry (Variants 0–4)

Each variant verifies — choosing to include is the same as choosing to exclude.

• Variant 0 (3 from 10): ✓.
• Variant 1 (2 from 8): ✓.
• Variant 2 (4 from 6): ✓.
• Variant 3 (5 from 9): ✓.
• Variant 4 (3 from 7): ✓.

Problem 4 — Permutation vs. Combination Decision and Counting Probability

(a) A combination — 3 students are selected for presentations with no ordering of slots, so the same 3 in any order form the same group.

(b) equally likely groups.

(c) Exactly 2 of 3 have completed volunteering: choose 2 of the 8 volunteers AND 1 of the 12 non-volunteers — . (Adding would count one choice, not both.)

(d) — combinations in both numerator and denominator.

Problem 1 — FCP Probability (Generator)

1. Total outcomes via FCP (multiply the options at each stage).
2. Favorable outcomes: same product, but the restricted stage uses its smaller favorable count.
3. .

If a 3-stage process has options and a restriction limits stage 1 to : When the restriction touches only one stage, the probability is just the favorable proportion at that stage.

Problem 2 — Permutation vs. Combination Classification (Variants 0–4)

• Variant 0 (ordered reading list, 4 from 9): permutation — .
• Variant 1 (jury of 5 from 12, no roles): combination — .
• Variant 2 (gold/silver/bronze from 7): permutation — .
• Variant 3 (2 scoops from 8, order irrelevant): combination — .
• Variant 4 (4-char password from 10 letters, ABCD ≠ DCBA): permutation — .

Problem 3 — Combination-Based Probability (Generator)

For “from people ( with a trait), choose — find ”: The numerator multiplies two independent counts: trait-holders from , and others from .

Example (, , , ): ; ; .

Problem 4 — Find the Error (Variants 0–4)

• Variant 0 (lineup of 4 from 7, used ): permutation for an unordered group. Correct: (the ratio confirms the overcount).
• Variant 1 (3-digit code, all different, used ): treated dependent stages as independent. Correct: .
• Variant 2 (hire 2 from 12, computed then doubled to 132): unwarranted doubling turns a combination into a permutation. Correct: (no roles → no ordering).
• Variant 3 (5 people in a row, used ): as if one person could occupy several seats. Correct: .
• Variant 4 (claimed ): confused with 0; by definition . Correct: .

Problem 5 — Synthesis: Hiring Committee

(a) Total ways to pick 6 from 15: .

(b) Exactly 4 experienced (and 2 inexperienced): — independent selections, so multiply.

(c) .

(d) For : the direct sum (exactly 4, 5, 6) has 3 terms; the complement () needs exactly 0, 1, 2, 3 — 4 terms. Direct is fewer here; the complement wins only when it has fewer cases.

Problem 1 — Feynman Test

The FCP multiplies the choices at each stage only when they are independent — the number of options at any stage must not change based on earlier choices. Selecting without replacement makes the stages dependent: each choice removes one option.

Counterexample — distinct digits: “4-digit codes from 0–9 with no repeats.” Incorrect: . Correct: — a digit used at one position can’t reappear. The words “no repeats,” “distinct,” “without replacement” always signal dependent stages.

Problem 2 — Apply: Required Committee Member

A council of 8 forms a 3-person committee that always includes the president.

(a) Fix the president; fill the other 2 spots from the remaining 7: committees.

(b) Total unrestricted committees: , so . Check via complement: , so ✓.

Problem 3 — Error Analysis

Error: used a combination for a ranked contest (1st/2nd/3rd are distinct), which ignores order.

Correct: ranked outcomes. And ✓ — each unordered group of 3 can be ranked in orders. Permutation = combination × internal arrangements.

Path A — The Cryptographer

Passcodes of exactly 4 characters from a 36-character set (0–9, A–Z), no repeats.

Task 1 — Total (no repetition): (dependent stages).

Task 2 — First character a digit: restrict stage 1 to 10 digits; stages 2–4 draw from the remaining 35, 34, 33: .

Task 3 — : — the proportion of digits in the set.

Task 4 — With repetition (): . With repetition, all 4 positions independently have 36 options (truly independent stages); without it, choices decrease 36 → 35 → 34 → 33 (dependent).

Path B — The Tournament Director

10 teams; directors dispute the number of gold-silver-bronze podiums.

Task 1 — Who is right? Director B: . Director A used a combination (), but gold/silver/bronze are distinct — order matters, undercounting by : ✓.

Task 2 — Organizing committee (3 teams, no hierarchy): unordered → committees.

Task 3 — : favorable , total , so .

Task 4 — : favorable (any of 8 teams for bronze), total , so .

Challenge 1 — Algebraic Proof + Combinatorial Argument

(a) Algebraic proof that : substitute for : The key is , so the denominator is — the same as for .

(b) Combinatorial argument: choosing objects to include from simultaneously determines objects to exclude; each inclusion uniquely fixes its complementary exclusion. So the count of -inclusions equals the count of -exclusions. Check (, ): all pairs from map to 10 complementary triples, so .

(c) Efficient evaluation: — no need for .

Challenge 2 — Complement Technique (Generator)

For a 5-card hand from 52 with at least one card from a specified suit, counting the complement (no cards from the suit) is far easier than summing exactly 1–5 from the suit: Each suit has 13 cards (39 non-suit), so the computation is identical across suits.

Challenge 3 — Restricted Arrangements (Block Method)

Six friends seated in a row of 6 chairs.

(a) Total: .

(b) Alex and Blake adjacent: treat them as one “AB block,” giving 5 entities → arrangements; within the block orders. So .

(c) Not adjacent: .

(d) . Equivalently , so ✓.