Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

What values should coins have?

  1. Jul 28, 2007 #1
    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.
     
    Last edited: Jul 28, 2007
  2. jcsd
  3. Jul 28, 2007 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
    Last edited: Jul 28, 2007
  4. Jul 28, 2007 #3

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  5. Jul 28, 2007 #4
    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.

    Code (Text):
    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.
    Code (Text):
    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]:

    Code (Text):
    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.
    Code (Text):
    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
     
    Last edited: Jul 28, 2007
  6. Jul 28, 2007 #5
    Hmm, interesting...I'll look at that situation next.

    So there are two coin types, shillings and pence?
     
  7. Jul 28, 2007 #6
    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...
     
  8. Jul 28, 2007 #7

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.)
     
  9. Jul 28, 2007 #8

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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!
     
  10. Jul 28, 2007 #9
    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.
    Code (Text):
    {{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 cuz that's kinda nasty-looking, here's just the list of x values and then the total number of coins needed:
    Code (Text):
    {{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.
     
  11. Jul 28, 2007 #10

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  12. Jul 28, 2007 #11

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Yes.

    As I suggested above (post 8), it looks like it found suboptimal solutions to 96 and 97, which throws off the true average.
     
  13. Jul 29, 2007 #12
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: What values should coins have?
Loading...