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 "Mock AIME 2 Pre 2005 Problems/Problem 9"

(→‎Solution)
(→‎Solution)
 
(2 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 12: Line 15:
 
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
−
=665280
+
=665\boxed{280}.
−
=>\boxed{280}</cmath>
+
</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}\] where $a_i \ne 0$ and $k_1 < k_2 < \cdots < k_m$. Determine the remainder obtained when $a_{1997}$ is divided by $1000$.

Solution

We begin by determining the value of $k_{1997}$. Experimenting, we find the first few $k_{i}$s: \[k_{1} = 3, k_{2} = {3^2}, k_{3} = {3^2}+3, k_{4} = {3^3}...\]

We observe that because ${3^k}>\sum_{n=1}^{k-1} {3^n}$, $k_{i}$ will be determined by the base 2 expansion of i. Specifically, every 1 in the $2^{(n-1)}$s digit of the expansion corresponds to adding $3^n$ to $k_{i}$. Since $1997 = 11111001101$ base 2, \[k_{1997}={3^{11}}+{3^{10}}+{3^9}+{3^8}+{3^7}+{3^4}+{3^3}+{3^1}.\]

Now we look for ways to attain an element with degree $k_{1997}$. 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 $k_{1997}$, 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}.\]

-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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_2_Pre_2005_Problems/Problem_9&oldid=141238"