AMC 10 · 2017 · #22

Grade 11 probability
probability-basicpermutations-basiccombinations-basic caseworksystematic-enumeration ↑ Prerequisites: probability-basicpermutations-basic
📏 Medium solution 💡 4 insights
Problem
Four players each start with 4 coins. In each of four rounds, one player is chosen at random to hand a single coin to a different randomly chosen player, with every ordered giver-receiver pair equally likely. Find the probability that after the fourth round every player again holds exactly 4 coins.

Pick an answer.

(A)
$\dfrac{7}{576}$
(B)
$\dfrac{5}{192}$
(C)
$\dfrac{1}{36}$
(D)
$\dfrac{5}{144}$
(E)
$\dfrac{7}{48}$
How to solve
Strategy Organize Information in More Ways

Chasing four coin piles through four rounds buries the problem in bookkeeping. Tool #15 (Organize Information in More Ways) re-records each round as a single arrow from giver to receiver, so the entire game becomes one picture of four arrows on four labeled dots, and the goal turns into a clean structural statement: every dot must send as many arrows as it receives. Tool #1 (Draw a Diagram) is what makes that reframing visible on paper. Tool #7 (Identify Subproblems) then splits the count into two independent halves — which four arrows appear, and in which order the four rounds produce them. Tool #2 (Make a Systematic List) finishes it by listing the only arrow patterns that can balance, with no overlaps and nothing missed.

1STEP 1

Turn each round into one arrow

One round is one arrow.

4 × 3 = 12 ⟹ 12⁴ = 20736 equally likely sequences
2STEP 2

Everyone even means out equals in

Back to even means each player receives as often as they give.

4 - out + in = 4 ⇔ out = in at every player
3STEP 3

Balanced arrows break into loops

Balanced arrows break into loops.

4 = 2 + 2 or 4 = 4 (4 = 3 + 1 impossible)
4STEP 4

Count the two-loop patterns

The two-loop shapes include using one pair twice.

C(4, 2) · 4!/2! 2! = 6 · 6 = 36 C(6, 2) · 4! = 15 · 24 = 360
5STEP 5

Count the four-loop patterns

The single loop through all four is counted separately.

3 · 2 · 4! = 6 · 24 = 144
6STEP 6

Add the cases and divide

Adding and dividing gives five one-hundred-ninety-seconds.

(36 + 360 + 144)/12⁴ = 540/20736 = 5/192 ⟹ (B)
Answer
5/192
A ceiling argument prices the answer without any counting. After three rounds three coins have moved, so the piles cannot already be level; and since one more transfer changes exactly two players by ± 1, the only way round four can level them is if after round three exactly one player sits at 5, one sits at 3, and two sit at 4. Round four must then be the one specific arrow from the 5 to the 3, which has probability 1/12. So the answer is 1/12 times some probability and can never exceed 1/12 — that alone rules out (E) 7/48, which would demand a probability of 7/4. Reading the same identity forward, 5/192 = 1/12 × 5/16, so the claim is that three rounds leave exactly one player up and one player down with probability 5/16 — a believable value, since the alternatives are the noticeably rarer spread-out states. A last guard on the arithmetic: the probability must be a whole number of outcomes over 20736, and 5/192 = 540/20736 checks out.
💡Key takeaway

Draw every payment as an arrow: everyone lands back where they started exactly when the arrows close up into loops, and then all that is left to do is count the loops.

  • Turn each round into one arrow
  • Everyone even means out equals in
  • Balanced arrows break into loops
  • Count the two-loop patterns
  • Count the four-loop patterns
  • Add the cases and divide