2023 AMC 10B Problem 21

P21-25~6 minPrint

Conditional Probability & States Number Properties Use an invariant, parity, or coloring argument Define states/recurrence and iterate Exploit symmetry to reduce work or pair up objects

Each of $2023$ balls is randomly placed into one of $3$ bins. Which of the following is closest to the probability that each of the bins will contain an odd number of balls?

Show solution without answering

Key insight

Only odd or even matters for each bin. Track one question, 'do all three bins match?', ball by ball. The chance quickly settles at 1/4.

Solution

$2023$ balls is far too many to handle directly, so watch what happens one ball at a time, keeping track only of whether each bin holds an odd or an even number.

1. Each ball flips one bin. When a ball lands in a bin, that bin switches from odd to even or from even to odd. The other two bins stay the same.
2. Two kinds of situations. Call the situation matched if all three bins are odd, or all three are even. Call it unmatched otherwise (two bins agree and one is different).
After $2023$ balls the total is odd, so "all even" is impossible; "matched" then means exactly "all three odd", which is what we want.
3. How one more ball changes things.
- From matched, the ball flips one bin, so the three no longer agree. Matched always becomes unmatched.
- From unmatched, there is one "odd one out" bin. The situation becomes matched only if the ball lands in that bin, a chance of $\frac{1}{3}$ .
4. The rule. Let $p$ be the chance of "matched" after some number of balls. After one more ball, the chance is
$\text{new } p = \frac{1}{3}\,(1 - p),$
because we must be unmatched first (chance $1 - p$ ) and then hit the right bin (chance $\frac{1}{3}$ ).
5. Run it. After $1$ ball, one bin has a ball and two are empty, so $p = 0$ .

balls	$1$	$2$	$3$	$4$	$5$	$6$
$p$	$0$	$\frac{1}{3}$	$\frac{2}{9}$	$\frac{7}{27}$	$\frac{20}{81}$	$\frac{61}{243}$
decimal	$0$	$0.333$	$0.222$	$0.259$	$0.247$	$0.251$

Where it settles. The values bounce above and below $0.25$ and get closer every step. In fact $\frac{1}{4}$ is the value that stays put: $\frac{1}{3}\left(1 - \frac{1}{4}\right) = \frac{1}{3} \cdot \frac{3}{4} = \frac{1}{4}$ . Each step, the distance from $\frac{1}{4}$ shrinks to a third of what it was, so after $2023$ balls the chance is extremely close to $\frac{1}{4}$ .

The answer is $\boxed{\textbf{(E)}\ \frac{1}{4}}$ .

Why this works

Keeping only "odd or even" for each bin shrinks a huge number of outcomes down to two situations, matched and unmatched. A step-by-step rule like "new $p = \frac{1}{3}(1 - p)$ " settles down to the value that the rule leaves unchanged, and here that value is $\frac{1}{4}$ . The words "closest to" hint that you want where the chance settles, not an exact fraction.

Alternative approach

A quick estimate. With so many balls, bin $1$ is odd about half the time and bin $2$ is odd about half the time, and the two hardly affect each other. Once bins $1$ and $2$ are known, bin $3$ is decided, because the total $2023$ is odd: if bins $1$ and $2$ are both odd, their sum is even, so bin $3$ is odd. So the chance is about
$\frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}.$

Concise solution

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

Only the parities of the three bin counts matter, and each ball flips the parity of the bin it lands in. After $k$ balls the three parities sum to the parity of $k$ , so after an odd number of balls the pattern is either "all odd" or "one odd, two even."

Call the pattern same when all three parities agree (all odd after an odd number of balls, all even after an even number) and split otherwise. Adding one ball moves a same pattern to split for sure, and moves a split pattern back to same with probability $\frac{1}{3}$ (the ball must land in the single bin whose parity differs).

Let $p_k$ be the probability of same after $k$ balls. Then
$p_{k+1} = \tfrac{1}{3}(1 - p_k), \qquad p_1 = 0.$
The fixed point is $p = \frac{1}{4}$ , and $p_{k+1} - \frac{1}{4} = -\frac{1}{3}\left(p_k - \frac{1}{4}\right)$ , so the error shrinks by a factor of $3$ every ball: $p_k = \frac{1}{4} - \frac{1}{4}\left(-\frac{1}{3}\right)^{k-1}$ . For $k = 2023$ this is $\frac{1}{4}$ minus something astronomically small.

The answer is $\boxed{\textbf{(E)}\ \frac{1}{4}}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 8: Basic Probability Techniques (§8.5)
Introduction to Number Theory, Chapter 1: Integers: The Basics
Intermediate Counting & Probability, Chapter 10: Recursion
Introduction to Algebra, Chapter 22: Special Manipulations (§22.3)