3
$\begingroup$

How many solutions are there to the equation $$a + 10b + 20c = 100$$ where $a,b,c$ are non-negative integers

The problem I'm asking is another way of phrasing "How many ways can you break $100$ dollars into $1$, $10$, and $20$ dollar bills", or any multitude of variants.

Solutions can, for example, be $(a,b,c) = (100, 0, 0)$, $(10, 7, 1)$, $(0, 6, 2)$, etc.

I wrote a quick program which gave me a total of $36$ solutions, but I'd like to have a better understanding as to where this answer comes from without something resembling brute-force. Preferably, I'd like to see how to use generating functions to solve this, as that was the method I first tried (and failed) with.

The solution should be the coefficient of the 100th-power term in the product:

$$(1 + x + x^2 + x^3 + ...)(1 + x^{10} + x^{20} + ...)(1 + x^{20} + x^{40} + ...)$$ I can get this coefficient from the following: $$\lim_{x \to 0} \frac{1}{100!} \frac{d^{100}}{dx^{100}}(1 + x + x^2 + x^3 + ...)(1 + x^{10} + x^{20} + ...)(1 + x^{20} + x^{40} + ...)$$ For whatever reason, applying product rule fails (or I fail to use it correctly), as I get $3$. So, assuming $|x| < 1$, this equals: $$\lim_{x \to 0} \frac{1}{100!} \frac{d^{100}}{dx^{100}} \frac{1}{(1-x)(1-x^{10})(1-x^{20})}$$ However, to much dismay, this is not such a simple thing to find derivatives of. Any advice?

$\endgroup$
  • $\begingroup$ I got $36$ as coefficient of $x^{100}$ so you were right... $$\ldots + 30 x^{98}+30 x^{99}+36 x^{100}+35 x^{101}+35 x^{102}+35 x^{103}+\ldots$$ $\endgroup$ – Raffaele Oct 20 '17 at 21:10
  • $\begingroup$ @Raffaele : You should get $36$ for every coefficient from $x^{100}$ to $x^{109}$. $\endgroup$ – Eric Towers Oct 20 '17 at 21:18
  • $\begingroup$ Calculating the 100th derivative is definitely harder than writing the solutions one by one. An idea is to use partial fraction decomposition on $\frac{1}{(1-x)(1-x^{10})(1-x^{20})}$ and then sum the coefficients in front of $x^{100}$. But this can be rather tedious and hard to do too. $\endgroup$ – Stefan4024 Oct 20 '17 at 21:20
  • $\begingroup$ The first time I used polynomial with a degree too low. I remade my calculations with higher degree polynomials (using Mathematica) and finally got $$\ldots+42 x^{111}+42 x^{110}+36 x^{109}+36 x^{108}+36 x^{107}+36 x^{106}+36 x^{105}+36 x^{104}+36 x^{103}+36 x^{102}+36 x^{101}+36 x^{100}+30 x^{99}+\ldots$$ BTW, I did not know this combinatorial trick :) $\endgroup$ – Raffaele Oct 20 '17 at 21:31
4
$\begingroup$

You can simplify fairly drastically, since $a = 100-10b-20c$ means $a$ must be a multiple of $10$. So setting $a' := a/10$, we have $a' + b + 2c = 10$.

Again $a'$ is determined by $b$ and $c$, so we just need $b+2c\le 10$. For $c=\{0,1,2,3,4,5\}$ we have $\{11,9,7,5,3,1\}$ options for $b$, for a total of $36$ possible combinations.

$\endgroup$
  • $\begingroup$ Nifty! Thanks for that argument. I was able to reduce it as well after reading up on the subject, but I quite like your closing argument to take $b + 2c \le 10$ and check the number of options for each $b$ at fixed $c$ $\endgroup$ – infinitylord Oct 20 '17 at 22:32
  • $\begingroup$ Thanks. Although sadly(?) not using generating functions. With a little extension you can see that the same answer also applies to target values from $101$ to $109$ (using $a' = (a-r)/10$). $\endgroup$ – Joffan Oct 20 '17 at 22:39
  • $\begingroup$ Slight generalization: For $x,y,z$ non-negative integers, the number of solutions to $x + by + cz = d$ where $b|c$, and $c|d$ is $(\frac{d}{2b} + 1)^2$ $\endgroup$ – infinitylord Oct 21 '17 at 2:08
2
$\begingroup$

Er, ..., calculate carefully?

$$(1 + x + x^2 + x^3 + ...)(1 + x^{10} + x^{20} + ...)(1 + x^{20} + x^{40} + ...) \\ = \dots +30 x^{98} + 30 x^{99} + 36 x^{100} + 36 x^{101} + ...$$


Another way: Suppose there are $n_k$ ways to write $k$ as a non-negative integer weighted sum of $\{1,10\}$. Then the total number of ways to write $k$ as a non-negative integer weighted sum of $\{1,10,20\}$ is $N = n_0 + n_{20} + n_{40} + n_{60} + n_{80} + n_{100}$, where $n_0$ counts the number of ways we finish by adding five $20$s, $n_{20}$ the number of ways we finish by adding four $20$s, ..., and $n_{100}$ the number of ways we finish by adding no $20$s.

  • Now $n_0 = 1$ because $0 \cdot 1 + 0 \cdot 10$ is the only way to write $0$ as a non-negative integer weighted sum of $\{1,10\}$.
  • And $n_{20} = 3$, depending on whether there are zero, one, or two $10$s in the sum, the rest being made up with $1$s.
  • And $n_{40} = 5$, for the same reason : zero to four $10$s and the remainder made of $1$s.
  • Finishing, $n_{60} = 7$, $n_{80} = 9$, and $n_{100} = 11$.

Finally, $N = 1 + 3 + 5 + 7 + 9 + 11 = 36$. That the number of ways is controlled by the $10$s and $20$s, with the $1$ making up the rest, is hinted in the snippet of the series in $x$, above. There is only one way to make totals up to $9$ from $\{1,10,20\}$. There are two ways for totals in $[10,19]$, four ways in $[20,29]$, six ways in $[30,31]$, nine ways in $[40,41]$, where the increment in the number of ways in each range of ten totals increases by $1$ each time we pass a multiple of $20$ (counting that we could either include or exclude one more $20$ in our sums).


Another way: You don't have to multiply out the full power series. You can calculate with $$( 1 + x+ x^2 + \cdots + x^{99} + x^{100})(1 + x^{10} + \cdots + x^{100})(1+x^{20}+\cdots+x^{100})$$ always discarding any term with power greater than $100$. If you do this from right to left, you essentially perform the calculation described above.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.