$42$ (U.S.) coins make $\$1$. If there's at least one quarter, dime, nickel, and penny, find the number of dimes and nickels.

Question

My piggy bank has $42$ coins worth exactly $\$1.00$. If it has at least one quarter, dime, nickel, and penny, find the total number of dimes and nickels.

I found $1+ 5 + 10 +25 =41$ cents with the minimum of each which then leaves $59$ cents and $38$ coins. I know there needs to be more pennies and if there was another quarter it would mean $34$ cents with $37$ coins which is impossible. So no more quarters. I'm then stuck

Answer 1

You've rightly pointed out that you can have no more quarters. So we can form a couple of equations.

If $p = $ no. of extra pennies, $d = $ no. of extra dimes, and $n = $ no. of extra nickels we have:

$p + d + n = 38$ (total number of coins),

and $1p + 5n + 10d = 59.$

Unfortunately we only have 2 equations for 3 unknowns, so we can't solve it directly. But we do have (by subtracting the first from the second) that:

EDIT Thank for pointing out a numerical error:

$4n + 9d = 21.$ Which can be solved if $n = 3$ and $d = 1.$

Plugging these values into our initial equal equations we get: $p + 4 = 38$ so $p = 34.$

In total you have $35$ pennies, $4$ nickels, $2$ dimes and a quarter.

So your total number of dimes and nickels is $6$

Answer 2

We have 59 cents to be realised with 38 coins. We can reduce this to 55 cents in 34 coins because the other four cents can only be realised by pennies (the other coins are multiples of five cents).

There must be five pennies in this remaining 55 cents, otherwise the most number of coins realising this amount would be 11 nickels. We can repeat this process on the remaining 50 cents in 29 coins until getting 25 cents in 4 coins, having taken out 25 pennies. The only way to realise this value is 3 nickels and 1 dime.

Thus we have 1 quarter, 2 dimes, 4 nickels and 35 pennies comprising the dollar, and there are six dimes and nickels combined.

Answer 3

Weighted pigeon hole method.

You have 38 coins into which you need to fit 59 cents, which at least 1 cent in each coin. That leaves you with 21 unallocated cents. Each coin can hold either 4 more cents or 9 more cents. So you need to find a partition of 21 consisting solely of 4's and 9's. At most 2 false starts will get you 21 = 4 + 4 + 4 + 9. That makes 3 more nickels and a dime for a total of 4 nickels and 2 dimes, or 6 nickels and dimes.

Answer 4

To get to $59$ cents, you know that at least $4$ of the $38$ coins must be pennies. This brings the known counts to one quarter, one dime, one nickel, and $5$ pennies, and leaves $34$ unassigned coins to total $55$ cents. At most $11$ of these can be nickels or higher, so at least $23$ must be pennies. Since pennies must come in groups of $5$, at least $25$ must be pennies. This brings the known counts to one quarter, one dime, one nickel, and $30$ pennies, and leaves $9$ coins to total $30$ cents. Once again, at most $6$ of these coins can be a nickel or higher, so at least $3$ must be pennies, which means, again, that at least $5$ must be pennies. This brings the known counts to one quarter, one dime, one nickel, and $35$ pennies, and leaves $4$ coins to total $25$ cents.

At this point, pennies can no longer be used (since they must come in groups of $5$), nor can quarters. It's not hard to jump straight to the answer, but let's be methodical: Since $25\gt4\cdot5$, we need at least one dime, and since $25\lt3\cdot10$, we can use at most two dimes, so we need at least $2$ nickels. This leaves $1$ coin to total $5$ cents, i.e. another nickel, so the $4$ coins totalling $25$ cents must be $3$ nickels and one dime. This brings to final known counts to $1$ quarter, $2$ dimes, $4$ nickels, and $35$ pennies.

Alternatively, let $P=p+1$, $N=n+1$, $D=d+1$, and $Q=q+1$ be the number of pennies, nickels, dimes, and quarters, where $p,n,d,q\ge0$. We have $P+N+D+Q=42$ and $P+5N+10D+25Q=100$, which imply

$$p+n+d+q=38$$ and $$p+5n+10d+25q=59$$

Subtracting these gives

$$4n+9d+24q=21$$

which immediately implies $q=0$, leaving $4n+9d=21$. Since $21$ is odd while $4$ is even, we must have $d$ odd, which means $d=1$ (since $d\ge3\implies9d\ge27\gt21$) and thus $4n=12$, so $n=3$. Thus $p=38-3-1-0=34$, hence $(P,N,D,Q)=(35,4,2,1)$.