# Combinatorics with a set number of coins

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
• Please, use descriptive titles. "Is there a mathematical way to solve this question or is guess and check the only way?" says nothing about the subject of the question. It's a useless title. Commented Dec 20, 2022 at 17:32
• @jjagmath Please, use descriptive comments. "It's a useless title" says nothing about the subject of the question. It's a useless comment, as it gives no recommendation on how to fix said title. Commented Dec 20, 2022 at 17:39
• Some preliminary elimination might help. In the 15 coin scenario, they can't all be quarters because that's to much money. They can't all be dimes because that's too little money. The all dime scenario falls short by 50 cents, but swapping in quarters for dimes only adds 15 cents per swap. Figure that means you need at least 4 quarters. So the 15 coin scenario means how many ways are there to make change for 90 cents with 11 coins. Similar reasoning can reduce the 16 coin case. Commented Dec 20, 2022 at 17:42
• @CoolDoodShooz1 You said my comment is useless, and yet you improved the title thanks to my comment. You're welcome ;) Commented Dec 20, 2022 at 18:01

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.

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).

• Could you please give me the name of the equations you are using so I can try to figure out what you just said without bothering you? Commented Dec 20, 2022 at 20:02
• @CoolDoodShooz1 Are you familiar with the modulo operation en.wikipedia.org/wiki/Modulo_operation ? I considered the equation $4m_2+9m_3+24m_4=185$ modulo 3 to obtain $m_2\equiv 2\pmod{3}$ and then I considered it modulo 2 to obtain $m_3 \equiv 1\pmod{2}$. Commented Dec 21, 2022 at 0:41
• By definition this means that there are constants $c_1$ and $c_2$ such that $m_2=2+3c_1$ and $m_3=1+2c_2$. Then I plugged that back into the equation $4m_2+9m_3+24m_4=185$ to obtain an expression for $m_4$ in terms of $c_1$ and $c_2$. Then I rearranged the constants so that I get no fractions in the expression for $m_4$, but that's not necessary if you're ok with fractions. Commented Dec 21, 2022 at 0:43