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

Question

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?

Answer 1

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];

Answer 2

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.