# 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