3
$\begingroup$

Mr. Long Johns has 2 pennies, 3 nickels, 2 dimes, 3 quarters, and 8 dollar coins. For how many different amounts can John make an exact purchase? (no change required)

  • A penny is 1 cent
  • A nickel is 5 cents
  • A dime is 10 cents
  • A quarter is 25 cents
  • A dollar coin is 100 cents

So....
1 cent
2 cents
5 cents
6 cents
7 cents
10 cents
11 cents
12 cents....
Any other way other than brute force?

$\endgroup$
  • $\begingroup$ Yes, it can be done without brute force. It's a decent exercise in mental arithmetic. $\endgroup$ – David K Jan 21 '15 at 5:14
  • $\begingroup$ So the only way is brute force then $\endgroup$ – suomynonA Jan 21 '15 at 5:43
3
$\begingroup$

Count the amounts you can get that are under a dollar (we'll jigger the rest in momentarily).

If you do a few, you'll see them as ${0,1,2,5,6,7,10,11,12...}$ - three out of each five consecutive values.

There are $3/5*100 = 60$ such values (including zero - we'll get to that...)

For each of the nine possible dollars used (including zero), that gives $9*60 = 540$.

Now, drop the zero case, $540-1 = 539$.

Finally, add in the values where a dollar's worth of non-dollar coins and the eight dollar coins are combined with the remaining coins: $9.00, 9.01, 9.02, 9.05, 9.06, 9.07, 9.10, 9.11, 9.12$ - so nine of them.

That gives $539+9 = 548$ possible distinct amounts.

$\endgroup$
2
$\begingroup$

You can have $0,1$ or $2$ pennies, so work out how many ways without pennies and multiply by 3.
You can either make a full dollar or more with loose change, or not.
If not, you can make any multiple of $5c$ from $0c$ to $95c$, and any number of dollars from $0$ to $8$.
If you make at least a dollar with loose change, you can also make $9.00$, $9.05$ and $9.10$.
Put them together, and subtract $1$ from the final total for $0c$.

$\endgroup$
1
$\begingroup$

Based on http://ocw.mit.edu/courses/mathematics/18-310c-principles-of-applied-mathematics-fall-2007/lecture-notes/22_2_ln.pdf the generating function for the possible amounts is:

$$ \sum_{i=0}^2 x^i \sum_{j=0}^3 x^{5j} \sum_{k=0}^2 x^{10k} \sum_{l=0}^3 x^{25l} \sum_{m=0}^8 x^{100m}$$

which can be expanded and the possible amounts are the exponents of $x$ in that expanded form (possible ways to make them are the coefficients of these terms).

$\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.