Difference between revisions of "1986 AIME Problems/Problem 7"
God of Math (talk | contribs) (Alternate solution) |
Math Kirby (talk | contribs) m |
||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | 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> | + | 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>100^{\mbox{th}}</math> term of this sequence. |
− | == Solution 1 == | + | == 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>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>. | 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 === | |
− | |||
− | == 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> | 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> |
Revision as of 12:38, 4 September 2011
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
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 |