Difference between revisions of "1986 AIME Problems/Problem 7"
I_like_pie (talk | contribs) (→See also) |
God of Math (talk | contribs) (Alternate solution) |
||
Line 2: | Line 2: | ||
The increasing [[sequence]] <math>1,3,4,9,10,12,13\cdots</math> consists of all those positive [[integer]]s which are [[exponent|powers]] of 3 or sums of distinct powers of 3. Find the <math>\displaystyle 100^{\mbox{th}}</math> term of this sequence. | The increasing [[sequence]] <math>1,3,4,9,10,12,13\cdots</math> consists of all those positive [[integer]]s which are [[exponent|powers]] of 3 or sums of distinct powers of 3. Find the <math>\displaystyle 100^{\mbox{th}}</math> term of this sequence. | ||
− | == Solution == | + | == Solution 1 == |
− | Rewrite all of the terms in base 3. Since the numbers are sums of ''distinct'' powers of 3, in base 3 each number is a sequence of 1s and 0s (if there is a 2, then it is no longer the sum of distinct powers of 3). Therefore, we can recast this into base 2 (binary) in order to determine the 100th number. <math>100</math> is equal to <math>64 + 32 + 4</math>, so in binary form we get <math> | + | |
+ | Rewrite all of the terms in base 3. Since the numbers are sums of ''distinct'' powers of 3, in base 3 each number is a sequence of 1s and 0s (if there is a 2, then it is no longer the sum of distinct powers of 3). Therefore, we can recast this into base 2 (binary) in order to determine the 100th number. <math>100</math> is equal to <math>64 + 32 + 4</math>, so in binary form we get <math>1100100</math>. However, we must change it back to base 3 for the answer, which is <math>3^6 + 3^5 + 3^2 = 729 + 243 + 9 = 981</math>. | ||
+ | |||
+ | ------------------------------------------------------------- | ||
+ | |||
+ | == Solution 2 == | ||
+ | |||
+ | Notice that the first term of the sequence is <math>1</math>, the second is <math>9</math>, the fourth is <math>27</math>, and so on. Thus the <math>64th</math> term of the sequence is <math>729</math>. Now out of <math>64</math> terms which are of the form <math>729</math> + <math>'''S'''</math>, <math>32</math> of them include <math>243</math> and <math>32</math> do not. The smallest term that includes <math>243</math>, i.e. <math>972</math>, is greater than the largest term which does not, or <math>854</math>. So the <math>95</math>th term will be <math>972</math>, then <math>973</math>, then <math>976</math>, then <math>977</math>, and finally <math>981</math> | ||
== See also == | == See also == |
Revision as of 02:03, 30 June 2009
Contents
Problem
The increasing sequence consists of all those positive integers which are powers of 3 or sums of distinct powers of 3. Find the term of this sequence.
Solution 1
Rewrite all of the terms in base 3. Since the numbers are sums of distinct powers of 3, in base 3 each number is a sequence of 1s and 0s (if there is a 2, then it is no longer the sum of distinct powers of 3). Therefore, we can recast this into base 2 (binary) in order to determine the 100th number. is equal to , so in binary form we get . However, we must change it back to base 3 for the answer, which is .
Solution 2
Notice that the first term of the sequence is , the second is , the fourth is , and so on. Thus the term of the sequence is . Now out of terms which are of the form + , of them include and do not. The smallest term that includes , i.e. , is greater than the largest term which does not, or . So the th term will be , then , then , then , and finally
See also
1986 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 6 |
Followed by Problem 8 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |