Sum of minimum number of fibonacci numbers that add to N, Greedy Works, proof needed on optimality !!

Revision en1, by prac64, 2018-06-29 09:44:10

Hello Codeforces,

Recently I came across a problem where we have to output the minimum number of fibonacci terms needed to make up a number. Repeating the terms to make up the representation is allowed. The fibonacci sequence 1,2,3,5,8,13,21.. will be used for all cases.

I can explain better with an example, lets say N=6, then the answer is 2, you can use the numbers 1 and 5 to make 6, another combination is 3 3, which also gives the optimal answer 2. However in this question we only need the minimum number of terms, not what those terms are.

Other examples: input = 5 output = 1 input = 7 output = 2 input = 19 output = 3

I tried out some examples and even submitted the greedy algorithm on this problem, which is to keep subtracting the largest fibonacci number possible which still keeps the result non-negative, and adding 1 for each of those terms subtracted. A few blogs on the same topic give this algorithm for solving the problem, however no proof on correctness.

A quick wikipedia search yielded Zuckendorf theorem, which just proves uniqueness with non-adjacent terms, I was unable to extend it to greedy or minimum.

Does anyone have a proof on correctness(or a counter-case is welcome too :D ) ?

Thank You Codeforces!

Tags math, fibonacci, proof, greedy

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English prac64 2018-06-29 09:44:10 1388 Initial revision (published)