AMC10 2014 A

AMC10 2014 A · Q24

AMC10 2014 A · Q24. It mainly tests Sequences & recursion (algebra), Recursion & DP style counting (basic).

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,000th number in the sequence?

一个自然数序列通过以下方式构造：先列出前 4 个，然后跳过 1 个，列出接下来 5 个，跳过 2 个，列出 6 个，跳过 3 个，在第 $n$ 次迭代中列出 $n+3$ 个并跳过 $n$ 个。序列开头为 1, 2, 3, 4, 6, 7, 8, 9, 10, 13。序列中的第 500,000 个数是多少？

(A) 996,506 996506

(B) 996,507 996507

(D) 996,509 996509

(E) 996,510 996510

Answer

Correct choice: (A)

正确答案：（A）

Solution

Answer (A): After the $n$th iteration there will be $4+5+6+\cdots+(n+3)=\frac{(n+3)(n+4)}{2}-6=\frac{n(n+7)}{2}$ numbers listed, and $1+2+3+\cdots+n=\frac{n(n+1)}{2}$ numbers skipped. The first number to be listed on the $(n+1)$st iteration will be one more than the sum of these, or $n^2+4n+1$. It is necessary to find the greatest integer value of $n$ such that $\frac{n(n+7)}{2}<500{,}000$. This implies that $n(n+7)<1{,}000{,}000$. Note that, for $n=993$, this product becomes $993\cdot1000=993{,}000$. Next observe that, in general, $(a+k)(b+k)=ab+(a+b)k+k^2$ so $(993+k)(1000+k)=993{,}000+1993k+k^2$. By inspection, the largest integer value of $k$ that will satisfy the above inequality is $3$ and the $n$ needed is $996$. After the $996$th iteration, there will be $\frac{993{,}000+1993\cdot3+9}{2}=\frac{998{,}988}{2}=499{,}494$ numbers in the sequence. The $997$th iteration will begin with the number $996^2+4\cdot996+1=996\cdot1000+1=996{,}001$. The $506$th number in the $997$th iteration will be the $500{,}000$th number in the sequence. This is $996{,}001+505=996{,}506$.

答案（A）：在第 $n$ 次迭代之后，将列出 $4+5+6+\cdots+(n+3)=\frac{(n+3)(n+4)}{2}-6=\frac{n(n+7)}{2}$ 个数，并跳过 $1+2+3+\cdots+n=\frac{n(n+1)}{2}$ 个数。第 $(n+1)$ 次迭代要列出的第一个数，将比上述两者之和大 $1$，即 $n^2+4n+1$。需要找到使得 $\frac{n(n+7)}{2}<500{,}000$ 成立的最大整数 $n$。这意味着 $n(n+7)<1{,}000{,}000$。注意当 $n=993$ 时，乘积为 $993\cdot1000=993{,}000$。再观察一般地，$(a+k)(b+k)=ab+(a+b)k+k^2$，因此 $(993+k)(1000+k)=993{,}000+1993k+k^2$。通过检验，满足上述不等式的最大整数 $k$ 为 $3$，所需 $n=996$。在第 $996$ 次迭代之后，序列中共有 $\frac{993{,}000+1993\cdot3+9}{2}=\frac{998{,}988}{2}=499{,}494$ 个数。第 $997$ 次迭代将以数字 $996^2+4\cdot996+1=996\cdot1000+1=996{,}001$ 开始。第 $997$ 次迭代中的第 $506$ 个数将是序列中的第 $500{,}000$ 个数。它等于 $996{,}001+505=996{,}506$。

Topics