What values should coins have?

[phoenixthoth]

What values "should" coins have?

Suppose in the current system, there aren't 50 cent pieces, just quarters, dimes, nickels, and pennies. Then the most number of coins you'll ever need is 9. (This happens for .99 and .94.) The average number of coins you need is 4.7 for values from 0 to $1. The quartiles are 3, 5, and 6, meaning that 25% of the time, you need from 0 to 3 coins, 25% of the time you need 4 or 5, 25% of the time 6, and 25% of the time over 6.

How would things change if coins had different values, assuming four types of coins?

To simplify the results, let M be a function that gives the most number of coins you'll ever need, A gives the average, and Q be the quartiles (so the second quartile is the median). What's written above can be translated to:
M(.25, .1, .05, .01) = 9
A(.25, .1, .05, .01) = 4.7
Q(.25, .1, .05, .01) = {3,5,6}.

Not all values of coins are feasible. For instance, if everything is the same except pennies are worth .02 instead of .01, then not all amounts of change can be given with those coins (.01, .11, .21, etc.).

Among the different feasible values for coins, what should the values be to minimize M and A (and Q, I suppose)?
For instance, if the nickel is changed to .03, I get
M(.25, .1, .03, .01) = 8 (you need 8 coins only if you're trying to get .93)
A(.25, .1, .03, .01) = 4.2
Q(.25, .1, .03, .01) = {3,4,5}.

In some sense, changing the value of a nickel to .03 would be better because the average number of coins you need goes down from 4.7 to 4.2.

To try to get an extremely bad scenario, .04, .03, .02, and .01 would be a particularly bad feasible case.
M(.04, .03, .02, .01) = 25 (you need 25 coins if you're trying to get .97, .98, .99, or $1)
A(.04, .03, .02, .01) = 12.9
Q(.04, .03, .02, .01) = {6.75, 13, 19}.

As long as the penny is worth .01, the result is feasible. An even worse feasible case is 1.00, .99, .98, .01:
M(1, .99, .98, .01) = 97
A(1, .99, .98, .01) = 47.1
Q(1, .99, .98, .01) = {21.75, 47, 72.25}.

In the case that the values are no more than .50, here are the worst and best cases:
Worst M:
M(.50, .49, .48, .01) = 48

Worst A:
A(.50, .49, .48, .01)= 22.9

Best M:
M(.27, .08, .03, 0.01) = 7 [7 occurs several times]...compare to 9 in the current case .25, .10, .05, and .01.

Best A:
A(.37, .11, .03, .01) = 4.1 [also occurs when the high is 0.38]...compare to 4.7 in the current case .25, .10, .05, and .01.

Now I'm going to search for the best/worst M and A when the values can go up to 1.00 instead of .50. This will take a lot longer...There were 18,424 cases when the max value is .50 but something like 156,849 cases when the max value is 1.00.

 

[CRGreathouse]

With over 18,000 cases you're not doing this by hand, I imagine. How do you determine the averages? Can you show us code? I'm curious about cases like (50, 49, 48, 1) where the greedy algorithm fails. Edit: In that case you have average 22.9 but I calculate 22.21. The greedy algorithm would give 23.12.

 

[AlephZero]

The old UK system (before decimalization in 1972) was much more elegant mathematically, since 240 had more factors than 100.

The coins and notes less than one pound (= 20 shillings = 240 pence) formed three binary series:

0.25 0.5, 1, 2 pence
3, 6, 12, 24 pence
30, 60, 120, 240 pence.

As a guide to their value in 1970 a pint of beer cost 2 shillings, i.e. 24 pre-decimal pence or 10 modern pence.

 

[phoenixthoth]

With over 18,000 cases you're not doing this by hand, I imagine. How do you determine the averages? Can you show us code? I'm curious about cases like (50, 49, 48, 1) where the greedy algorithm fails. Edit: In that case you have average 22.9 but I calculate 22.21. The greedy algorithm would give 23.12.

I'm using mathematica...

In these definitions, v1-v4 are the values for the coins where I assume v4<v3<v2<v1. x is a desired value to determine the number of coins, given by c. f gives a list of how many coins would be needed in the form {q, d, n, p} where q is the number of coins of value v1 needed, d is number of coins of value v2 needed, n is number of coins of value v3 needed, and p is number of coins of value v4 needed. The last line, c = Total[f] is adding q+d+n+p to get the number of coins needed to result in value x.

q[x_, v1_, v2_, v3_, v4_] := Max[{0, Floor[x/v1]}]
d[x_, v1_, v2_, v3_, v4_] := Max[{0, Floor[(x - q[x, v1, v2, v3, 4]*v1)/v2]}]
n[x_, v1_, v2_, v3_, v4_] :=
   Max[{0, Floor[(x - q[x, v1, v2, v3, v4]*v1 - d[x, v1, v2, v3, v4]*v2)/v3]}]
p[x_, v1_, v2_, v3_, v4_] := Max[{0, Floor[(x - q[x, v1, v2, v3, v4]*v1 - d[x, v1, v2, v3, v4]*v2 - n[x, v1, v2, v3, v4]*v3)/v4]}]
f[x_, v1_, v2_, v3_, v4_] := {q[x, v1, v2, v3, v4], d[x, v1, v2, v3, v4], n[x, v1, v2, v3, v4], p[x, v1, v2, v3, v4]}
c[x_, v1_, v2_, v3_, v4_] := Total[f[x, v1, v2, v3, v4]]

Below, m is the function which gives the most number of coins used when x ranges in [0,1] in increments of .01. a gives the average number of coins used when x ranges in [0,1] in increments of .01 and q gives the quartiles.

m[v1_, v2_, v3_, v4_] := Max[Table[c[x, v1, v2, v3, v4], {x, 0, 1, 1/100}]]
a[v1_, v2_, v3_, v4_] := Mean[Table[c[x, v1, v2, v3, v4], {x, 0, 1, 1/100}]]
q[v1_, v2_, v3_, v4_] := Quartiles[Table[c[x, v1, v2, v3, v4], {x, 0, 1, 1/
  100}]]

I imagine your means are a bit different because I'm (probably not rightly so) including the two extreme cases when no coins are really needed, x=0 and x=1.

Now I want the values v1-v4 to range of all possible ones to search for the worst and best m and a. There's probably a better way to do this but...

This compiles a list of feasible coin values in which .01=v4 < v3 < v2 < v1 <= e/100 where in the case below, e=50, so in that case, the highest valued coin could be up to .50 (the list itself is what I'm calling feasible]:

e = 50;
feasible = Module[{t = {}}, Do[t = Join[t, {{v1, v2, v3, 1/100}}]], {v3, Rationalize[.02], (e - 2)/100, 1/100}, {v2, v3 + 1/100, (e - 1)/100, 1/100}, {v1, v2 + 1/100, e/100, 1/100}]; t];
Length[feasible]
Clear[e]

In the above, Rationalize[.02] is just going to be 2/100=1/50 and Length[feasible] is going to give the number of different sets of values.

The next part of the code I'm not really happy with. It compiles a list of m values and a values for all elements in feasible. After finding the max and min of both m and a, it compiles a list of values where those max's and min's are achieved.

maximums = Table[m[feasible[[k]][[1]], feasible[[k]][[2]], feasible[[k]][[3]], feasible[[k]][[4]]], {k, 1, Length[feasible]}];

averages = Table[a[feasible[[k]][[1]], feasible[[k]][[2]], feasible[[k]][[3]], feasible[[k]][[4]]], {k, 1, Length[feasible]}];

maxmax = Max[maximums];
minmax = Min[maximums];
maxavg = Max[averages];
minavg = Min[averages];

maxmax2 = Module[{t = {}}, Do[If[m[feasible[[k]][[1]], feasible[[k]][[2]], feasible[[k]][[3]], feasible[[k]][[4]]] == maxmax, t = Join[t, {{feasible[[k]][[1]], feasible[[k]][[2]], feasible[[k]][[3]], feasible[[k]][[4]]}, m[feasible[[k]][[1]], feasible[[k]][[2]], feasible[[k]][[3]], feasible[[k]][[4]]]}], t = t], {k, 1, Length[feasible]}]; t];

minmax2 = Module[{t = {}}, Do[If[m[feasible[[k]][[1]], feasible[[k]][[2]], feasible[[k]][[3]], feasible[[k]][[4]]] == minmax, t = Join[t, {{feasible[[k]][[1]], feasible[[k]][[2]], feasible[[k]][[3]], 
              feasible[[k]][[4]]}, m[feasible[[k]][[1]], feasible[[k]][[2]], feasible[[k]][[3]], feasible[[k]][[4]]]}], t = t], {k, 1, Length[feasible]}]; t];

maxavg2 = Module[{t = {}}, Do[If[a[feasible[[k]][[1]], feasible[[k]][[2]], feasible[[k]][[3]], feasible[[k]][[4]]] == maxavg, t = Join[t, {{feasible[[k]][[1]], feasible[[k]][[2]], feasible[[k]][[3]], feasible[[k]][[4]]}, a[feasible[[k]][[1]], feasible[[k]][[2]], feasible[[k]][[3]], feasible[[k]][[4]]]}], t = t], {k, 1, Length[feasible]}]; t];

minavg2 = Module[{t = {}}, Do[If[a[feasible[[k]][[1]], feasible[[k]][[2]], 
                  feasible[[k]][[3]], feasible[[k]][[4]]] == minavg, t = Join[t, {{feasible[[k]][[1]], feasible[[k]][[2]], feasible[[k]][[3]], feasible[[k]][[4]]}, a[feasible[[k]][[1]], feasible[[k]][[2]], feasible[[k]][[3]], feasible[[k]][[4]]]}], t = t], {k, 1, Length[feasible]}]; t];

maxmax2
minmax2
maxavg2
minavg2

 

[phoenixthoth]

The old UK system (before decimalization in 1972) was much more elegant mathematically, since 240 had more factors than 100.

The coins and notes less than one pound (= 20 shillings = 240 pence) formed three binary series:

0.25 0.5, 1, 2 pence
3, 6, 12, 24 pence
30, 60, 120, 240 pence.

As a guide to their value in 1970 a pint of beer cost 2 shillings, i.e. 24 pre-decimal pence or 10 modern pence.

Hmm, interesting...I'll look at that situation next.

So there are two coin types, shillings and pence?

 

[phoenixthoth]

Now that I'm discarding two cases when you really wouldn't use coins, x=0 and x=1, the code changes a bit and for 50, 49, 48, 1, I get an average of 23.33 coins needed...

 

[CRGreathouse]

I imagine your means are a bit different because I'm (probably not rightly so) including the two extreme cases when no coins are really needed, x=0 and x=1.

How curious. I get about 2221/101 ~= 21.99 when I include the endpoints (before I had 1 but not 0 for a nice, round 100 points). Where do we differ? Can you put up a table of how many coins for each total 1..100? (You can back-derive that from the averages if that's easiest for you.)

 

[CRGreathouse]

Now that I'm discarding two cases when you really wouldn't use coins, x=0 and x=1, the code changes a bit and for 50, 49, 48, 1, I get an average of 23.33 coins needed...

You are (very probably) using a greedy algorithm then. That uses 48 coins for n = 97 and 47 coins for n = 96, where 2 coins is the optimal number.

This is an interesting problem you've found, though. Please keep us posted on what you find!

 

[phoenixthoth]

Before I do that, we are talking about the case when v1=.50, v2=.49, v3=.48, and v4=.01, right?

For x going from .01 to .99...
In this list, the first entries are the x values, the second entry is giving the numbers of the 4 types of coins needed and the third entries are the totals of the second entries, the total number of coins needed.

{{0.01, {0, 0, 0, 1}, 1}, {0.02, {0, 0, 0, 2}, 2}, {
  0.03, {0, 0, 0, 3}, 3}, {0.04, {0, 0, 0, 4}, 4}, {
  0.05, {0, 0, 0, 5}, 5}, {0.06, {0, 0, 0, 6}, 6}, {
  0.07, {0, 0, 0, 7}, 7}, {0.08, {0, 0, 0, 8}, 8}, {
  0.09, {0, 0, 0, 9}, 9}, {0.1, {0, 0, 0, 10}, 10}, {0.11, {0, 0, 
    0, 11}, 11}, {0.12, {0, 0, 0, 12},
   12}, {0.13, {0, 0, 0, 13}, 13}, {0.14, {0, 
    0, 0, 14}, 14}, {0.15, {0, 0, 0, 15}, 15}, {0.16, {0, 0,
   0, 16}, 16}, {0.17, {0, 0, 0, 17}, 17}, {0.18, {0, 
  0, 0, 18}, 18}, {0.19, {0, 0, 0, 19}, 19}, {0.2, {0,
   0, 0, 20}, 20}, {0.21, {0, 0, 0, 21}, 21}, {0.22, {0,
   0, 0, 22}, 22}, {0.23, {0, 0, 0, 23}, 23}, {0.24, {0,
   0, 0, 24}, 24}, {0.25, {0, 0, 0, 25}, 25}, {0.26, {0,
   0, 0, 26}, 26}, {0.27, {0, 0, 0, 27}, 27}, {0.28, {0,
   0, 0, 28}, 28}, {0.29, {0, 0, 0, 29}, 29}, {0.3, {0, 
  0, 0, 30}, 30}, {0.31, {0, 0, 0, 31}, 31}, {0.32, {0, 
  0, 0, 32}, 32}, {0.33, {0, 0, 0, 33}, 33}, {0.34, {0, 
  0, 0, 34}, 34}, {0.35, {0, 0, 0, 35}, 35}, {0.36, {0, 
  0, 0, 36}, 36}, {0.37, {0, 0, 0, 37}, 37}, {0.38, {0, 0, 0, 
  38}, 38}, {0.39, {0, 0, 0, 39}, 39}, {0.4, {0,
   0, 0, 40}, 40}, {0.41, {0, 0, 0, 41}, 41}, {0.42, {
  0, 0, 0, 42}, 42}, {0.43, {0, 0, 0, 43}, 43}, {0.44, {
  0, 0, 0, 44}, 44}, {0.45, {0, 0, 0, 45}, 45}, {0.46, {
  0, 0, 0, 46}, 46}, {0.47, {0, 0, 0, 47}, 47}, {0.48, {
  0, 0, 1, 0}, 1}, {0.49, {0, 1, 0, 0}, 1}, {0.5, {1, 0,
   0, 0}, 1}, {0.51, {1, 0, 0, 1}, 2}, {0.52, {1, 0, 0, 
  2}, 3}, {0.53, {1, 0, 0, 3}, 4}, {0.54, {1, 0, 0, 4}, 
  5}, {0.55, {1, 0, 0, 5}, 6}, {0.56, {1, 0, 0, 6}, 7}, {0.57, {1, 0, 
    0, 7}, 8}, {0.58, {1, 0, 0, 8}, 9}, {0.59, {1, 0, 
    0, 9}, 10}, {0.6, {1, 0, 0, 10}, 11}, {0.61, {1, 0, 0, 11}, 12}, {0.62, {
    1, 0, 0, 12}, 13}, {0.63, {1, 0, 0, 13}, 14}, {0.64, {1, 0,
   0, 14}, 15}, {0.65, {1, 0, 0, 15}, 16}, {0.66, {1, 
  0, 0, 16}, 17}, {0.67, {1, 0, 0, 17}, 18}, {0.68, {1, 0, 0, 18},
     19}, {0.69, {1, 0, 0, 19}, 20}, {0.7, {1, 0, 0, 
    20}, 21}, {0.71, {1, 0, 0, 21}, 
    22}, {0.72, {1, 0, 0, 22}, 23}, {0.73, {1, 0, 0, 23}, 
    24}, {0.74, {1, 0, 0, 24}, 25}, {0.75, {1, 0, 0, 25}, 
    26}, {0.76, {1, 0, 0, 26}, 27}, {0.77, {1, 0, 0, 27}, 
    28}, {0.78, {1, 0, 0, 28}, 29}, {0.79, {1, 
  0, 0, 29}, 30}, {0.8, {1, 0, 0, 30}, 31}, {0.81, {1,
   0, 0, 31}, 32}, {0.82, {1, 0, 0, 32}, 33}, {0.83, {1,
   0, 0, 33}, 34}, {0.84, {1, 0, 0, 34}, 35}, {0.85, {1,
   0, 0, 35}, 36}, {0.86, {1, 0, 0, 36}, 37}, {0.87, {1,
   0, 0, 37}, 38}, {0.88, {1, 0, 0, 38}, 39}, {0.89, {1,
   0, 0, 39}, 40}, {0.9, {1, 0, 0, 40}, 41}, {0.91, {1, 
  0, 0, 41}, 42}, {0.92, {1, 0, 0, 42}, 43}, {0.93, {1, 
  0, 0, 43}, 44}, {0.94, {1, 0, 0, 44}, 45}, {0.95, {1, 
  0, 0, 45}, 46}, {0.96, {1, 0, 0, 46}, 47}, {0.97, {1, 
  0, 0, 47}, 48}, {0.98, {1, 0, 1, 0}, 2}, {0.99, {1, 1, 0, 0}, 2}}

And because that's kinda nasty-looking, here's just the list of x values and then the total number of coins needed:

{{0.01, 1}, {0.02, 2}, {0.03, 3}, {0.04, 4}, {0.05, 5}, {0.06, 6}, {
  0.07, 7}, {0.08, 8}, {0.09, 9}, {0.1, 10}, {
  0.11, 11}, {0.12, 12}, {0.13, 13}, {0.14, 14}, {0.15, 15}, {0.16, 
  16}, {0.17, 17}, {0.18, 18}, {0.19, 19}, {0.2, 20}, {0.21,
     21}, {0.22, 22}, {0.23, 23}, {0.24, 24}, {0.25, 25}, {0.26, 26}, {0.27,
     27}, {0.28, 28}, {0.29, 29}, {0.3, 30}, {0.31, 31}, {0.32, 32}, {0.33, 
    33}, {0.34, 34}, {0.35, 35}, {0.36, 36}, {0.37, 
    37}, {0.38, 38}, {0.39, 39}, {0.4, 40}, {0.41, 41}, {0.42, 42}, {0.43,
     43}, {0.44, 44}, {0.45, 45}, {0.46, 46}, {0.47, 47}, {0.48, 1}, {0.49, 
    1}, {0.5, 
  1}, {0.51, 2}, {0.52, 3}, {0.53, 4}, {0.54, 5}, {0.55, 6}, {
    0.56, 7}, {0.57, 8}, {0.58, 9}, {0.59, 10}, {
    0.6, 11}, {0.61, 12}, {0.62, 13}, {0.63, 14}, {0.64, 15}, {0.65, 16}, \
{0.66, 17}, {0.67, 18}, {0.68, 19}, {0.69, 20}, {0.7, 21}, {0.71, 22}, {0.72,
     23}, {0.73, 24}, {0.74, 25}, {0.75, 26}, {0.76, 27}, {0.77, 28}, {0.78,
     29}, {0.79, 30}, {
    0.8, 31}, {0.81, 32}, {0.82, 33}, {0.83, 34}, {0.84, 35}, {0.85, 36}, \
{0.86, 37}, {0.87, 38}, {0.88, 39}, {0.89, 40}, {0.9, 41}, {0.91,
   42}, {0.92, 43}, {0.93, 44}, {0.94, 45}, {0.95, 46}, {0.96,
     47}, {0.97, 48}, {0.98, 2}, {0.99, 2}}

For the average number of coins needed, I get 70/3 ~ 23.33.

 

[CRGreathouse]

Hmm, interesting...I'll look at that situation next.

So there are two coin types, shillings and pence?

Many coin types, with various colloquial names. 5d = 1s now (decimal), but the old penny was worth less, 12d = 1s. Ijn both cases 20 shillings were a pound sterling.

When I was in Wales, the coins were the half-pence (0.5), penny (1), shilling (5), ten pence (10), twenty pence (20), fifty pence (50), and the pound (100). There were larger coins as well, at least a 2-pound coin, but I didn't often see those.

 

[CRGreathouse]

Before I do that, we are talking about the case when v1=.50, v2=.49, v3=.48, and v4=.01, right?

Yes.

As I suggested above (post 8), it looks like it found suboptimal solutions to 96 and 97, which throws off the true average.

 

[phoenixthoth]

Not sure why it took as long as it did but "I" checked all cases where .99>=v1>v2>v3>v4=.01 and two came up with the lowest average number of coins needed:
.37, .11, .03, .01 and
.38, .11, .03, .01 both use an average of
410/99 ~ 4.14 coins per value in (0,1). In both of these cases, the most number of coins needed is 7.

Compare to the standard case, .25, .10, .05, and .01 which results in
470/99 ~ 4.75 coins per value and a max of 9 coins needed.

In this table of ordered pairs (x,y), x is the number of coins needed in the standard case minus the coins needed in the case .37, .11, .03, .01, and y is the number of times (for values in (0,1)) that difference happens:

{{-4, 1}, {-3, 2}, {-2, 13}, {-1, 9}, {0, 22}, {1, 20}, {2, 18}, {3, 9}, {4, 4}, {5, 0}, {6, 1}}.

When x is negative, the standard case is better, when 0 they give the same number of coins needed, and when x is positive, the standard case requires more coins. The standard case is worse in 20+18+9+4+1 = 52 cases, the same in 22 cases, and better in 1+2+13+9 = 25 cases.