Combinatorics with a set number of coins

Question

I came upon this question yesterday and was wondering about it:

Sydney started the day with $15$ coins in her pocket which totaled $2.00$ dollars. At the end of the day, after a number of transactions, she had $16$ coins which totaled $3.00$ dollars. She had only quarters, dimes, nickels, and pennies, and ended the day with a different number of each type of coin than she had started with (one or the other of which could have been zero). If she started with $m$ quarters and ended with $n$ quarters, what is $m + n$?

After a long, brute force process, I determined that $m + n = 18$, with her original coins being $7$ quarters, $1$ dime, $2$ nickels, and $5$ pennies, and her coins at the end of the day being $11$ quarters, $0$ dimes, $5$ nickels, and $0$ pennies.

I achieved this answer by completely brute-forcing my way through all of the possible coin combinations and figuring it out after about an hour and a half. Is there a better way to do this (without a calculator) that I could have done?

For reference:

• quarter = $0.25$ dollar
• dime = $0.10$ dollar
• nickel = $0.05$ dollar
• penny = $0.01$ dollar

Answer 1

Let $m_1$, $m_2$, $m_3$ and $m_4$ be the number of pennies, nickles, dimes and quarters at the start of the day, respectively.

The problem boils down to solving $4m_2+9m_3+24m_4=185$ over the integers. Applying modular arithmetic this reduces to $m_2 = 2+3c_1$, $m_3=1+4c_1+8c_2$ and $m_4=7-2c_1-3c_2$, where $c_1$ and $c_2$ are arbitrary integer constants.

Since we are looking for non-negative solutions, clearly $0\leq c_1\leq 3$ and $0\leq c_2\leq 2$, which reduces the brute-force check to less than 12 possibilities, some of which we can immediately discard (e.g. $c_2=2$ and $c_1\neq 0$).

You quickly find that the only solution that makes sense is for $c_1=c_2=0$, i.e. $m_2=2$, $m_3=1$ and $m_4=7$, meaning that $(m_1,m_2,m_3,m_4)=(5,2,1,7)$ is a solution for the start of the day.

Similar technique applies to the end-of-day case, where $n_1$, $n_2$, $n_3$ and $n_4$ are the numbers of the coins at the end of the day. However, one has to apply modular arithmetic to all 4 equations obtained by eliminating one of the $n_i$'s from the system $$ n_1+n_2+n_3+n_4=16\\ n_1+5n_2+10n_3+25n_4=300 $$ until a solution that satisfies the problem is found (i.e. such that $n_i\neq m_i$ for $i=1,2,3,4$).

This is found already by applying the same reasoning above to the equation $-4n_1+5n_3+20n_4=220$ (obtained by eliminating $n_2$ from the system above).

Answer 2

Due to the nature of the problem I don't think there is a general method that is really better than figuring out the combinations ad-hoc. But it is possible to work out the combinations much faster than in an hour and a half.

For the $2.00$ case, consider the case where there is a penny. Then there must be at least five pennies. If there are five pennies than we have to make $1.95$ with the other $10$ coins. Try seven quarters and three other coins; the three coins have to total $0.20$ so the are a dime and two nickels. Try six quarters; then we need $0.45$ with four coins, impossible when the largest coin is $0.10.$

If there are more than five pennies, there are ten, so we need to get $1.90$ with five coins, which is not possible when the largest coin is $0.25.$

So the only combination with pennies is $7(0.25) + 1(0.10) + 2(0.05) + 5(0.01).$

Without pennies, the largest possible number of quarters is $6$ (leaving $0.50$ to be made up by $9$ other coins) and the least possible number is $4$ (leaving $1.00$ to be made up by $11$ other coins). For each number of quarters there will be at most one way to make the remaining amount in nickels and dimes, so let's put off working that out exactly until we see what happens with $3.00$ dollars.

For $3.00$, that equals $12$ quarters; to increase the number of coins to $16$ you can trade one quarter for $5$ other coins, two quarters for $6$ other coins, etc.

None of the other coins can be pennies because we'd have to use at least five pennies and then we'd need to make $2.95$ with the remaining $11$ coins.

If you have $11$ quarters you need to make $0.25$ with five coins, so you have five nickels and no other coins.

If you have $10$ quarters you need to make $0.50$ with six coins, which can only be $4(0.10) + 2(0.05).$

You can't have $9$ quarters because then you'd need $7$ other coins to total $0.75.$

So there are no pennies at the end of the day, which means Sydney started with $7(0.25) + 1(0.10) + 2(0.05) + 5(0.01).$

So she can't have ended with two nickels, which rules out the $10$ quarters case. That leaves only $11$ quarters: $11(0.25) + 0(0.10) + 5(0.05) + 0(0.01) = 3.00.$ Check that all four numbers of coins are different from the start of the day. They are. So that's the solution.

Note that if I had started with the $3.00$ case I would have known that the $2.00$ case had to have pennies in it before I started analyzing that case, and I could have saved the effort of thinking about how to make $2.00$ without pennies.