I have this statement:

In how many ways, you can pay $12,000$ dollars, with bills of $10,000$ , $5,000$ and $1,000$ dollars?

I can do combinatorics like:

$1)$ 1 bill of $10,000$ and two of $1,000$

$2)$ 2 bills of $5,000$ and two of $1,000$

Well, but i read a other solution that says:

Get all natural solutions of:

$12 = 10a + 5b + c$

then, $a$, $b$ and $c$ can be $\{0, 1, 2, 3..\}$ $\rightarrow \mathbb{N}$, example:

$12 = 10*1 + 5*0 + c*2$, with $a=1$, $b = 0$ and $c = 2$

But how can I find all naturals solutions? Like determinant in quadratic equations.

  • $\begingroup$ So rather than figuring out the specific answer to this specific problem (which is trivial), you are asking for a general formula/method/equation to figure out the answer for these general types of question, right? $\endgroup$ – Bram28 Mar 13 '18 at 14:28
  • 1
    $\begingroup$ Look at your second example again. $\endgroup$ – user535339 Mar 13 '18 at 14:28

We must have $a \in \{0,1\}$,

If $a=1,$ the problem becomes $$2 = 5b+c$$

Hence $b=0, c=2$.

If $a=0$, the problem become $$12=5b+c$$

Only $3$ cases $b \in \{0,1,2\}$ and for each case we can get our $c$.


$10a+5b+c=12$, because $a,b,c$ are natural numbers, $a$ can only be $0$ or $1$ (if $a \ge 2$ than the total would be more than or equal to $20$, contradiction).

With $a=0$, we have $5b+c=12$ and with $a=1$, we have $5b+c+10=12$, for both cases we can get the solution easily, using the method on this question.


This cannot be obtained by a formula, but using a recursive algorithm:

  • order the bills by decreasing value;

  • try all possible numbers of the largest bill that fit, and solve the same problem on the remainder and without using the largest bill.

In this case, $12$ using $10,5,1$:

  • $1\times10$ and solve for $2$ using $5,2$;

    • $0\times5$ and solve for $2$ using $1$;
  • $0\times10$ and solve for $12$ using $5,2$;

    • $2\times 5$ and solve for $2$ using $1$;

    • $1\times5$ and solve for $7$ using $1$;

    • $0\times5$ and solve for $12$ using $1$.

(All the "using $1$" subproblems are trivial.)


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.