Difference between revisions of "2008 AMC 12A Problems/Problem 17"

m
(Alternate Solution)
Line 23: Line 23:
  
 
So we can set up an equation, <math>3x + 1 = 2(2k - 1)</math> where x is equal to <math>a_1</math>. Rearranging the equation yields <math>(3x + 3)/4 = k</math>. Experimenting yields that every 4th <math>x</math> after 3 creates an integer, and thus satisfies the sequence condition. So the number of valid solutions is equal to <math>2008/4 = 502 \Rightarrow D</math>.
 
So we can set up an equation, <math>3x + 1 = 2(2k - 1)</math> where x is equal to <math>a_1</math>. Rearranging the equation yields <math>(3x + 3)/4 = k</math>. Experimenting yields that every 4th <math>x</math> after 3 creates an integer, and thus satisfies the sequence condition. So the number of valid solutions is equal to <math>2008/4 = 502 \Rightarrow D</math>.
 +
 
==See Also==
 
==See Also==
 
{{AMC12 box|year=2008|ab=A|num-b=16|num-a=18}}
 
{{AMC12 box|year=2008|ab=A|num-b=16|num-a=18}}
 
[[Collatz Problem]]
 
[[Collatz Problem]]
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 14:47, 1 January 2017

Problem

Let $a_1,a_2,\ldots$ be a sequence determined by the rule $a_n=a_{n-1}/2$ if $a_{n-1}$ is even and $a_n=3a_{n-1}+1$ if $a_{n-1}$ is odd. For how many positive integers $a_1 \le 2008$ is it true that $a_1$ is less than each of $a_2$, $a_3$, and $a_4$?

$\mathrm{(A)}\ 250\qquad\mathrm{(B)}\ 251\qquad\mathrm{(C)}\ 501\qquad\mathrm{(D)}\ 502\qquad\mathrm{(E)} 1004$

Solution

All positive integers can be expressed as $4n$, $4n+1$, $4n+2$, or $4n+3$, where $n$ is a nonnegative integer.

  • If $a_1=4n$, then $a_2=\frac{4n}{2}=2n<a_1$.
  • If $a_1=4n+1$, then $a_2=3(4n+1)+1=12n+4$, $a_3=\frac{12n+4}{2}=6n+2$, and $a_4=\frac{6n+2}{2}=3n+1<a_1$.
  • If $a_1=4n+2$, then $a_2=2n+1<a_1$.
  • If $a_1=4n+3$, then $a_2=3(4n+3)+1=12n+10$, $a_3=\frac{12n+10}{2}=6n+5$, and $a_4=3(6n+5)+1=18n+16$.

Since $12n+10, 6n+5, 18n+16 > 4n+3$, every positive integer $a_1=4n+3$ will satisfy $a_1<a_2,a_3,a_4$.

Since one fourth of the positive integers $a_1 \le 2008$ can be expressed as $4n+3$, where $n$ is a nonnegative integer, the answer is $\frac{1}{4}\cdot 2008 = 502 \Rightarrow D$.

Alternate Solution

After checking the first few $a_n$ such as $1$, $2$ through $7$, we can see that the only $a_1$ that satisfy the conditions are odd numbers that when tripled and added 1 to, are double an odd number. For example, for $a_n=3$, we notice the sequence yields $10$, $5$, and $16$, a valid sequence.

So we can set up an equation, $3x + 1 = 2(2k - 1)$ where x is equal to $a_1$. Rearranging the equation yields $(3x + 3)/4 = k$. Experimenting yields that every 4th $x$ after 3 creates an integer, and thus satisfies the sequence condition. So the number of valid solutions is equal to $2008/4 = 502 \Rightarrow D$.

See Also

2008 AMC 12A (ProblemsAnswer KeyResources)
Preceded by
Problem 16
Followed by
Problem 18
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 12 Problems and Solutions

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

Invalid username
Login to AoPS