Difference between revisions of "2014 AMC 10A Problems/Problem 24"

(Solution 2)
m (Solution 4(Cheap))
(20 intermediate revisions by 16 users not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
  
A sequence of natural numbers is constructed by listing the first <math>4</math>, then skipping one, listing the next <math>5</math>, skipping <math>2</math>, listing <math>6</math>, skipping <math>3</math>, and, on the <math>n</math>th iteration, listing <math>n+3</math> and skipping <math>n</math>. The sequence begins <math>1,2,3,4,6,7,8,9,10,13</math>. What is the <math>500,000</math>th number in the sequence?
+
A sequence of natural numbers is constructed by listing the first <math>4</math>, then skipping one, listing the next <math>5</math>, skipping <math>2</math>, listing <math>6</math>, skipping <math>3</math>, and, on the <math>n</math>th iteration, listing <math>n+3</math> and skipping <math>n</math>. The sequence begins <math>1,2,3,4,6,7,8,9,10,13</math>. What is the <math>500,\!000</math>th number in the sequence?
 
 
<math> \textbf{(A)}\ 996,506\qquad\textbf{(B)}\ 996507\qquad\textbf{(C)}\ 996508\qquad\textbf{(D)}\ 996509\qquad\textbf{(E)}\ 996510 </math>
 
  
 +
<math> \textbf{(A)}\ 996,\!506\qquad\textbf{(B)}\ 996,\!507\qquad\textbf{(C)}\ 996,\!508\qquad\textbf{(D)}\ 996,\!509\qquad\textbf{(E)}\ 996,\!510 </math>
  
 
==Solution 1==
 
==Solution 1==
Line 15: Line 14:
 
<math>13,14,15,16,17,18</math> etc.
 
<math>13,14,15,16,17,18</math> etc.
  
so that the <math>500,000</math>th number is the <math>506</math>th number on the <math>997</math>th row. (<math>4+5+6+7......+999 = 499,494</math>) The last number of the <math>996</math>th row (when including the numbers skipped) is <math>499,494 + (1+2+3+4.....+996)= 996,000</math>, (we add the <math>1-996</math> because of the numbers we skip) so our answer is <math>996,000 + 506 = \boxed{\textbf{(A)}996,506}</math>
+
so that the <math>500,000</math>th number is the <math>506</math>th number on the <math>997</math>th row because <math>4+5+6+7......+999 = 499,494</math>. The last number of the <math>996</math>th row (when including the numbers skipped) is <math>499,494 + (1+2+3+4.....+996)= 996,000</math>, (we add the <math>1-996</math> because of the numbers we skip) so our answer is <math>996,000 + 506 = \boxed{\textbf{(A) }996,506}</math>.
 +
 
 +
===Note===
 +
One may also note we simply need to add the number of skipped numbers to <math>500,000</math> to get our answer. The number of skipped numbers is <math>\frac{996\cdot 997}{2}</math> which has a units digit of <math>6</math>. Looking at the answer choices, it becomes apparent that the answer is <math>\boxed{\textbf{(A) }996,506}</math>
 +
 
 +
~firebolt360
  
 
==Solution 2==
 
==Solution 2==
 
Let's start with natural numbers, with no skips in between.
 
Let's start with natural numbers, with no skips in between.
  
<math>1,2,3,4,5,...,500000</math>
+
<math>1,2,3,4,5,...,500,000</math>
 +
 
 +
All we need to do is count how many numbers are skipped, <math>n</math>, and "push" (add on to) <math>500,000</math> according to however many numbers are skipped.
 +
 
 +
Clearly, <math>\frac{999(1000)}{2}<500,000<\frac{1000(1001)}{2}</math>. This means that the number of skipped number "blocks" in the sequence is <math>999-3=996</math> because we started counting from 4.
 +
 
 +
Therefore <math>n=\frac{996(997)}{2}=496,506</math>, and the answer is <math>496,506+500000=\boxed{\textbf{(A) }996,506}</math>.
 +
 
 +
==Solution 3 (AOPS Video Transcript)==
 +
 
 +
First, we group the numbers together in the following way: <math>{1, 2, 3, 4, (5)}; {6, 7, 8, 9, 10, (11, 12)}; ...</math> We quickly realize that the number of terms in the curly braces follow a pattern: <math>5, 7, 9, 11, ... , n</math> (where <math>n</math> is the <math>n^\text{th}</math> block. Now, we can tell that the last number in a curly brace will be the number of terms in the set added to the number of terms in all the previous sets. Luckily for us, odd numbers are easy to add. If we pretend that there was a <math>1, 3</math> at the beginning, then the sum of all of the numbers before and including <math>n</math> is <math>(n+2)^2</math>. However, we have to subtract <math>1+3</math> which results in <math>n^2+4n</math>. The amount of numbers in the parenthesis are the <math>n^\text{th}</math> triangular number or <math>\frac{n(n+1)}{2}</math>. Next, we want to find the greatest <math>n</math>, where <math>(n^2+4n) - \frac{n(n+1)}{2}<500000</math>. Simplifying, we get <math>n^2+7n<1000000</math>. We realize that <math>n=1000</math> results in a number just <math>7000</math> greater than our target. Next, we square <math>999</math>: <math>(1000 - 1)^2 = 1000000 - 2001</math>. As we decrease <math>n</math> by <math>1</math>, we decrease the result of the equation by approximately <math>2000</math>. In order to decrease by at least <math>7000</math>, we have to decrease <math>4</math> times leading to <math>n=1000-4=996</math>. We plug it in to <math>n^2+4n</math> getting <math>996\cdot1000=996000</math>. This is the last number in the <math>996^\text{th}</math> set. The number of terms used is <math>\frac{n\cdot(n+7)}{2}=\frac{996\cdot1003}{2}=498\cdot1003=498000+1494=499494</math>. We need to add <math>500000-499494=506</math> terms to get an answer of <math>\boxed{\textbf{(A) }996,506}</math>.
 +
 
 +
~MathFun1000
 +
 
 +
==Solution 4(Cheap)==
 +
We look at each option starting from <math>A</math>. Clearly <math>500000 + n(n+1)/2 = 996506</math> where <math>n</math> is the number of the skipped numbers. So we have <math>n^2 + n - 987012 = 0</math>. This factors as <math>(n+997)(n-996)</math>. Since <math>n</math> is a positive integer the answer is <math>A</math>.
  
All we need to do is count how many numbers are skipped, <math>n</math>, and "push" (add on to) <math>500000</math> however many numbers are skipped.
+
~coolmath_2018
  
Clearly, <math>\frac{999(1000)}{2}\le500,000</math>. This means that the number skipped number "blocks" in the sequence is <math>999-3=996</math> because we started counting from 4.
+
== Video Solution by Richard Rusczyk ==
  
Therefore <math>n=\frac{996(997)}{2}=496,506</math>, and the answer is <math>496,506+500000=\boxed{\textbf{(A)}996,506}</math>.
+
https://www.youtube.com/watch?v=KfGtE4G6tBo
 +
 
 +
~ dolphin7
  
 
==See Also==
 
==See Also==
Line 32: Line 53:
 
{{AMC10 box|year=2014|ab=A|num-b=23|num-a=25}}
 
{{AMC10 box|year=2014|ab=A|num-b=23|num-a=25}}
 
{{MAA Notice}}
 
{{MAA Notice}}
 +
 +
[[Category:Intermediate Combinatorics Problems]]

Revision as of 22:43, 30 May 2022

Problem

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

$\textbf{(A)}\ 996,\!506\qquad\textbf{(B)}\ 996,\!507\qquad\textbf{(C)}\ 996,\!508\qquad\textbf{(D)}\ 996,\!509\qquad\textbf{(E)}\ 996,\!510$

Solution 1

If we list the rows by iterations, then we get

$1,2,3,4$

$6,7,8,9,10$

$13,14,15,16,17,18$ etc.

so that the $500,000$th number is the $506$th number on the $997$th row because $4+5+6+7......+999 = 499,494$. The last number of the $996$th row (when including the numbers skipped) is $499,494 + (1+2+3+4.....+996)= 996,000$, (we add the $1-996$ because of the numbers we skip) so our answer is $996,000 + 506 = \boxed{\textbf{(A) }996,506}$.

Note

One may also note we simply need to add the number of skipped numbers to $500,000$ to get our answer. The number of skipped numbers is $\frac{996\cdot 997}{2}$ which has a units digit of $6$. Looking at the answer choices, it becomes apparent that the answer is $\boxed{\textbf{(A) }996,506}$

~firebolt360

Solution 2

Let's start with natural numbers, with no skips in between.

$1,2,3,4,5,...,500,000$

All we need to do is count how many numbers are skipped, $n$, and "push" (add on to) $500,000$ according to however many numbers are skipped.

Clearly, $\frac{999(1000)}{2}<500,000<\frac{1000(1001)}{2}$. This means that the number of skipped number "blocks" in the sequence is $999-3=996$ because we started counting from 4.

Therefore $n=\frac{996(997)}{2}=496,506$, and the answer is $496,506+500000=\boxed{\textbf{(A) }996,506}$.

Solution 3 (AOPS Video Transcript)

First, we group the numbers together in the following way: ${1, 2, 3, 4, (5)}; {6, 7, 8, 9, 10, (11, 12)}; ...$ We quickly realize that the number of terms in the curly braces follow a pattern: $5, 7, 9, 11, ... , n$ (where $n$ is the $n^\text{th}$ block. Now, we can tell that the last number in a curly brace will be the number of terms in the set added to the number of terms in all the previous sets. Luckily for us, odd numbers are easy to add. If we pretend that there was a $1, 3$ at the beginning, then the sum of all of the numbers before and including $n$ is $(n+2)^2$. However, we have to subtract $1+3$ which results in $n^2+4n$. The amount of numbers in the parenthesis are the $n^\text{th}$ triangular number or $\frac{n(n+1)}{2}$. Next, we want to find the greatest $n$, where $(n^2+4n) - \frac{n(n+1)}{2}<500000$. Simplifying, we get $n^2+7n<1000000$. We realize that $n=1000$ results in a number just $7000$ greater than our target. Next, we square $999$: $(1000 - 1)^2 = 1000000 - 2001$. As we decrease $n$ by $1$, we decrease the result of the equation by approximately $2000$. In order to decrease by at least $7000$, we have to decrease $4$ times leading to $n=1000-4=996$. We plug it in to $n^2+4n$ getting $996\cdot1000=996000$. This is the last number in the $996^\text{th}$ set. The number of terms used is $\frac{n\cdot(n+7)}{2}=\frac{996\cdot1003}{2}=498\cdot1003=498000+1494=499494$. We need to add $500000-499494=506$ terms to get an answer of $\boxed{\textbf{(A) }996,506}$.

~MathFun1000

Solution 4(Cheap)

We look at each option starting from $A$. Clearly $500000 + n(n+1)/2 = 996506$ where $n$ is the number of the skipped numbers. So we have $n^2 + n - 987012 = 0$. This factors as $(n+997)(n-996)$. Since $n$ is a positive integer the answer is $A$.

~coolmath_2018

Video Solution by Richard Rusczyk

https://www.youtube.com/watch?v=KfGtE4G6tBo

~ dolphin7

See Also

2014 AMC 10A (ProblemsAnswer KeyResources)
Preceded by
Problem 23
Followed by
Problem 25
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
All AMC 10 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png