AMC 10 · 2021 · #23

Grade 12 probabilitycounting

Archetype Arithmetic Expression Decomposition └ Sub-archetype Weighted Group Aggregation

expected-valuecombinations-basicprobability-basicpair-counting identify-subproblemseasier-related-problem ↑ Prerequisites: expected-valuecombinations-basic

📏 Medium solution 💡 3 insights

Problem

Pick five different numbers from 1 to 30, with every such choice equally likely. Inside the picked set, count how many times two of the picked numbers are next-door neighbours. Find the average of that count over all possible picks.

Pick an answer.

(A)

$\frac{2}{3}$

(B)

$\frac{29}{36}$

(C)

$\frac{5}{6}$

(D)

$\frac{29}{30}$

(E)

How to solve

Strategy Identify Subproblems

Sorting all 142506 subsets by how many consecutive pairs they contain is a nightmare of cases. So I stop looking at subsets and look at the 29 neighbor slots 1-2, 2-3, ..., 29-30 instead. Each slot contributes either 0 or 1 to a subset's count, so the total count is a sum of 29 tiny counts, and an average of a sum is the sum of the averages. That turns one huge case analysis into 29 copies of a single easy question: what fraction of subsets grab both halves of one fixed neighbor slot? Answer that one question, multiply by 29, done.

1STEP 1

Name the thing being averaged

Name the thing being averaged.

X = number of consecutive pairs, answer = (sum of X over all subsets)/(C(30, 5))

2STEP 2

Split X into 29 yes-or-no counts

Split it into twenty-nine yes-or-no counts.

X = Σ_i=1²⁹ X_i ⟹ average of X = Σ_i=1²⁹ (average of X_i)

3STEP 3

Average of one slot is its probability

One slot's average is its probability.

average of X_i = (C(28, 3))/(C(30, 5)) = 3276/142506 = (C(5, 2))/(C(30, 2)) = 10/435 = 2/87

4STEP 4

Add the 29 equal averages

Adding twenty-nine equal averages gives two thirds.

answer = 29 · 2/87 = 58/87 = 2/3

Answer

2/3

A value below 1 is what the situation demands: 5 numbers spread over a range of 30 are usually far apart, so most subsets contain no consecutive pair at all and only a minority contain one. An average of 2/3 says roughly two subsets in three carry a single pair's worth. The general formula behind the work is (n-1) · (C(k, 2))/(C(n, 2)) for choosing k numbers from 1 to n, and it survives a case small enough to check by hand: choosing 3 numbers from 1 to 6 predicts 5 · 3/15 = 1, and listing all 20 such subsets does give 20 consecutive pairs in total, an average of exactly 1. The formula also behaves sensibly at the edges, since k = n forces all n-1 pairs and the formula returns n-1.

💡Key takeaway

When an average is hard to compute all at once, break the thing you are counting into small yes-or-no pieces, average one piece, and add up the pieces.

Name the thing being averaged
Split X into 29 yes-or-no counts
Average of one slot is its probability
Add the 29 equal averages

Name the thing being averaged

Split X into 29 yes-or-no counts

Average of one slot is its probability

Add the 29 equal averages

More like this