GeneratingFunction PUMaC Difficult
2011


Problem - 4326

For every integer $n$ from $0$ to $6$, we have $3$ identical weights with weight $2^n$ grams. How many total ways are there to form a total weight of $263$ grams using only these weights?


The answer is the coefficient of the $x^{263}$ in the expanded form of the following polynomial. $$\begin{align*} f(x)=\ &(1+x+x^2+x^3)\left(1+x^2+x^{2\times 2}+x^{2\times 3}\right)\\ &\cdots \\ &\left(1+x^{2^6}+x^{2^{6}\times 2}+x^{2^{6}\times 3}\right) \\ =\ &\frac{x^4-1}{x-1}\cdot\frac{x^8-1}{x^2-1}\cdots\frac{x^{256}-1}{x^{64}-1}\\=\ &\frac{x^{128}-1}{x^2-1}\cdot\frac{x^{256}-1}{x-1}\\= &\left(1+x^2+x^{4}\cdots+x^{126}\right)\left(1+x+x^2+\cdots+x^{255}\right)\end{align*}$$

In order to obtain one $x^{263}$ term, we must take one term from the first bracket whose exponent is at least $8$. There are totally $60$ such terms. For each of these terms, there is one unique matching term in the second bracket to make their product $x^{263}$. Hence, the desired result is $\boxed{60}$. 

report an error