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

Possibleness of greedy payment

  1. Nov 2, 2011 #1
    1. The problem statement, all variables and given/known data

    You have a series of coins with different values. You want to buy something, but the store will only accept if you pay with the minimum number of coins possible. What conditions do the values of your coins have to satisfy in order for it to be safe to pay by always choosing the largest possible coin? (you never try to buy something with a value that you can't construct from your coins)(you have as many of each type of coin as you want)

    2. Relevant equations

    3. The attempt at a solution

    So far I've come to the conclusion that if you arrange the values in rising order from left to right, then value number x, let's call it V(x), must be at least V(x-1) + (V(x-1)-V(x-2)).

    E. g. 1 3 5 is valid because 5 is at least as large as 3+(3-1), whereas 1 3 4 is invalid.

    The reason being that always choosing the largest possible coin will fail for 2*V(x-1) if V(x)-V(x-1) < V(x-1)-V(x-2), because then V(x)+V(x-2) < 2*V(x-1). With numbers:

    the values 1 3 4 will fail for 2*3 because 4-3 < 3-1, and hence 4+1 < 2*3. Since you always choose the largest possible coin you will begin by choosing 4. 3 is out of the question because 2*3 < 3+4 (that is, 2*V(x-1) < V(x) + V(x-1)), so you have to choose 1. But since 4+1 < 2*3 (that is, V(x)+V(x-2) < 2*V(x-1)) you have to choose at least one more coin, and thus you have to use at least three coins to do something that can be done with two (two coins with value V(x-1)).

    In conclusion V(x) - V(x-1) < V(x-1) - V(x-2) leads to fail, so V(x) >= V(x-1) + (V(x-1)-V(x-2))

    Apologies for the rather poor explanation, my wording skills aren't the best. What I'm not able to figure out is if this is a sufficient condition or if there are other conditions that the values of the coins must also satisfy.
    Last edited: Nov 2, 2011
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?