2021 AMC 10B Problem 22

P21-25~8 minPrint

Inclusion-Exclusion Arrangements with Restrictions Basic Probability Map the objects to something easier to count Exploit symmetry to reduce work or pair up objects

Ang, Ben, and Jasmin each have $5$ blocks, colored red, blue, yellow, white, and green; and there are $5$ 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 $3$ blocks all of the same color is $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. What is $m + n ?$

Show solution without answering

Key insight

Ang's order can be taken as fixed. A box is all one color when Ben and Jasmin both match Ang there. Count with add, subtract, add: 2556 of 14400.

Solution

Step 1: fix Ang's arrangement.

Each person puts their $5$ colors into the $5$ boxes in some order. There are $5 \times 4 \times 3 \times 2 \times 1 = 120$ orders.
Whatever Ang does, we can name the boxes by the color Ang put in them: the "red box," the "blue box," and so on. So think of Ang as always putting red in the red box, blue in the blue box, etc.
A box gets three blocks of one color exactly when Ben and Jasmin both put that box's color in it. Call such a box a match.
Ben and Jasmin together have $120 \times 120 = 14400$ equally likely pairs of orders. We count the pairs with at least one match.

Step 2: count pairs where chosen boxes match.

Pick one box, say the red box. Ben must put red there, and his other $4$ colors can go anywhere: $4! = 24$ ways. The same for Jasmin, so $24 \times 24 = 576$ pairs make the red box a match.
In the same way, if we pick $k$ particular boxes that must all match, each person has $(5 - k)!$ ways to place the rest, so there are $\big((5-k)!\big)^2$ pairs.

boxes that must match, $k$	ways to pick them	pairs for each pick
$1$	$5$	$24^2 = 576$
$2$	$10$	$6^2 = 36$
$3$	$10$	$2^2 = 4$
$4$	$5$	$1^2 = 1$
$5$	$1$	$1^2 = 1$

Step 3: add and subtract to fix double counting.

7. Adding $5 \times 576$ counts a pair with two matches twice, a pair with three matches three times, and so on. The standard fix (inclusion–exclusion) is to subtract the "two boxes" count, add back the "three boxes" count, and keep alternating:
$5 \cdot 576 - 10 \cdot 36 + 10 \cdot 4 - 5 \cdot 1 + 1 \cdot 1 = 2880 - 360 + 40 - 5 + 1 = 2556.$
8. After this, every pair with at least one match is counted exactly once.

Step 4: simplify.

The probability is $\frac{2556}{14400}$ . Both numbers divide by $36$ : $\frac{71}{400}$ . Since $71$ is prime and does not divide $400$ , this is in lowest terms.
So $m + n = 71 + 400 = 471$ .

The answer is $\boxed{\textbf{(D)}\ 471}$ .

Why this works

Because everyone arranges at random, one person's arrangement can be treated as fixed without changing any chances. The events "this box matches" overlap, so simply adding their counts overcounts. Adding, then subtracting the overlaps, then adding back the triple overlaps, and so on, corrects this. A quick check: adding five chances of $\frac{1}{25}$ gives $0.2$ , an overcount, and the true answer $\frac{71}{400} = 0.1775$ is a little smaller.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Each person's placement is a permutation of the five colors. Relabel the colors by Ang's placement, so Ang puts color $i$ in box $i$ . Ben's and Jasmin's placements are then independent uniformly random permutations $\sigma$ and $\tau$ , and box $i$ is monochromatic exactly when $\sigma(i) = i$ and $\tau(i) = i$ : box $i$ is a common fixed point.

Count ordered pairs $(\sigma, \tau)$ out of $120^2 = 14400$ that share at least one fixed point. For a chosen set of $k$ boxes, the number of pairs in which both permutations fix all $k$ of them is $\big((5-k)!\big)^2$ . Inclusion–exclusion over $k = 1, \dots, 5$ :
$\binom51 (4!)^2 - \binom52 (3!)^2 + \binom53 (2!)^2 - \binom54 (1!)^2 + \binom55 (0!)^2$
$= 5 \cdot 576 - 10 \cdot 36 + 10 \cdot 4 - 5 \cdot 1 + 1 = 2880 - 360 + 40 - 5 + 1 = 2556.$

The probability is $\frac{2556}{14400}$ . Dividing by $36$ : $\frac{71}{400}$ , and $71$ is prime, so this is lowest terms.

$m + n = 71 + 400 = 471$ . The answer is $\boxed{\textbf{(D)}\ 471}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic (§1.3)
Introduction to Counting & Probability, Chapter 7: Introduction to Probability
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.5)
Introduction to Algebra, Chapter 22: Special Manipulations (§22.3)