2021 AMC 10A Problem 16

P16-20~4 minPrint

Statistics & Data Sequences & Series Bound the quantity above/below or estimate to pin it down Set up the equation/formula and compute; no special trick needed

In the following list of numbers, the integer $n$ appears $n$ times in the list for $1 \leq n \leq 200$ . $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, \dots, 200, 200, \dots , 200$ What is the median of the numbers in this list?

Show solution without answering

Key insight

The list has 20100 numbers, so the middle is at position 10050. The numbers 1 through n fill the first n(n+1)/2 spots; find which block holds that position.

Solution

Count the entries: $1 + 2 + \cdots + 200 = \frac{200 \times 201}{2} = 20100$ . That is even, so the median is the average of the $10050$ th and $10051$ st entries. The list is already in order.
Look at how the first few numbers fill positions:

number	positions it fills	last position
$1$	$1$	$1$
$2$	$2$ to $3$	$3$
$3$	$4$ to $6$	$6$
$4$	$7$ to $10$	$10$

The last position filled by $n$ is $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ .
3. We want the first $n$ whose last position reaches $10050$ , so $n(n+1)$ should be about $20100$ . Since $n \times n$ is close to $n(n+1)$ , try $n$ near the square root of $20100$ . We have $141^2 = 19881$ and $142^2 = 20164$ , so check $141$ and $142$ .
4. $\frac{141 \times 142}{2} = 10011$ , so the numbers $1$ to $141$ end at position $10011$ .
5. $\frac{142 \times 143}{2} = 10153$ , so the number $142$ fills positions $10012$ through $10153$ .
6. Both $10050$ and $10051$ are in that stretch, so both middle entries are $142$ . The median is $142$ .

The answer is $\boxed{\textbf{(C)}\ 142}$ .

Why this works

For a list made of blocks of repeated numbers, first find the middle position, then find which block contains it by counting how many positions the earlier blocks use up. Here the running count is a triangular number, $\frac{n(n+1)}{2}$ , and a square root tells you where to look. Always check that both middle positions fall in the same block.

Concise solution

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

The list has $1 + 2 + \dots + 200 = \frac{200 \cdot 201}{2} = 20100$ entries, an even number, so the median is the average of the $10050$ th and $10051$ st entries (the list is already sorted).

The values $1, 2, \dots, n$ together fill the first $\frac{n(n+1)}{2}$ positions. We want the smallest $n$ with $\frac{n(n+1)}{2} \ge 10050$ , i.e. $n(n+1) \ge 20100$ . Since $n^2 \approx 20100$ suggests $n \approx 142$ :
$\frac{141 \cdot 142}{2} = 10011 < 10050,\qquad \frac{142 \cdot 143}{2} = 10153 \ge 10051.$
Positions $10012$ through $10153$ all hold the value $142$ , which includes both middle positions.

The median is $\frac{142 + 142}{2} = 142$ , so the answer is $\boxed{\textbf{(C)}\ 142}$ .

Review in the AoPS books

Prealgebra, Chapter 13: Data and Statistics
Introduction to Algebra, Chapter 21: Sequences & Series (§21.1, §21.2, §21.3, §21.4)
Intermediate Algebra, Chapter 17: More Sequences and Series (§17.1, §17.2)