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}=1

f_{2}=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

_{1}. 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.

## No comments:

Post a Comment