Mock AIME 2 Pre 2005 Problems/Problem 9

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