Possibleness of greedy payment

[Appledave]

Homework Statement

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)

Homework Equations

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.

 

[nate808]

Any help would be greatly appreciated.

Hello,

Thank you for your post. Your reasoning is correct, and your condition is sufficient for ensuring that always choosing the largest possible coin will result in the minimum number of coins being used to make a purchase. This is because if V(x) - V(x-1) < V(x-1) - V(x-2), then you will not be able to make the purchase with the minimum number of coins, as you have explained.

However, there is another condition that must be satisfied for this method to work. The values of the coins must also be relatively prime, meaning that they do not share any common factors other than 1. This is because if there are common factors, then there are certain values that cannot be constructed using only the given coins. For example, if you have coins with values 2 and 4, you will not be able to make a purchase with a value of 3, as it cannot be constructed using only these two coins.

Therefore, the conditions for the values of the coins to satisfy in order for it to be safe to pay by always choosing the largest possible coin are:

1. The values must be arranged in ascending order from left to right, with each value being at least V(x-1) + (V(x-1) - V(x-2)).

2. The values must be relatively prime, with no common factors other than 1.

I hope this helps. Let me know if you have any further questions.