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:

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 {fk} for k>0.

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

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 {fi1,fi2,...fiK} 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 fn, so let M be the largest number such that fM<C. I claim that fM is not in the list {fi1,fi2,...fiK}. If it were, then the greedy algorithm would use the coin fM and then optimize C-fM. However, the list {fi1,fi2,...fiK} adds to C and so if it contains fM then C-fM 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 {fi1,fi2,...fiK} does not contain fM. 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 2fk with fk+1 and fk-2. I claim that a list of Fibonacci numbers fj with J less than M with no consecutive numbers and no repeats cannot add to larger than fM.

This can be proven as follows:

Continue on this logic, until you get down to f1. We see that our list {fi1,fi2,...fiK} cannot add to larger than fM, but C was larger than fM, 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: