7
$\begingroup$

In United States, there are four common coins people carry,

\begin{align*} 1 \text{ Penny} &= \$0.01 \\ 1 \text{ Nickel} &= \$0.05 \\ 1 \text{ Dime} &= \$0.10 \\ 1 \text{ Quarter} &= \$0.25 \\ \end{align*}

Define making the exact change as not getting any coins back from the cashier, i. e., paying the fractional dollar in exact coins. E. g., one buys two gallons of milk for $\$10.19$ then making the exact change here means paying the fractional dollar as a dime, a nickel and four pence.

Some people (like myself) always pay the ceiling of the total bill and end-up with an ever increasing pile of coins under the armrest of their cars. To remedy that, I started thinking if I could assure myself of making the exact change each time, I will be better encouraged to actually take some of those coins with me.

Clearly, the more random coins one carries, the greater the probability of making the exact change but,

What is the least amount of pence, nickels, dimes and quarters that guarantees making any change exactly?

Taking a greedy approach, you can conclude that you need 3 quarters since if you needed four then you are paying in a dollar, 2 dimes since three means you can use a quarter, 1 nickel since two of them mean you can use a dime and 4 pence since five would mean you can use a nickel.

Now I want to prove this in a more algebraic way where 4 pence, 1 nickel, 2 dimes and 3 quarters fall out as a solution of something. Let $\lceil x_1\rceil, \lceil x_2\rceil, \lceil x_3\rceil, \lceil x_4\rceil$ be the number of pence, nickels, dimes and quarters then,

  1. Assume that we will on average need 2 of each type of coins.
  2. The coins will have to sum up to more than $\$0.98$ since otherwise we can't make $\$0.99$.

One way I have done it is using this system,

\begin{align*} x_1+x_2+x_3+x_4 &> 8 && \text{By assumption 1}\\ x_1+5x_2+10x_3+25x_4 &> 98 && \text{By observation 2}\\ x_1+x_2 &> 4 && \text{By assumption 1}\\ x_1+5x_2 &> 6 && \text{By an observation similar to 2}\\ \end{align*}

Solving this system does yield,

$$ \lceil x_1\rceil, \lceil x_2\rceil, \lceil x_3\rceil, \lceil x_4\rceil = 4, 1, 2, 3 $$

But I find this proof to be kinda hand-wavy and obvious in its reverse-engineering. Does someone see a better, more elegant algebraic/combinatoric proof here? Maybe something with the binomials or a generating function?

$\endgroup$
10
  • 1
    $\begingroup$ Please, use descriptive titles. "Is there a more elegant proof for this argument?" says nothing about the subject of the question, it's a useless title. See the "Choose a good title" section in How to ask a good question. $\endgroup$
    – jjagmath
    Aug 4 at 10:32
  • $\begingroup$ Is it better now? $\endgroup$
    – scribe
    Aug 4 at 17:56
  • $\begingroup$ Yes, that's better $\endgroup$
    – jjagmath
    Aug 4 at 18:02
  • $\begingroup$ "Assume that we will on average need 2 of each type of coins." Um... why? $\endgroup$
    – fleablood
    Aug 4 at 18:30
  • $\begingroup$ I think the most elegant expression is a modulo proof. If $M\equiv p\pmod 5; 0\le p < 5$ then you need at least $p$ pennies (no american says "pence" BTW) but no more and $p\le 4$. If $M\equiv 5n + p\pmod {10};0\le 5n+p<10\implies n=0,1$ then we need $n$ nickles but no more $n\le 1$. If $M\equiv 10d + 5n+p\pmod{25};d\le 2$ then we need $d$ dimes and no more. If $M\equiv 25q + 10d + 5n + p\pmod{100};q< 4$ then we need $q$ quarters and no more. And all else are bills. $\endgroup$
    – fleablood
    Aug 4 at 18:38

2 Answers 2

1
$\begingroup$

The following MiniZinc model is a machine-wavy view on your problem:

int: TotalCoins = 10;

%  how many coins do wee keep per value?
array[1..4] of var 0..TotalCoins: x;

%  we don't want to keep more coins than necessary
constraint sum(x) == TotalCoins;

constraint forall(s in 1..99) (
      exists(c1 in 0..x[1], c5 in 0..x[2], c10 in 0..x[3], c25 in 0..x[4]) (
        s == (1*c1 + 5*c5 + 10*c10 + 25*c25)
      )
    );
   

For $10$ coins, it comes up with your solution. For less than $10$ coins, no solution exists.

A solution without Nickles:

x = [9, 0, 2, 3];

A solution without Dimes:

x = [4, 4, 0, 3];

A solution without Quarters:

x = [4, 1, 9, 0];
$\endgroup$
0
$\begingroup$

Inspired by @fleablood's comment, here is a proof using moduli,

Proof. Let $t\in\mathbb{N}$ be any dollar amount in cents and $c \in \{5, 10, 25, 100\}$. Define $\max(\mathbb{Z}/c\mathbb{Z})$ as the smallest element of the largest residue class in $\mathbb{Z}/c\mathbb{Z}$ then, $$ \max(\mathbb{Z}/c\mathbb{Z}) = c-1 $$ Observe that any $t \mod c$ can be paid entirely using only the coins worth less than $c$. Since we know that,

$$ \max(t \mod c) = \max(\mathbb{Z}/c\mathbb{Z}) $$ We list the needed minimum number of coins of each type to make $\max(\mathbb{Z}/c\mathbb{Z})$ for each $c$,

\begin{align*} \max(\mathbb{Z}/5\mathbb{Z}) = 5-1 &= 4 && \text{4 Pence.} \\ \max(\mathbb{Z}/10\mathbb{Z}) = 10-1 = 9 &= 5+4 && \text{1 Nickel, 4 Pence.} \\ \max(\mathbb{Z}/25\mathbb{Z}) = 25-1 = 24 &= 10+10+4 && \text{2 Dimes, 4 Pence.} \\ \max(\mathbb{Z}/100\mathbb{Z}) = 100-1 = 99 &= 25+25+25+10+10+4 && \text{3 Quarters,} \\ & && \text{2 Dimes, 4 Pence.} \\ \end{align*}

Therefore, any $t$ can be made exactly with 3 Quarters, 2 Dimes, 1 Nickel and 4 Pence. QED.

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