Let $ \prod_{n=1}^{1996}{(1+nx^{3^n})}= 1+ a_{1}x^{k_{1}}+ a_{2}x^{k_{2}}+...+ a_{m}x^{k_{m}}$ where $a_{1}, a_{1}, . . . , a_{m}$ are nonzero and $k_{1} < k_{2} <...< k_{m}$. Find $a_{1996}$.
Problem
Source: Turkey TST 1996 Problem 1
Tags: algebra proposed, algebra
29.09.2011 03:54
Note that each $k_i$ can be represented by $\sum_{n=1}^{j}c_n3^{n}$, where $c_n \in \{0,1\}$, and $j$ is some positive integer. Also, note that there is no index for $n=0$. Since $\{k_i\}$ is an increasing sequence, we get that each $k_i$ is obtained by transposing $i$ into its base-2 equivalent, shifting it up by one digit (as the lowest exponent is $3$ instead of $1$) and then reading it in base $3$. For example, $k_{10}$ is obtained by taking $10=1010_2$, shifting it up to $10100_2$, then reading in base-3 to get $10100_3 = 90$. To obtain $k_{1996}$, we have $1996=11111001100_2$, and thus $k_{1996} = 111110011000_3 = 3^{11}+3^{10}+3^{9}+3^8+3^7+3^4+3^3$. Therefore $a_{1996} = 11\cdot 10 \cdot 9\cdot 8 \cdot7\cdot4 \cdot 3 = 665280$.
11.09.2013 20:19
It's Pen S 9
14.07.2015 15:40
I don't understand why to find $k_i$ I have to write $2i$ in base 2 and counting in base 3. How do you prove this?
07.11.2015 20:37
Note that $ \prod_{n=1}^{1996}{(1+nx^{3^n})}=(1+x^3)(1+2x^9)(1+3x^{27})...(1+1996x^{3^{1996}})=1+x^3+2x^9+2x^{12}+...$ We will examine the degree of all the terms on the RHS. We can write these degrees in base $3$ to get a sequence of $0, 10, 100, 110, 1000, 1010, 1100, 1110,...$ These seem to be all positive integers in base $2$ written in order with a $0$ added at the end. Thus we just need to find what $1996$ in base $2$ is. We find that $1996_{10} = 11111001100_2$. So this means the degrees of our terms that will be multiplied together are $3^{11}, 3^{10}, 3^9, 3^8, 3^7, 3^4, \text{and}$ $3^3$. From here we just need to multiply out our terms to get $11\cdot10\cdot9\cdot8\cdot7\cdot4\cdot3=665280$.
06.02.2021 19:22
Holder wrote: I don't understand why to find $k_i$ I have to write $2i$ in base 2 and counting in base 3. How do you prove this? The power of an $x$ term in the expansion is the sum of the powers of $3$ (like $3^1, 3^2, 3^3, 3^4, \dots $). Also these powers occur at most once in a term. For example, $(1+x^3)(1+2x^9)(1+3x^{27})(1+4x^{81})$ $ = 30 x^{282} + 30 x^{279} + 15 x^{273} + 15 x^{270} + 10 x^{255} + 10 x^{252} + 5 x^{246} + 5 x^{243} \\ + 24 x^{120} + 24 x^{117} + 12 x^{111} + 12 x^{108} + 8 x^{93} + 8 x^{90} + 4 x^{84} + 4 x^{81} \\ + 6 x^{39} + 6 x^{36} + 3 x^{30} + 3 x^{27} + 2 x^{12} + 2 x^9 + x^3 + 1$. and for the the term $x^{117}$, $117= 3^{4} + 3^{3} + 3^{2} = (11100)_3$. In base $3$, there can only be digits $0 ,1$. But $2$ is not seen. I gave more explanation in Turkish language here.