Greedy Coins

Time for a new puzzle. As seems to be the constant state these days, I am running out of puzzles and as such I am digging up all the weird ones I remember. Actually, I rather enjoyed this one, but it is more mathematical than most of my puzzles. I first learned this one from Bart:

Consider the problem of making change for a certian amount of money, given a set of coins that you can select from. You have a target number x, and you wish to construct x by using elements from a set S (so S could be the set {1,5,10,25} for example). In particular we wish to reach the target number using a few coins as possible, so making 23 with 10+10+1+1+1 is considered more optimal than using 10+5+5+1+1+1. This is known as the change-making problem.

There are plenty of good solutions for the change-making problem, but let us consider a special style of solution, which is known as the "greedy algorithm". This algorithm is to always take the largest available coin that is smaller than your target number and the reduce the target number by that amount. As an example of this algorithm, lets try to make 28 is the set {1,5,10}, we first take 10, now we want to reach 18, so we take another 10, now we want to reach 8 so we take 5 and finally to get 3 we use 1 three times, thus the algorithm gives us the solution 10+10+5+1+1+1, which you can convince yourself is optimal for this case. For another example we can consider the set {1,4,5} and try to reach target number 8. The greedy algorithm gives us 5+1+1+1, but we can see that 4+4 is a better solution, so in this case the greedy algorithm does not give us the optimal solution.

With some sets of numbers, such as {1,5,10,25} the greedy algorithm will always give the optimal solution, but with others such as {1,4,5} it will not (lets not ask what happens if the number 1 is not in our coin set). With some sets, like reaching 4 with {1,2,3} the greedy algorithm gives an optimal solution, but not the only solution, so 4=1+3 but also 4=2+2. We will call a set of natural numbers "greedy" if the greedy algorithm always gives an optimal solution for the change-making problem.

Consider the set of numbers that occur in the Fibonacci sequence, call this set F. The puzzle is prove that F is a greedy set.

If you don't know what the Fibonacci sequence is then I am astounded that you are even reading this blog, but anyway, it should be pretty easy to look it up on the internets somewhere.

One can ask the much more general question of "classify all greedy sets", but that is actually really hard and if you can do that, I suggest you publish. You can try to solve out the classification of all greedy sets of the form {1,a,b} though, that actually has a somewhat nice answer.