Difference between revisions of "Mock AIME 2 Pre 2005 Problems/Problem 9"
(→Solution) |
(→Solution) |
||
| 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 16: | Line 19: | ||
-MRGORILLA | -MRGORILLA | ||
| + | |||
| + | == See also == | ||
| + | {{Mock AIME box|year=Pre 2005|n=2|num-b=8|num-a=10|source=14769}} | ||
| + | |||
| + | [[Category:Intermediate Number Theory Problems]] | ||
Revision as of 16:07, 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 =665280 =>\boxed{280}\]](http://latex.artofproblemsolving.com/9/0/1/90135463d4b1fd64622501b659e0e2439e635a59.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 | ||
