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 00:22, 1 January 2021
Problem
Let 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:
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,
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
-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 |