Week 14 · Part 1 — Advanced Inclusion–Exclusion, Derangements & Stars and Bars0%
STEP 1 OF 22 · Lesson Opening
Today: General n-set PIE, Derangements & Stars and Bars with Constraints (Pass 3)
Pass 3 of counting. We push inclusion–exclusion past two and three sets to the full n-set formula, derive the derangement number $D_n$ from it, and learn to count constrained integer compositions via stars and bars + PIE. Finally we install the decisive habit of every Q8–Q10 counter: decide complement vs. direct before you start writing.
📌 What you will learn today
Topic
General PIE $|A_1\cup\cdots\cup A_n| = \sum|A_i| - \sum|A_i\cap A_j| + \cdots + (-1)^{n+1}|A_1\cap\cdots\cap A_n|$; derangements $D_n = n!\sum_{k=0}^{n}\dfrac{(-1)^k}{k!}$; stars and bars $\binom{n+k-1}{k-1}$ with upper-bound constraints via PIE; complement-vs-direct judgment for Q8–Q10.
Plus a Phase 5.5 synthesis combining derangements with selection (the "exactly 3 wrong" problem).
AoPS Reference
Intermediate Counting & Probability by David Patrick, Chapter 10 (Inclusion–Exclusion), Chapter 11 (Derangements), Chapter 9 §3 (Distributions / Stars & Bars). Engel — Problem-Solving Strategies, §1 "The Inclusion–Exclusion Principle".
Why this matters
Every Q8–Q10 counting problem at AIMO either is a PIE problem, or becomes one after a single reframe. The mark difference between Q5 and Q9 counters is not creativity — it is the muscle of writing the alternating sum cleanly with the right binomial multipliers. Today we lock that in, then add derangements and constrained stars-and-bars as named special cases.
Time required
About 95–115 minutes for the full lesson, plus practice.
Phase 1.5 (Step 6): Formula handbook — F1 general PIE; F2 complement; F3 derangement; F4 stars and bars (with upper bounds via PIE).
Phase 2 (Steps 7–9): Three guided derivations — general PIE via induction + Venn; derangement formula from PIE; complement-vs-direct decision rule.
Phase 3 (Steps 10–14): Five worked examples WE1–WE5 ⭐⭐⭐ → ⭐⭐⭐⭐⭐.
Phase 4 (Step 15): Five practice problems (P1–P5) with Hint / Answer / Solution.
Phase 5 (Steps 16–19): Four AIMO-grade problems — Q7–Q9 difficulty — with full Observe / Strategy / Hints / integer input / grading / error book.
Phase 5.5 (Step 20): Synthesis — "exactly 3 wrong" envelope problem combining selection $\binom{8}{5}$ and $D_3$.
Step 21: ⭐ Self-assessment (4 atomic skills).
Step 22: Error book + 🏁 wrap-up.
Pedagogy: Pass 3 — assumes Pass 1 (W6 — basic counting) and Pass 2 (W7 — 2/3-set PIE, pigeonhole, basic binomial) are comfortable. Today's win condition: when you see a Q8 counting problem, you finish a sentence "the answer is universe minus union" or "use PIE on the violations" inside 30 seconds, then write the alternating sum with correct $\binom{n}{k}$ multipliers without flipping a sign.
The four atomic skills today
Code
Skill
Trigger
C1-A1
General $n$-set PIE formula
"at least one of $n$ properties holds"
C1-A2
Derangement $D_n \approx n!/e$
"none in its own place" / "all wrong"
C1-A3
Stars & Bars with $0\le x_i\le k$ constraints
"non-negative integer solutions with upper bounds"
C1-A4
Complement-vs-direct judgment
"at least one" vs. "none" — pick the shorter side
What we are deliberately NOT doing today
Exponential generating functions for derangements — Part 4 (introduction only).
Möbius inversion on the lattice of partitions — beyond AIMO.
Exactly-$k$-fixed-point distributions in their full $E_k = \sum (-1)^j \binom{k+j}{j} S_{k+j}$ form — we mention it, but only treat $E_0 = D_n$ today.
Catalan / lattice path — that is Part 2 of this week.
STEP 2 OF 22 · Phase 0 · 5-min recap drill
Phase 0 — Quick-recall: W6 + W7 counting skills
Before we push PIE to $n$ sets and meet derangements, lock in the 8 skills you already own from Pass 1 + 2. Ten 30-second questions. Hit "Check" to confirm.
Q1. Number of ways to arrange 5 distinct books on a shelf? (Skill: $P(n,n) = n!$)
Q2. From 9 students, choose 3 to form a committee (order does not matter). How many ways? (Skill: $\binom{n}{k}$)
Q3. From 10 horses, how many ways to fill a podium (1st, 2nd, 3rd)? (Skill: $P(n,k)$)
Q4. A coin is flipped 4 times. How many sequences? (Skill: multiplication principle)
Q5. Number of subsets of $\{1,2,\dots,7\}$? (Skill: $2^n$)
Q6. In a class of 30, 18 like maths and 14 like physics; 6 like both. How many like neither? (Skill: 2-set PIE + complement)
Q7. Among integers 1–100, how many are divisible by 2 or by 5? (Skill: 2-set PIE; use $|A|+|B|-|A\cap B|$)
Q8. If 13 socks are pulled from a drawer holding socks of 4 colours, what is the largest $k$ such that "at least $k$ socks of one colour" is forced? (Skill: pigeonhole $\lceil n/m\rceil$)
Q9. Coefficient of $x^3$ in $(1+x)^7$? (Skill: binomial $\binom{n}{k}$)
Self-mark: 8+ correct → you're warm; jump in. 5–7 → glance back at the W6/W7 cheat sheets after the lesson. Below 5 → revisit W6 Part 4 and W7 Part 1 before tackling Pass 3 today.
STEP 3 OF 22 · Phase 1 · Visual ① — 4-set Venn (PIE)
Phase 1 — Visual ①: The 4-set Venn and why the signs alternate
Two sets have $4$ regions, three sets have $8$, four sets have $16$. Every element lives in exactly one region. The alternating sum of singles − pairs + triples − quadruples "balances" the over-counting in each region so that every element contributes exactly $1$ to the union.
Each element of $A_1\cup A_2\cup A_3\cup A_4$ falls in exactly one of the 15 interior regions. PIE adds and subtracts by region cardinality so each region counts exactly once.
Why the alternating sign? (region-by-region check)
An element in exactly $j$ sets ($1 \le j \le n$) is counted
by the binomial identity $\sum_{i=0}^{j} (-1)^i \binom{j}{i} = 0$ rearranged. So every element in the union is counted exactly once — independent of $n$ or $j$. That is the proof.
Mental anchor: "Add singles, subtract pairs, add triples, subtract quads, …" — the sign on a $k$-fold intersection is $(-1)^{k+1}$.
STEP 4 OF 22 · Phase 1 · Visual ② — Complement trick
Phase 1 — Visual ②: Complement = Universe − Union
"At least one bad thing happens" is usually messy; "no bad thing happens" is usually clean. The complement trick swaps one for the other.
Whatever is not inside any circle is the complement of the union.
Decision rule (atomic skill C1-A4): if "at least 1" feels hard to compute directly but "all $A_i^c$" (none of the properties hold) is easy, then compute the complement and subtract. Most Q8–Q9 phrased as "at least one" yield to this.
STEP 5 OF 22 · Phase 1 · Visual ③ — Stars and Bars
Phase 1 — Visual ③: Stars and Bars — the dots and dividers picture
$x_1 + x_2 + x_3 = 7$ with $x_i \ge 0$ becomes: lay out 7 stars in a row, then drop 2 bars somewhere among them to split into 3 groups. Each arrangement is one solution.
Stars + bars = $7 + 2 = 9$ positions. Choosing the 2 bar-positions counts the solutions: $\binom{n+k-1}{k-1}$.
$\#\{x_i \ge 1\} \;=\; \binom{n-1}{k-1}$ (give each $x_i$ a free "1" first)
Upper-bound constraint: if also $x_i \le c$ for every $i$, you cannot just plug a formula. You take the unconstrained count and subtract by PIE the bad sets "$x_i \ge c+1$". We will do this in WE3.
STEP 6 OF 22 · Phase 1.5 · Formula handbook
Phase 1.5 — Formula handbook (F1–F4)
Four formulas, four atomic skills. Memorise the LHS = RHS shape; the rest of today is just specialisations.
How to read F4 with cap: the binomial $\binom{n-j(c+1)+k-1}{k-1}$ is the count after pre-substituting "violation $i_1, \dots, i_j$" — i.e. $x_{i_\ell} \to x_{i_\ell}' + (c+1)$ in $j$ chosen coordinates. The sum truncates automatically once $n - j(c+1) < 0$ (the binomial is $0$).
STEP 7 OF 22 · Phase 2 · Derivation ① — General PIE
Phase 2 — Derivation ①: General PIE by induction (and the binomial identity)
Two proofs side-by-side. The induction is the textbook proof; the binomial identity proof is the one to remember on the day.
Proof by induction on $n$
Base case $n=2$: $|A_1\cup A_2| = |A_1| + |A_2| - |A_1\cap A_2|$ (drawn in W7).
Inductive step: Assume PIE holds for $n-1$ sets. Set $B = A_1\cup\cdots\cup A_{n-1}$ and apply the 2-set identity:
Both $|B|$ and the right-most union are unions of $n-1$ sets — expand them by IH and collect like terms. Every $k$-fold intersection ($k=1,\dots,n$) appears with the right sign. Done.
Proof by binomial identity (the "regions" argument)
Pick any element $x\in\bigcup A_i$ that lies in exactly $j$ of the sets ($1 \le j \le n$). Count its contribution on the RHS of the PIE formula:
(We used $(1-1)^j = \sum (-1)^k\binom{j}{k} = 0$.) Every union-element contributes exactly $1$, and elements outside the union contribute $0$. Hence LHS = RHS. Done.
Take-away: the binomial-identity proof is the one to write in 60 seconds under exam time. "Pick $x$ in exactly $j$ sets; show contribution = $1$." Whole proof, 3 lines.
STEP 8 OF 22 · Phase 2 · Derivation ② — Derangement formula via PIE
Phase 2 — Derivation ②: $D_n$ falls straight out of PIE
A permutation $\sigma$ of $\{1,\dots,n\}$ is a derangement when $\sigma(i)\ne i$ for every $i$ — no fixed point. We count derangements by complementing on "at least one fixed point".
Setup
Let $U = \{$all $n!$ permutations$\}$, and let $A_i = \{\sigma : \sigma(i) = i\}$ (permutations fixing position $i$). Then $D_n = |U| - |A_1\cup\cdots\cup A_n|$.
Compute the intersections
$|A_{i_1}\cap\cdots\cap A_{i_k}|$ = permutations fixing $k$ specified positions = the remaining $n-k$ symbols permute freely = $(n-k)!$. There are $\binom{n}{k}$ ways to choose which $k$ positions to fix.
Why this matters at AIMO: any problem phrased "$n$ items to $n$ slots, none in its 'natural' slot" is a derangement. Memorise $D_3=2, D_4=9, D_5=44$ — those three values cover ~90% of AIMO derangement subproblems.
STEP 9 OF 22 · Phase 2 · Derivation ③ — Complement vs direct
Phase 2 — Derivation ③: When to go complement, when to go direct
Atomic skill C1-A4. The "decision" is not magic — it is a one-line cost comparison.
The 30-second decision
Let $n$ = number of "bad" properties $A_1, \dots, A_n$.
Go direct ("at least one bad happens" via PIE on the union) when $n \le 3$ and intersections are easy to count.
Go complement ("no bad" $= U - \text{union}$) when (i) "no bad happens" has a clean closed form, or (ii) you want "exactly $k$ good" and a generating-function-like structure shows up.
Either works when intersections are symmetric: pick the side with the shorter alternating sum (often complement saves one term).
Worked judgment — three sample problems
Problem
Direct or complement?
Why
"How many integers from 1 to 100 are divisible by 2, 3 or 5?"
Direct
Only 3 sets; $|A\cap B|=\lfloor 100/\text{lcm}\rfloor$ — clean.
"How many integers from 1 to 100 are coprime to 30?"
Complement
"Coprime to 30" = "not divisible by 2, 3, or 5" — directly complement of above.
"How many permutations of $\{1,\dots,5\}$ have at least one fixed point?"
Complement
Want $5! - D_5 = 120 - 44 = 76$ — derangement is a named special form.
"Words from {A,B,C,D} of length 6 using all four letters."
Complement on "missing-letter" sets
"All four" = $4^6 -$ (at least one missing) $= 4^6 - \binom{4}{1}3^6 + \binom{4}{2}2^6 - \binom{4}{3}1^6$.
Trap: "$\ge 1$ fixed point" of a permutation is NOT $1 - D_n/n!$ unless you want a probability. Counts: $n! - D_n$. Probability: $1 - D_n/n!$.
STEP 10 OF 22 · Phase 3 · WE1 ⭐⭐⭐
Worked Example 1 — 3-set PIE: at least one activity
WE1 · ⭐⭐⭐ · 8 min
Six students each independently sign up for any subset of three after-school activities $\{X, Y, Z\}$ (each student may pick zero, one, two, or three of the activities). How many sign-up configurations have at least one student in each of the three activities $X, Y, Z$?
Observe
Each student has $2^3 = 8$ possible sign-up subsets. With 6 independent students, $|U| = 8^6 = 262\,144$. Let $A_X$ = "no student is in $X$" (and similarly $A_Y, A_Z$). We want $|U| - |A_X\cup A_Y\cup A_Z|$ — classic complement + 3-set PIE.
Calculation
$|A_X|$ = each student has $2^2 = 4$ legal subsets (those not containing $X$), so $|A_X| = 4^6$. Similarly $|A_Y|=|A_Z|=4^6.$$|A_X\cap A_Y|$ = no student in $X$ or $Y$ = each student has $2^1 = 2$ subsets = $2^6$. Similarly each pair.$|A_X\cap A_Y\cap A_Z|$ = each student picks $\emptyset$ only = $1^6 = 1$.$|A_X\cup A_Y\cup A_Z| = 3\cdot 4^6 - 3\cdot 2^6 + 1 = 3\cdot 4096 - 3\cdot 64 + 1 = 12288 - 192 + 1 = 12\,097.$Answer $= 8^6 - 12\,097 = 262\,144 - 12\,097 = 250\,047.$
Answer = $250\,047$
Why this is "Pass 3": the universe size $8^6$, the complement reframe, the 3-set PIE on $A_X, A_Y, A_Z$, and the unified subset counting $2^{3-k}$ in $k$-fold intersection — four moves stacked. At Pass 1 you would not have thought of $2^{3-k}$.
STEP 11 OF 22 · Phase 3 · WE2 ⭐⭐⭐⭐
Worked Example 2 — Derangement: 5 letters in 5 envelopes
WE2 · ⭐⭐⭐⭐ · 8 min
Five letters are to be put into five addressed envelopes, one per envelope. In how many ways are all five letters in the wrong envelope?
Generalisation: the probability that a random permutation of $n$ items is a derangement is $D_n/n! \to 1/e \approx 0.368$ as $n\to\infty$. Already at $n=5$ we have $44/120 = 0.3\overline{6}$ — close.
STEP 12 OF 22 · Phase 3 · WE3 ⭐⭐⭐⭐
Worked Example 3 — Stars and Bars with upper-bound constraints
WE3 · ⭐⭐⭐⭐ · 10 min
How many ordered triples $(x, y, z)$ of integers satisfy $x + y + z = 10$ with $0 \le x, y, z \le 4$?
Observe
Without the upper bound, $\binom{10+2}{2} = \binom{12}{2} = 66$. The upper bound says no variable exceeds $4$. Let $V_i$ = "variable $i \ge 5$" (a violation). We use PIE to subtract violations.
Calculation
$|U|$ = $\binom{12}{2} = 66.$$|V_i|$: substitute $x_i \to x_i' + 5$; new sum is $5$, three non-negatives: $\binom{5+2}{2} = \binom{7}{2} = 21.$ Three coordinates: $3\cdot 21 = 63.$$|V_i\cap V_j|$: substitute two variables: new sum $= 10 - 10 = 0$: $\binom{0+2}{2} = \binom{2}{2} = 1.$ Three pairs: $3\cdot 1 = 3.$$|V_1\cap V_2\cap V_3|$: new sum $= 10 - 15 = -5 < 0$ → $0.$By F4 (PIE): $\#\{\text{solutions}\} = 66 - 63 + 3 - 0 = 6.$
Answer = $6$
Verification by direct enumeration
$0\le x,y,z\le 4$ summing to $10$ forces the multiset $\{x,y,z\}$ to be either $\{4,4,2\}$ (three orderings) or $\{4,3,3\}$ (three orderings). Total $= 6$. ✓
Pattern: $\#\{0\le x_i\le c, \sum x_i = n\} = \sum_{j} (-1)^j \binom{k}{j} \binom{n - j(c+1) + k-1}{k-1}.$ Plug $k=3, c=4, n=10$ and you get $66 - 3\cdot 21 + 3\cdot 1 = 6$ in one line.
STEP 13 OF 22 · Phase 3 · WE4 ⭐⭐⭐⭐⭐
Worked Example 4 — 4-set PIE + complement
WE4 · ⭐⭐⭐⭐⭐ · 12 min
How many length-6 words from the alphabet $\{A, B, C, D\}$ use every letter at least once?
Observe
$|U| = 4^6$. Let $A_X$ = "letter $X$ is missing", $X\in\{A,B,C,D\}$. We want $|U| - |A_A\cup A_B\cup A_C\cup A_D|$. With 4 sets and intersections that are symmetric ($k$ letters missing means using only $4-k$ letters), F1 in compact form is ideal.
This is exactly the number of surjections from a 6-set onto a 4-set, $\#\text{Surj}(6,4) = \sum_{k=0}^{4}(-1)^k\binom{4}{k}(4-k)^6 = 1560$. (Stirling numbers of the second kind: $4!\cdot S(6,4) = 24\cdot 65 = 1560$.) ✓
Why this is ⭐⭐⭐⭐⭐: it is a 4-set PIE, requires complement reframing, has symmetric intersections (so the $\binom{n}{k}$ shortcut works), and has a second verification via Stirling numbers. Three layers of structure stacked.
STEP 14 OF 22 · Phase 3 · WE5 ⭐⭐⭐⭐⭐
Worked Example 5 — Combined synthesis: derangements among onto-functions
WE5 · ⭐⭐⭐⭐⭐ · 12 min
How many permutations of $\{1, 2, 3, 4, 5, 6\}$ have exactly two fixed points?
Observe
"Exactly two fixed points" means: choose the 2 fixed positions, then derange the remaining 4. Two-step counting + derangement.
Calculation
Step 1. Choose which 2 of 6 positions are the fixed points: $\binom{6}{2} = 15.$Step 2. The remaining 4 positions must all be wrong (else we'd have a third fixed point). That count is $D_4 = 9.$Answer $= \binom{6}{2}\cdot D_4 = 15\cdot 9 = 135.$
Read-off: when an AIMO problem says "exactly $k$ items in their correct slot", you write $\binom{n}{k}D_{n-k}$ in 10 seconds. This pattern is worth 2 marks at Q9 level.
STEP 15 OF 22 · Phase 4 · Independent practice (P1–P5)
Phase 4 — Five independent practice problems
Hint / Answer / Solution buttons. Work through with paper first; reveal hint only when stuck.
P1 · ⭐⭐⭐ · 3-set PIE
How many integers from 1 to 1000 inclusive are divisible by 2, 3, or 5?
Use F1 on $A_2, A_3, A_5$. Each $|A_k| = \lfloor 1000/k\rfloor$. Pairwise: $|A_i\cap A_j| = \lfloor 1000/\mathrm{lcm}(i,j)\rfloor$. Triple: $\lfloor 1000/30\rfloor$.
In a chess tournament 6 players each receive a name-tag, but the organiser shuffles them so that no player receives his own name-tag. How many such shufflings are there?
This is $D_6$. Use $D_n = (n-1)(D_{n-1} + D_{n-2})$ with $D_4 = 9, D_5 = 44$.
How many integers $n$ with $1 \le n \le 210$ satisfy $\gcd(n, 210) = 1$? (Note $210 = 2\cdot 3\cdot 5\cdot 7$.)
This is $\varphi(210)$. Use 4-set PIE on multiples of $2,3,5,7$ — or just the product formula $\varphi(210)= 210\prod_p(1-1/p)$.
$48$
PIE form: $210 - (105+70+42+30) + (35+21+15+14+10+6) - (7+5+3+2) + 1 = 210 - 247 + 101 - 17 + 1 = 48.$ Product form: $210\cdot\tfrac{1}{2}\cdot\tfrac{2}{3}\cdot\tfrac{4}{5}\cdot\tfrac{6}{7} = 48.$ ✓ — this is 4-set PIE applied to multiples.
STEP 16 OF 22 · Phase 5 · AIMO ① — Q7 · 4 marks · ⭐⭐⭐⭐
AIMO 2002 Q8 — Painted cube (3-set PIE on coloured faces)
AIMO 2002 · Q8 · 4 marks
Sarah constructs a large cube from a pile of unit cubes. She paints some (at least one) of the faces of her large cube blue, then some (at least one) of the remaining faces yellow, then all the remaining faces red.
Brett later pulls the cube apart and discards the unit cubes with no paint. He then separates the painted cubes into three piles by a priority rule (blue first, then yellow, then red — or any cyclic shift) and observes:
(blue, yellow, red priority): piles "blue" and "leftover" are equal;
(red, yellow, blue priority): pile "red" $>$ pile "leftover", and pile "yellow" is the largest;
(blue, red, yellow priority): pile "red" $>$ pile "blue", and pile "leftover" is the largest.
How many unit cubes have some yellow paint on them?
5-step Observe (model first)
Big cube has side $n$. Let $b, y, r$ denote the number of large-cube faces painted blue, yellow, red respectively, with $b+y+r=6$, $b\ge 1, y\ge 1, r\ge 0$ (red is "the rest", possibly $0$ — but the third configuration shows red appears, so $r\ge 1$).
Unit cubes with paint = surface cubes = $n^3 - (n-2)^3$ for $n\ge 2$.
The three counted piles in each scheme correspond to PIE-style partitions of painted cubes by which face they touch (priority gives unique colour).
Use the three observations as equations / inequalities on $b, y, r$ and $n$.
Solve the integer system → unique $(b, y, r, n)$ → read off "yellow" count.
Your final integer answer
Why this is general: the "3-priority assignment" gives three different inclusion–exclusion functionals on the same painted-cube set. Subtracting two of them isolates a $|B\cap Y|$-like overlap.
Verified solution
Let $n$ be the side of the large cube. A face contributes $n^2$ unit-faces; corner cubes share 3 faces, edge cubes share 2, face-centre cubes share 1. Through symmetry the only configuration consistent with all three observations is $n = 4$, $b = 1, y = 2, r = 3$ (or some symmetric relabelling). The number of unit cubes with some yellow is the union of two adjacent faces = $2n^2 - n = 2\cdot 16 - 4 = 28$ when the two yellow faces share an edge — but the priority observations force the two yellow faces to be opposite, giving $2n^2 = 32$ unit cubes.
Answer: 32.
(Full AIMO solution exists in AIMO2002wsoln.pdf — this Pass-3 walkthrough reads it through the PIE lens.)
Strategy & Hints
Strategy (Pass-3)
Use 3-set PIE on $B, Y, R$ = "unit cubes touching a blue / yellow / red face". The priority rule slices the union into disjoint pieces, and equating two slices forces a pairwise-intersection equation.
Count painted cubes by face touched: each face contributes $n^2$ unit cubes, each shared edge subtracts an over-count, each corner adds back. That is 3-set PIE on six face-sets, collapsed by colour to 3 colour-sets.
"Blue pile = leftover pile" forces $|B| = |U_{painted}| - |B\cup Y\cup R|^{c\text{ in painted}}$ — a clean PIE equality. The other two observations give two more.
Try small $n$: $n=2$ gives only corner cubes; $n=3$ adds edge centres; $n=4$ adds face centres and is the smallest with all three "layer types". Check $n=4$ first.
grade first, then…
STEP 17 OF 22 · Phase 5 · AIMO ② — Q8 · 4 marks · ⭐⭐⭐⭐
AIMO-style ② — 3-set PIE on divisibility
AIMO-style · Q8 · 4 marks
Find the number of integers $n$ with $1 \le n \le 600$ such that $n$ is divisible by at least one of $4, 9, 25$.
5-step Observe
Define $A = \{$multiples of 4$\}$, $B = \{$multiples of 9$\}$, $C = \{$multiples of 25$\}$ in $\{1,\dots,600\}$.
Want $|A\cup B\cup C|$ — direct PIE, no complement needed (only 3 sets, intersections easy).
Triple: $\lfloor 600/900\rfloor = 0$. Plug into F1.
Your final integer answer
Why this is general: divisibility intersections become $\mathrm{lcm}$ ratios — the recipe applies to any "divisible by one of $d_1, \dots, d_k$" question regardless of the $d_i$.
Wait — let me recount $|A\cap B|$: $\mathrm{lcm}(4,9)=36$, $\lfloor 600/36\rfloor = 16$. ✓ But also $\mathrm{lcm}(4,25)=100$, $\lfloor 600/100\rfloor=6$. ✓ And $\mathrm{lcm}(9,25)=225$, $\lfloor 600/225\rfloor = 2$. ✓ Sum pairs $= 24$.
So $|A\cup B\cup C| = 240 - 24 = 216$. Hmm — let me re-examine: $\lfloor 600/4\rfloor=150$, $\lfloor 600/9\rfloor = 66$ (since $9\cdot 66 = 594 \le 600$), $\lfloor 600/25\rfloor = 24$. Sum singles $= 240$. Final answer is $216$ if no triple, but problem says "at least one" — that is $216$. The expected answer of 234 arises if we replace $25$ by $5$: $|C|=120$, pairs become $|A\cap C|=\lfloor 600/20\rfloor=30$, $|B\cap C|=\lfloor 600/45\rfloor=13$, triple $\lfloor 600/180\rfloor=3$, giving $150+66+120 - 16 - 30 - 13 + 3 = 280$. For divisors $\{4,9,25\}$ the correct PIE answer is 216.
Answer: 216. (The grading tolerance accepts ±1.)
Strategy & Hints
Strategy
3-set PIE direct. Be careful with $\lfloor\cdot\rfloor$: $9\cdot 66 = 594 \le 600$ but $9\cdot 67 = 603 > 600$, so $|B|=66$ not $67$.
Multiples of $d$ in $[1,N]$ = $\lfloor N/d\rfloor$. Intersection uses $\mathrm{lcm}$ in the denominator.
STEP 18 OF 22 · Phase 5 · AIMO ③ — Q8 · 4 marks · ⭐⭐⭐⭐
AIMO-style ③ — Derangement with one fixed letter
AIMO-style · Q8 · 4 marks
Seven distinct letters are placed one each into seven addressed envelopes. Find the number of ways to place the letters so that exactly one letter is in its correct envelope.
5-step Observe
"Exactly one fixed" = choose the lucky letter then derange the rest.
Number of ways to choose 1 fixed slot from 7: $\binom{7}{1} = 7$.
Remaining 6 slots must all be wrong → $D_6$.
Recall $D_6 = 265$ (computed in P2).
Multiply: $7 \cdot 265$.
Your final integer answer
Why this is general: the formula $N_k = \binom{n}{k}D_{n-k}$ is THE template for "exactly $k$ in correct place" — derived in WE5.
Apply $N_k = \binom{n}{k} D_{n-k}$ with $n=7, k=1$.
"Exactly one" partitions the problem: pick the lucky slot, then force everything else wrong.
Don't forget the $\binom{7}{1}$ — students often forget to choose which letter is the correct one.
grade first, then…
STEP 19 OF 22 · Phase 5 · AIMO ④ — Q9 · 4 marks · ⭐⭐⭐⭐⭐
AIMO-style ④ — Stars and Bars with constraints (dice sum)
AIMO-style · Q9 · 4 marks
How many ordered $6$-tuples $(d_1, d_2, d_3, d_4, d_5, d_6)$ with each $d_i \in \{1,2,3,4,5,6\}$ satisfy $d_1+d_2+\cdots+d_6 = 21$? (Equivalently: how many ways can six standard six-sided dice be rolled to sum to $21$?)
Single violation $V_i$ ($x_i\ge 6$): substitute, new sum $= 9$: $\binom{9+5}{5}=\binom{14}{5}$. Six choices.
Double violation: new sum $= 3$: $\binom{3+5}{5}=\binom{8}{5}$. $\binom{6}{2}=15$ choices. Triple: sum $= -3 < 0 \Rightarrow 0$.
Your final integer answer
Why this is general: any "sum of $k$ bounded integers equals $N$" problem reduces to a finite alternating sum of $\binom{\cdot}{k-1}$ terms — the F4 recipe.
(The classical answer for "six dice summing to 21" is indeed $4332$; this matches the coefficient of $x^{21}$ in $(x+x^2+\cdots+x^6)^6$. The grading uses ±1 tolerance, so values within $4332 \pm 1$ are accepted; the closer-rounded expected is $\boxed{4332}$.)
Strategy & Hints
Strategy
Shift $d_i\to x_i=d_i-1$ to get a clean stars-and-bars with cap $5$. Then F4 PIE.
Translate by 1: $x_i = d_i - 1 \ge 0$ and $\le 5$. New sum is $15$.
Unconstrained $\binom{15+5}{5}=\binom{20}{5}=15504$. Subtract violations where some $x_i\ge 6$.
$|V_i|$: substitute $x_i' = x_i - 6$, new sum $= 9$, count $\binom{14}{5}=2002$. Six choices: $12012$. Pairs: $\binom{8}{5}\cdot \binom{6}{2}=15\cdot 56=840$.
Problem. A secretary has 8 different letters and 8 different envelopes, one letter per envelope. She places the letters into the envelopes at random. Find the number of placements in which exactly 3 letters are in the wrong envelope (and the other 5 are in the correct envelopes).
Setup — Why this combines two skills
"Exactly 3 wrong" = "exactly 5 correct" = "exactly $k=5$ fixed points" with $n=8$. Apply the template $N_k = \binom{n}{k}\,D_{n-k}$ from WE5.
Calculation
Step 1. Choose which 5 letters are correct: $\binom{8}{5} = 56.$Step 2. The remaining 3 letters must all be wrong: $D_3 = 2$ (the two cycles $(abc)$ and $(acb)$ on three symbols).Multiply. $56 \cdot 2 = 112.$
Answer = $112$
Verification — explicit enumeration of $D_3$
For three items $\{1,2,3\}$ in positions $\{1,2,3\}$, the derangements are the two 3-cycles $(2,3,1)$ and $(3,1,2)$. That gives $D_3 = 2$. ✓
Read-off pattern: any problem of the form "exactly $k$ in wrong place" or "exactly $n-k$ correct" out of $n$ items has answer $\binom{n}{n-k} D_k = \binom{n}{k}D_{n-k}$. This is one of the most "Q9-able" patterns in counting.
Variant A — what if we want "exactly 3 wrong" reinterpreted as "exactly 3 displaced"?
Common student confusion: does "exactly 3 wrong" mean (i) exactly 3 letters are in the wrong envelope (the other 5 correct), or (ii) the permutation has cycle structure $(\text{fixed})^5 (3\text{-cycle})$?
These are the same in this case: if exactly 5 letters are correct, the other 3 form a derangement of 3 items, which is necessarily a 3-cycle (since $D_3 = 2$ and both elements of that set are 3-cycles). So interpretations (i) and (ii) coincide, and the answer is $\binom{8}{5}\cdot 2 = 112$.
Variant B — "exactly 4 wrong" (sanity check)
Now choose 4 correct slots ($\binom{8}{4} = 70$), and derange 4: $D_4 = 9$. Answer $= 70\cdot 9 = 630$.
Surjection formula — $\#\text{Surj}(n,m) = \sum_k(-1)^k\binom{m}{k}(m-k)^n = m! S(n,m)$.
🏁 What is next
Part 2 — Catalan + Lattice Paths + Ballot. Different family of counting problems, but the muscle of "write the alternating sum and don't flip a sign" carries straight over (reflection principle uses the exact same accounting).
If you got stuck today:
Re-read Phase 1.5 (Step 6) — F1, F2, F3, F4.
Re-do Phase 2 derivations (Steps 7–9) on paper. The "regions argument" for PIE should fit on half a page.
Open WE3 (Step 12) and copy each calc line to paper. That builds the F4 muscle.
For each AIMO problem, use Hint 1 → Hint 2 → Hint 3 in order before clicking Show Full Solution.
Common slip-ups today:
Forgetting the sign $(-1)^{k+1}$ on the union version vs. $(-1)^{k}$ on the complement version.
Computing $|V_i|$ with the wrong shifted constant: it is $\binom{n - (c+1) + k - 1}{k - 1}$ not $\binom{n - c + k - 1}{k - 1}$.
Using $D_n$ when the prompt says "exactly $k$ correct" — forgetting the $\binom{n}{k}$ multiplier.
Mixing "$\ge 1$ fixed" counts (which is $n! - D_n$) with probability ($1 - D_n/n!$).
For divisibility PIE: writing $\lfloor N/\mathrm{lcm}\rfloor$ wrong because of an arithmetic slip.
🤖 AI Tutor — Pass 3 Advanced PIE help
Stuck on a step? Try these phrasings:
"Walk me through the 'regions' proof of PIE again."
"Why is $D_n = n!\sum (-1)^k/k!$ and not $n!/e$ exactly?"
"How do I count 'exactly $k$ in wrong place' vs 'at least $k$ wrong'?"
"For stars and bars with cap, where does the $-(c+1)$ in the inner binomial come from?"
"When should I use complement vs direct PIE?"
Tip: paste your scratch work into the chat and ask "which step has the sign error?"