Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1986 AIME Problems/Problem 7"

(→‎Solution 4)
(→‎Solution 5)
 
(11 intermediate revisions by the same user not shown)
Line 18: Line 18:
 
Writing out a few terms of the sequence until we reach the next power of 3 (27), we see that the <math>2^{nth}</math> term is equal to <math>3^n</math>. From here, we can ballpark the range of the 100th term. The 64th term is <math>3^6</math> = <math>729</math> and the 128th term is <math>3^7</math> = <math>2187</math>. Writing out more terms of the sequence until the next power of 3 again (81) we can see that the (<math>2^n</math>+<math>2^{n+1}</math>)/2 term is equal to <math>3^n</math> + <math>3^{n-1}</math>. From here, we know that the 96th term is <math>3^6</math> + <math>3^5</math> = <math>972</math>. From here, we can construct the 100th term by following the sequence in increasing order. The 97th term is <math>972 + 1 = 973</math>, the 98th term is <math>972 + 3 = 975</math>, the 99th term is <math>972 + 3 + 1 = 976</math>, and finally the 100th term is <math>972 + 9 = \boxed{981}</math>
 
Writing out a few terms of the sequence until we reach the next power of 3 (27), we see that the <math>2^{nth}</math> term is equal to <math>3^n</math>. From here, we can ballpark the range of the 100th term. The 64th term is <math>3^6</math> = <math>729</math> and the 128th term is <math>3^7</math> = <math>2187</math>. Writing out more terms of the sequence until the next power of 3 again (81) we can see that the (<math>2^n</math>+<math>2^{n+1}</math>)/2 term is equal to <math>3^n</math> + <math>3^{n-1}</math>. From here, we know that the 96th term is <math>3^6</math> + <math>3^5</math> = <math>972</math>. From here, we can construct the 100th term by following the sequence in increasing order. The 97th term is <math>972 + 1 = 973</math>, the 98th term is <math>972 + 3 = 975</math>, the 99th term is <math>972 + 3 + 1 = 976</math>, and finally the 100th term is <math>972 + 9 = \boxed{981}</math>
  
−
=== Solution 5 ===
+
=== Solution 5 ===
−
The number of terms <math>3^n</math> produces includes each power of 3 before(<math>1, 3^1, ...</math>), the sums of two power of 3s, three power of 3s, and so on and so forth to the sum of all. Hence, we can represent the number of terms as <math>{n}\choose{0}</math>
+
The number of terms <math>3^n</math> produces includes each power of 3 (<math>1, 3^1, ..., 3^n</math>), the sums of two power of 3s(ex. <math>3^1 + 1</math>), three power of 3s (ex. <math>3^1 + 1 + 3^n</math>), all the way to the sum of them all. Since there are <math>n+1</math> powers of 3, the one number sum gives us <math>{n+1\choose 1} </math> terms, the two number <math>{n+1\choose 2} </math> terms, all the way to the sum of all the powers which gives us <math>{n+1\choose n+1}</math> terms. Summing all these up gives us <math>2^{n+1} - 1 ^ {*}</math> according to the theorem <center><math>\sum_{k=0}^N{{N}\choose{k}} = 2^N</math>.</center>
 +
Since <math>2^6</math> is the greatest power <math><100</math>, then <math>n=5</math> and the sequence would look like {<math>3^0, ..., 3^5</math>}, where <math>3^5</math> or <math>243</math> would be the <math>2^5 - 1 = 63</math>rd number. The next largest power <math>729</math> would be the 64th number. However, its terms contributed extends beyond 100, so we break it to smaller pieces.
 +
Noting that <math>729</math> plus any combination of lower powers <math>{1, 3^1 . . .3^4}</math> is < <math>729 + 243</math>, so we can add all those terms(<math>2^5 - 1 = 31</math>) into our sequence:
 +
<center>{<math>3^0, ..., 3^5, 729, 729 + 1, .... 729 + (1 + 3^1 + . . . +3^4)</math>}</center>
 +
Our sequence now has <math>63 + 1 + 31 = 95</math> terms. The remaining <math>5</math> would just be the smallest sums starting with <math>729 + 243</math> or <math>972</math>:
 +
 
 +
<center>[<math>972</math>, <math>972 + 1</math>, <math>972 + 3</math>, <math>972+1+3</math>, <math>972 + 9</math>]</center>
 +
Hence the 100th term would be <math>972 + 9 = \boxed{981}</math>. ~SoilMilk
 +
 
 +
<math>{}^{*}</math>Note that there isn't a <math>{n+1\choose 0}</math> as choosing 0 numbers will not give you a term.
  
 
== See also ==
 
== See also ==

Latest revision as of 00:00, 22 December 2022

Problem

The increasing sequence $1,3,4,9,10,12,13\cdots$ consists of all those positive integers which are powers of 3 or sums of distinct powers of 3. Find the $100^{\mbox{th}}$ term of this sequence.

Solutions

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. $100$ is equal to $64 + 32 + 4$, so in binary form we get $1100100$. However, we must change it back to base 10 for the answer, which is $3^6 + 3^5 + 3^2 = 729 + 243 + 9 = \boxed {981}$.

Solution 2

Notice that the first term of the sequence is $1$, the second is $3$, the fourth is $9$, and so on. Thus the $64th$ term of the sequence is $729$. Now out of $64$ terms which are of the form $729$ + $'''S'''$, $32$ of them include $243$ and $32$ do not. The smallest term that includes $243$, i.e. $972$, is greater than the largest term which does not, or $854$. So the $96$th term will be $972$, then $973$, then $975$, then $976$, and finally $\boxed{981}$

Solution 3

After the $n$th power of 3 in the sequence, the number of terms after that power but before the $(n+1)$th power of 3 is equal to the number of terms before the $n$th power, because those terms after the $n$th power are just the $n$th power plus all the distinct combinations of powers of 3 before it, which is just all the terms before it. Adding the powers of $3$ and the terms that come after them, we see that the $100$th term is after $729$, which is the $64$th term. Also, note that the $k$th term after the $n$th power of 3 is equal to the power plus the $k$th term in the entire sequence. Thus, the $100$th term is $729$ plus the $36$th term. Using the same logic, the $36$th term is $243$ plus the $4$th term, $9$. We now have $729+243+9=\boxed{981}$

Solution 4

Writing out a few terms of the sequence until we reach the next power of 3 (27), we see that the $2^{nth}$ term is equal to $3^n$. From here, we can ballpark the range of the 100th term. The 64th term is $3^6$ = $729$ and the 128th term is $3^7$ = $2187$. Writing out more terms of the sequence until the next power of 3 again (81) we can see that the ($2^n$+$2^{n+1}$)/2 term is equal to $3^n$ + $3^{n-1}$. From here, we know that the 96th term is $3^6$ + $3^5$ = $972$. From here, we can construct the 100th term by following the sequence in increasing order. The 97th term is $972 + 1 = 973$, the 98th term is $972 + 3 = 975$, the 99th term is $972 + 3 + 1 = 976$, and finally the 100th term is $972 + 9 = \boxed{981}$

Solution 5

The number of terms $3^n$ produces includes each power of 3 ($1, 3^1, ..., 3^n$), the sums of two power of 3s(ex. $3^1 + 1$), three power of 3s (ex. $3^1 + 1 + 3^n$), all the way to the sum of them all. Since there are $n+1$ powers of 3, the one number sum gives us ${n+1\choose 1}$ terms, the two number ${n+1\choose 2}$ terms, all the way to the sum of all the powers which gives us ${n+1\choose n+1}$ terms. Summing all these up gives us $2^{n+1} - 1 ^ {*}$ according to the theorem

$\sum_{k=0}^N{{N}\choose{k}} = 2^N$.

Since $2^6$ is the greatest power $<100$, then $n=5$ and the sequence would look like {$3^0, ..., 3^5$}, where $3^5$ or $243$ would be the $2^5 - 1 = 63$rd number. The next largest power $729$ would be the 64th number. However, its terms contributed extends beyond 100, so we break it to smaller pieces. Noting that $729$ plus any combination of lower powers ${1, 3^1 . . .3^4}$ is < $729 + 243$, so we can add all those terms($2^5 - 1 = 31$) into our sequence:

{$3^0, ..., 3^5, 729, 729 + 1, .... 729 + (1 + 3^1 + . . . +3^4)$}

Our sequence now has $63 + 1 + 31 = 95$ terms. The remaining $5$ would just be the smallest sums starting with $729 + 243$ or $972$:

[$972$, $972 + 1$, $972 + 3$, $972+1+3$, $972 + 9$]

Hence the 100th term would be $972 + 9 = \boxed{981}$. ~SoilMilk

${}^{*}$Note that there isn't a ${n+1\choose 0}$ as choosing 0 numbers will not give you a term.

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

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1986_AIME_Problems/Problem_7&oldid=184415"