Ang, Ben, and Jasmin each have blocks, colored red, blue, yellow, white, and green; and there are empty boxes. Each of the people randomly and independently of the other two people places one of their blocks into each box. The probability that at least one box receives blocks all of the same color is , where and are relatively prime positive integers. What is
- A)
- B)
- C)
- D)
- E)
Answer
D
Key insight
Fix Ang's placement; box i is monochromatic iff Ben's and Jasmin's permutations both fix i, so count pairs with a common fixed point by inclusion–exclusion.
Solution
Each person's placement is a permutation of the five colors. Relabel the colors by Ang's placement, so Ang puts color in box . Ben's and Jasmin's placements are then independent uniformly random permutations and , and box is monochromatic exactly when and : box is a common fixed point.
Count ordered pairs out of that share at least one fixed point. For a chosen set of boxes, the number of pairs in which both permutations fix all of them is . Inclusion–exclusion over :
The probability is . Dividing by : , and is prime, so this is lowest terms.
. The answer is .
Why this works
Symmetry lets you fix one player's arrangement for free, turning "three blocks match" into "two permutations agree with the identity at some position." Events like "box matches" overlap heavily, so inclusion–exclusion is the natural tool, and fixing specified points of a permutation leaves freedom. Sanity check: the union bound gives at most , and sits just below it.
The trap
Adding the five box probabilities (5 · 1/25) without subtracting overlaps, or dropping the alternating signs in inclusion–exclusion.
Common mistakes
- Adding the five box probabilities (5 · 1/25) without subtracting overlaps, or dropping the alternating signs in inclusion–exclusion.
- Using instead of , forgetting that both Ben and Jasmin must fix the chosen boxes.
Techniques
Map the objects to something easier to count · Exploit symmetry to reduce work or pair up objects