Number of ways in which $2010$ can be formed using $2,5,10$.

Question

We can form $10$ using $2,5,10$ in $3$ ways. In how many ways can we form $2010(201*10)$. My teacher mentioned. $202*203/2$ I cannot figure out how. I also saw a DP method for finding number of ways in which a sum can be obtained. If there is a direct formula for calculating this after finding it to some factor of a number, Why do we have a polynomial time algorithm?

Answer 1

a number $10n$ can be formed using $10$ and $5$ only in $n+1$ ways (there can be any number from $0$ to $n$ $10$-coins)

The previous statement implies the number of $2$-coins must be a multiple of $5$

since $2010=201\cdot2\cdot5$ the number of $2$-coins can be any number between $0$ and $201$ and using the previous paragraph this means that when there are exactly $5k$ coins of value $2$ there are $\frac{210-10k}{10}+1$ ways to pay the remaining cash using $2$ and $5$ coins.Using this we see there are $202+201+\dots+2+1$ ways to make up $2010$ using $2,5$ and$10$-coins. Using Gaussian summation we find this is equal to $\frac{202\cdot203}{2}$

Answer 2

This might not be the smartest way to solve this. You want to solve $2x+5y+10z=2010$ for $x,y,z$ nonnegative integers.

We see $y$ must be even say $=2y'$ (why?), so we have $2x+10y'+10z=2010$, that is $x+5y'+5z=1005$. We must have $5\mid x'$ so we want to solve $x'+y'+z=201$. This is the coefficient of $x^{201}$ in $(1+x+x^2+\cdots)(1+x+x^2+\cdots)(1+x+x^2+\cdots)$ (why?)

Since $$\frac{1}{(1-x)^3}=\sum_{k\geqslant 0}\binom{2+k}{k}x^k=\sum_{k\geqslant 0}\frac{(2+k)(k+1)}{2}x^k$$

this gives $\dfrac{203\cdot 202}{2}$ solutions.

Answer 3

Since we have $$2x+5y+10z=2010\Rightarrow 2x=5(402-y-2z),$$ $x$ has to be represented as $x=5k$. Hence we have $$2\cdot 5k+5y+10z=2010\Rightarrow 2k+y+2z=402\Rightarrow y=2(201-k-z).$$ Since $y$ has to be even, letting $y=2m$, we have $$2k+2m+2z=402\Rightarrow k+m+z=201\Rightarrow m+z=201-k.$$ Since for each $0\le k\le 201$ such that $m+z=201-k$, there are $201-k+1$ pairs for $(m,z)$.

Hence, the answer is $$\sum_{k=0}^{201}(201-k+1)=202+\sum_{k=1}^{201}k=202+\frac{201\cdot 202}{2}=\frac{202\cdot 203}{2}.$$

Answer 4

We have to solve the equation $$2x+5y+10z=2010\tag{1}$$ in nonnegative integers. From $(1)$ we immediately deduce that $x$ has to divisible by $5$, and $y$ has to be divisible by $2$. Writing $x=5u$, $y=2v$ we obtain the new equation $$u+v+z=201\ ,\tag{2}$$ which has $$N:={201+2\choose 2}=20\,503$$ solutions in nonnegative integers. (This is a "stars and bars" problem: Any solution $(u,v,z)$ of $(2)$ can be encoded as a binary sequence consisting of $u$ stars, a bar, $v$ stars, a bar, and $z$ stars, containing $201$ stars in all. There are ${203\choose 2}$ such sequences.) The number $N$ is also the solution to the original problem.

Answer 5

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ As ${\tt @Christian Blatter}$ and ${\tt @mathlove}$ have already shown in their straightforward answers, it's sufficient to look for combinations of $\ds{\braces{a,b,c}}$ such that $\ds{a + b + c = 201}$. Those are given by:

\begin{align}&\color{#66f}{\large \sum_{a=0}^{\infty}\sum_{b=0}^{\infty}\sum_{c=0}^{\infty} \delta_{a\ +\ b\ +\ c\ ,\ 201}} =\sum_{a=0}^{\infty}\sum_{b=0}^{\infty}\sum_{c=0}^{\infty} \oint_{0\ <\ \verts{z}\ <\ 1}\ {1 \over z^{-a - b - c + 202}}\,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{0\ <\ \verts{z}\ <\ 1}\ {1 \over z^{202}} \sum_{a=0}^{\infty}z^{a}\sum_{b=0}^{\infty}z^{b} \sum_{c=0}^{\infty}z^{c}\,{\dd z \over 2\pi\ic} =\oint_{0\ <\ \verts{z}\ <\ 1}\ {1 \over z^{202}}\,{1 \over \pars{1 - z}^{3}}\,{\dd z \over 2\pi\ic} \\[5mm]&=\sum_{n = 0}^{\infty}\pars{-1}^{k}{-3 \choose k}\ \overbrace{\oint_{0\ <\ \verts{z}\ <\ 1}\ {1 \over z^{202 - k}}\,{\dd z \over 2\pi\ic}} ^{\color{#c00000}{\ds{=\ \delta_{k\,,\,201}}}} =\pars{-1}^{201}{-3 \choose 201} \\[5mm]&=-\braces{\pars{-1}^{201}{-\bracks{-3} + 201 - 1 \choose 201}} ={203 \choose 201} = {203! \over 201!\ 2!} = {203\times 202 \over 2} =203\times 101 \\[3mm]&=\color{#66f}{\large 20503} \end{align}