Difference between revisions of "Mock AIME 2 Pre 2005 Problems/Problem 9"
(Created page with "== Solution == We begin by determining the value of <math>k_{1997}</math>. Experimenting, we find the first few <math>k_{i}</math>s: <cmath>k_{1} = 3, k_{2} = {3^2}, k_{3} =...") |
(→Solution) |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| + | == Problem == | ||
| + | Let <cmath>(1+x^3)\left(1+2x^{3^2}\right)\cdots \left(1+kx^{3^k}\right) \cdots \left(1+1997x^{3^{1997}}\right) = 1+a_1 x^{k_1} + a_2 x^{k_2} + \cdots + a_m x^{k_m}</cmath> where <math>a_i \ne 0</math> and <math>k_1 < k_2 < \cdots < k_m</math>. Determine the remainder obtained when <math>a_{1997}</math> is divided by <math>1000</math>. | ||
| + | |||
== Solution == | == Solution == | ||
| Line 8: | Line 11: | ||
We observe that because <math>{3^k}>\sum_{n=1}^{k-1} {3^n}</math>, <math>k_{i}</math> will be determined by the base 2 expansion of i. Specifically, every 1 in the <math>2^{(n-1)}</math>s digit of the expansion corresponds to adding <math>3^n</math> to <math>k_{i}</math>. Since <math>1997 = 11111001101</math> base 2, | We observe that because <math>{3^k}>\sum_{n=1}^{k-1} {3^n}</math>, <math>k_{i}</math> will be determined by the base 2 expansion of i. Specifically, every 1 in the <math>2^{(n-1)}</math>s digit of the expansion corresponds to adding <math>3^n</math> to <math>k_{i}</math>. Since <math>1997 = 11111001101</math> base 2, | ||
| − | <cmath>k_{1997}={3^11}+{3^10}+{3^9}+{3^8}+{3^7}+{3^4}+{3^3}+{3^1}.</cmath> | + | <cmath>k_{1997}={3^{11}}+{3^{10}}+{3^9}+{3^8}+{3^7}+{3^4}+{3^3}+{3^1}.</cmath> |
Now we look for ways to attain an element with degree <math>k_{1997}</math>. Since each sum of powers of 3 is unique, there is only one; namely, take the x element for every binomial with a degree of one of the added powers of 3 in <math>k_{1997}</math>, and the 1 for all else. Finally, since the coefficients of the x elements are equal to the degree to which the 3 is raised, we conclude | Now we look for ways to attain an element with degree <math>k_{1997}</math>. Since each sum of powers of 3 is unique, there is only one; namely, take the x element for every binomial with a degree of one of the added powers of 3 in <math>k_{1997}</math>, and the 1 for all else. Finally, since the coefficients of the x elements are equal to the degree to which the 3 is raised, we conclude | ||
<cmath>a_{1997}=11*10*9*8*7*4*3*1 | <cmath>a_{1997}=11*10*9*8*7*4*3*1 | ||
| − | = | + | =665\boxed{280}. |
| − | + | </cmath> | |
| + | |||
| + | -MRGORILLA | ||
| + | |||
| + | == See also == | ||
| + | {{Mock AIME box|year=Pre 2005|n=2|num-b=8|num-a=10|source=14769}} | ||
| + | |||
| + | [[Category:Intermediate Number Theory Problems]] | ||
Latest revision as of 23:22, 31 December 2020
Problem
Let ![\[(1+x^3)\left(1+2x^{3^2}\right)\cdots \left(1+kx^{3^k}\right) \cdots \left(1+1997x^{3^{1997}}\right) = 1+a_1 x^{k_1} + a_2 x^{k_2} + \cdots + a_m x^{k_m}\]](http://latex.artofproblemsolving.com/6/4/2/642a3134837deae29f73ef1e2df3daa87321b4e1.png)
where 
and 
. Determine the remainder obtained when 
is divided by 
.
Solution
We begin by determining the value of 
. Experimenting, we find the first few 
s:
![\[k_{1} = 3, k_{2} = {3^2}, k_{3} = {3^2}+3, k_{4} = {3^3}...\]](http://latex.artofproblemsolving.com/e/c/2/ec25b2f4e8bcb96d11cc80eca12a5141e930f954.png)
We observe that because 
, will be determined by the base 2 expansion of i. Specifically, every 1 in the 
s digit of the expansion corresponds to adding 
to . Since 
base 2,
![\[k_{1997}={3^{11}}+{3^{10}}+{3^9}+{3^8}+{3^7}+{3^4}+{3^3}+{3^1}.\]](http://latex.artofproblemsolving.com/e/f/2/ef2776c115da46de44ccbfb1bfced24494f29fab.png)
Now we look for ways to attain an element with degree . Since each sum of powers of 3 is unique, there is only one; namely, take the x element for every binomial with a degree of one of the added powers of 3 in , and the 1 for all else. Finally, since the coefficients of the x elements are equal to the degree to which the 3 is raised, we conclude
![\[a_{1997}=11*10*9*8*7*4*3*1 =665\boxed{280}.\]](http://latex.artofproblemsolving.com/a/b/3/ab37335ef9fe448f53162f9af01d13f775950ff0.png)
-MRGORILLA
See also
| Mock AIME 2 Pre 2005 (Problems, Source) | ||
| Preceded by Problem 8 |
Followed by Problem 10 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
