Odd Coins

So, apparently I just stop blogging when I have a semi-academic job, but don't have an office to go with it. Anyway, its about time for the solution to the coin puzzle from last time.

So, I suspect that somebody who works with the Fibonacci numbers alot will not really have much of a problem with this puzzle, there are a reasonable number of relationships the Fibonacci numbers obey that make the puzzle quite straightforward. First of all, I will give my definition of the Fibonacci numbers for the purpose of this puzzle:

f₁=1
f₂=2
f_k=f_k-1+f_k-2

I call this "my definition for the purpose of this puzzle" because nobody would ever normally start the Fibonacci numbers off with 1 and 2, 1 and 1 is most common, and 0 and 1 sometimes, but 1 and 2 is being chosen for this so that there are no repeats in the sequence {f_k} for k>0.

Next, I will derive an identity that will be needed for the solution:

2f_k=f_k+f_k-1+f_k-2
=f_k+1+f_k-2

A short derivation, but an important one.

Alright, now suppose the set of Fibonacci numbers is not a greedy set. Then there is a number C such that C can be expressed as a sum of K Fibonacci numbers {f_i1,f_i2,...f_iK} and the greedy algorithm uses at least K+1 such numbers. We will assume that C is chosen to be the smallest such number (if any exist, there must be a smallest one).

Naturally C is not one of the f_n, so let M be the largest number such that f_M<C. I claim that f_M is not in the list {f_i1,f_i2,...f_iK}. If it were, then the greedy algorithm would use the coin f_M and then optimize C-f_M. However, the list {f_i1,f_i2,...f_iK} adds to C and so if it contains f_M then C-f_M can be expressed using K-1 Fibonacci numbers, but the greedy algorithm would be able to optimize this, as C was the smallest counterexample.

Alright, so we have proven that the list {f_i1,f_i2,...f_iK} does not contain f_M. It is also obvious that it does not contain two consecutive Fibonacci numbers (if it did, we could make it more efficient). Finally, it can be made to not contain the same number twice, for if it did we could use our earlier identity to replace 2f_k with f_k+1 and f_k-2. I claim that a list of Fibonacci numbers f_j with J less than M with no consecutive numbers and no repeats cannot add to larger than f_M.

This can be proven as follows:

f_M=f_M-1+f_M-2
=f_M-1+f_M-3+f_M-4
=f_M-1+f_M-3+f_M-5+f_M-6

Continue on this logic, until you get down to f₁. We see that our list {f_i1,f_i2,...f_iK} cannot add to larger than f_M, but C was larger than f_M, so we have a contradiction, proving there is no smallest counterexample.

Thats all I got for now, I might post the full solution to the greedy sets of the form {1,a,b} next time, or I might just move on to a new puzzle, we will see.