Counting nickels, dimes and quarters, order matters.

combinatoricsdiscrete mathematics

A parking meter costs 5 cents per minute and only accepts the nickels, dimes or quarters. How many different ways can $n$ minutes be purchased by inserting coins into the parking meter where the order in which the coins are inserted matters? Let $A_n$ be the number of ways $n$ minutes can be purchased and assume that the correct initial values have been defined for $A_0, A_1, A_2$, etc. have been defined as needed. Recall that 1 quarter = 25 cents, 1 dime =10 cents, and 1 nickel = 5 cents.

Answer choices

$A_n = A_{n-5} + A_{n-2} + A_{n-1}$

$A_n = A_{n-25} + A_{n-10} + A_{n-5}$

$A_n = A_{n-5} \cdot A_{n-2} \cdot A_{n-1}$

$A_n = 5\cdot A_{n-5} +2\cdot A_{n-2} + A_{n-1}$

Part of my work or
Explanation and Justification:
The simpler rows are justified by writing out the sequences.
I explain more complex rows with the following formula.
w-xNyDzQ
xN represents number of Nickels
yD represents number of Dimes
zQ represents number of Quarters
w is the number of permutations of that set of nickels, dimes and quarters.
Note: "order matters" so 15 cents from ND is different from DN

Ex. From row $A_4$, 3-2N1D represents two nickels and one dime. NND, NDN, DNN is 3 permutations.

$A_n$	Value	Count	Justification
$A_0$	0	0	{null set is empty**}
$A_1$	5	1	{N}
$A_2$	10	2	{NN}, {D}
$A_3$	15	3	{N}, {ND, DN}
$A_4$	20	5	NNNN, 3-2N1D, DD
$A_5$	25	9	1-5N, 4-3ND, 3-1N2D, 1Q
$A_6$	30	14	1-6N, 5-4N,1D, 6-2N2D, 2-QN

** In my humble opinion, I.M.H.O., $A_0$ should be excluded from the question to make the recursive rule work.

However, my $A_4$, $A_5$, $A_6$ don't fit any of the options given for recursive formulas.
$A_{n-25}$ would be related 125 cents prior, not 25 cents prior, so option 2 is pretty clearly incorrect. Option 3 and option 4 seem to be growing far quicker than my table.
Option 1 is the closest fit, but breaks down on $A_6$.

Best Answer

Thanks to @GerryMyerson I figured it out. I was missing the 3 dimes permutation in the $A_6$ row. That row should list a count of 15 which is consistent with the recursive formula for multiple choice 1.

Related Solutions

[Math] On problems of coins totaling to a given amount

Question (2) is a known problem; it's called the change-making problem. The Wikipedia page lists integer programming and dynamic programming as solution approaches. The change-making problem is also a variation of the famous knapsack problem. One of the implications of that is that since the standard version of the knapsack problem is NP-complete, it's likely that the change-making problem is as well, dashing hopes for an easy-to-find fast algorithm for solving it.

However, the Wikipedia page also says that for the US and most other coin systems, the greedy algorithm will give the optimal solution. Thus for the nickel/dime/quarter example you give, the optimal solution is to use as many quarters as you can, then account for what's left by using as many dimes as you can, then make up the rest with nickels. So 3 is the minimum number of nickels, dimes, and quarters required to make 40 cents.

Here's the integer program formulation for Question (2). If you let $x_i$ be the number of coins of type $i$ to be used, $d_i$ be the denomination of coin type $i$, and $A$ be the target amount, Question (2) entails solving

$$\min \sum_i x_i $$ subject to $$\sum_i d_i x_i = A,$$ $$x_i \geq 0, x_i \in \mathbb{Z}.$$

While integer programs are hard to solve in general, for small problems like the example you give a good IP solver will return a solution very quickly. For instance, if you take coins of denominations 31, 37, and 41 cents (since nickels, dimes, and quarters are too easy :) ), and want to know the minimum number required to be equivalent to 2011 cents, the solver Lingo requires only the following code to find the answer:

MIN = x1 + x2 + x3;
31*x1 + 37*x2 + 41*x3 = 2011;
@GIN(x1); @GIN(x2); @GIN(x3);

Lingo outputs the optimal solution as $x_1 = 0, x_2 = 20, x_3 = 31,$ with only 7 solver iterations and "00:00:00" time elapsed. So the minimum number of coins is $51$.

You did ask specifically for an algorithm. Many IP solvers (including Lingo) use the branch and bound algorithm, which has solving a linear program (usually with the simplex method) embedded in it.

For Question (1), you could use the following integer program to find a single solution or determine that one does not exist. (In the latter case, the IP solver will report that the problem is infeasible.)

$$\max 1$$ subject to $$\sum_i d_i x_i = A,$$ $$\sum_i x_i = n,$$ $$x_i \geq 0, x_i \in \mathbb{Z}.$$

Again, for small problems a good IP solver will return a solution almost instantaneously. I'm not sure how (or even if it's possible) to modify an IP approach to find all solutions like you request. The generating function techniques mentioned by cardinal and in the question linked to by Derek Jennings will tell you how many solutions there are, but I'm not sure if they will tell you exactly what those solutions are.

[Math] Find the number of ways of making change for a dollar with coins where the number of coins is odd

Here's the generating function solution:

The generating function that counts all ways of making change is:

$$ \text{all}(x) = \frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})} $$

[That is, the coefficient of $x^{100}$ is the number of ways to make change of a dollar.]

If we look at the function

$$ \text{alternating}(x) = \frac{1}{(1+x)(1+x^5)(1+x^{10})(1+x^{25})} $$

Then the coefficient of $x^{100}$ is (number of ways to do it with even number of coins) - (number of ways to do it with odd number of coins) [can you see why?]. From here you can easily solve for both (even number of ways) and (odd number of ways).

Best Answer

Related Solutions

[Math] On problems of coins totaling to a given amount

[Math] Find the number of ways of making change for a dollar with coins where the number of coins is odd

Related Question