2014 AMC 10A Problem 24

P21-25~6 minPrint

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

A sequence of natural numbers is constructed by listing the first $4$ , then skipping one, listing the next $5$ , skipping $2$ , listing $6$ , skipping $3$ , and, on the $n$ th iteration, listing $n+3$ and skipping $n$ . The sequence begins $1,2,3,4,6,7,8,9,10,13$ . What is the $500,000^{\text{th}}$ number in the sequence?

Show solution without answering

Key insight

The 500,000th listed number is 500,000 plus how many numbers were skipped before it. Up to that point, 1 + 2 + ... + 996 = 496,506 numbers were skipped.

Solution

Every whole number is either listed or skipped. So the $500{,}000$ th listed number equals $500{,}000$ plus the number of skipped numbers that come before it. The job is to count those skipped numbers.

1. What one round does. Round $n$ lists $n + 3$ numbers, then skips $n$ .
2. Count the listed numbers after some rounds. After $n$ rounds, the number of listed numbers is
$(1 + 3) + (2 + 3) + \cdots + (n + 3) = (1 + 2 + \cdots + n) + 3n = \frac{n(n+1)}{2} + 3n.$
Check with the start: after $1$ round, $4$ listed; after $2$ rounds, $4 + 5 = 9$ listed. The formula gives $1 + 3 = 4$ and $3 + 6 = 9$ .
3. Find the right round. We want this count to be close to $500{,}000$ . It is roughly $\frac{n^2}{2}$ , so $n^2 \approx 1{,}000{,}000$ and $n$ is a bit under $1000$ . Try $n = 996$ :
$\frac{996 \cdot 997}{2} + 3 \cdot 996 = 496{,}506 + 2{,}988 = 499{,}494.$
That is $506$ short of $500{,}000$ . Round $997$ lists $997 + 3 = 1000$ numbers, which is more than $506$ . So the $500{,}000$ th number is listed during round $997$ , before its skip.
4. Count the skipped numbers before it. The first $996$ rounds skipped $1 + 2 + \cdots + 996 = \frac{996 \cdot 997}{2} = 496{,}506$ numbers. Round $997$ has not skipped anything yet.
5. The answer. $500{,}000 + 496{,}506 = 996{,}506$ .

Check with the given start: the $10$ th listed number should be $13$ . Before it, rounds $1$ and $2$ skipped $1 + 2 = 3$ numbers, and $10 + 3 = 13$ .

The answer is $\boxed{\textbf{(A)}\ 996,506}$ .

Why this works

For a list that skips some numbers, "the $k$ th number on the list" equals $k$ plus the number of skipped numbers before it. That turns the question into counting skips, which here is just $1 + 2 + \cdots + n$ . The answer choices differ by $1$ , so checking the method on the start of the list, as we did with the $10$ th number, is worth the few seconds.

Alternative approach

Track where each round starts. Round $n$ uses $2n + 3$ numbers ( $n + 3$ listed and $n$ skipped). So after $n$ rounds we have gone through $5 + 7 + \cdots + (2n + 3) = n(n + 4)$ numbers. After $996$ rounds that is $996 \cdot 1000 = 996{,}000$ , and $499{,}494$ numbers have been listed. Round $997$ lists $996{,}001$ , $996{,}002$ , and so on. We need the $500{,}000 - 499{,}494 = 506$ th of these, which is $996{,}000 + 506 = 996{,}506$ .

Concise solution

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

Track two running totals after $n$ complete rounds.

Numbers listed: $\sum_{k=1}^{n} (k + 3) = \frac{n(n+1)}{2} + 3n = \frac{n(n+7)}{2}$ .

Integers passed (listed or skipped): $\sum_{k=1}^{n} (2k + 3) = n(n+1) + 3n = n(n+4)$ . So round $n+1$ begins with the integer $n(n+4) + 1$ .

Check: $n = 1$ gives $4$ listed and $5$ passed; $n = 2$ gives $9$ listed and $12$ passed, and the next term is $13$ , matching the given start.

Now find the round containing the $500{,}000$ th term. We need $\frac{n(n+7)}{2} \approx 500{,}000$ , i.e. $n^2 + 7n \approx 1{,}000{,}000$ , so $n \approx 996$ . Indeed
$\frac{996 \cdot 1003}{2} = 498 \cdot 1003 = 499{,}494 < 500{,}000,$
and round $997$ lists $1000$ more, which is plenty. The integers passed after $996$ rounds total $996 \cdot 1000 = 996{,}000$ .

Round $997$ lists $1000$ consecutive integers starting at $996{,}001$ . The $500{,}000$ th term is entry number $500{,}000 - 499{,}494 = 506$ of this block:
$996{,}000 + 506 = 996{,}506.$

The answer is $\boxed{\textbf{(A)}\ 996,506}$ .

Review in the AoPS books

Introduction to Algebra, Chapter 21: Sequences & Series (§21.1, §21.2, §21.3, §21.4)
Introduction to Number Theory, Chapter 1: Integers: The Basics
Intermediate Algebra, Chapter 17: More Sequences and Series (§17.1, §17.2)
Introduction to Algebra, Chapter 20: Special Functions (§20.3)