Greedy approach proof


#1

Could somebody please prove how greedy works properly in this question.


#2

The same way Dijkstra’s greedy algorithm works. An algorithm for finding the shortest paths between nodes in a graph. This problem is also about finding shortest path(minimum numbers).


#3

Proof by Zeckendorf’s Theorem


#4

How can you prove that the number of fibonacci numbers used will always be minimum if we are following Zeckendorf’s theorem


#5

Actually concept is quite simple and can be understood without thinking of complex proofs. First we will get all Fibonacci numbers less that A. Let they be a1, a2, a3, a4, …, an. Now, ‘an’ is the last element and is less than A. Greedy suggests we shall take it. Now suppose you didn’t take ‘an’. Now following things happens
Claim1: You can not choose consecutive index of fibonacci in optimal solution. Because if that was the case then we can take last consecutive pairs and replace them by the next index of 2, remove them from our optimal solution. For example if you took 1,1, 3,5,8 as optimal solution, so you can remove 5 and 8 and use 13.
Now you take non consecutive elements only.
Claim2: Summation of non consecutive elements will be less than A.
‘an’<A
But ‘an’ is not in our solution as we are taking case when we are not following greedy.
Max possible sum is ‘a(n-1) + a(n-3) + a(n-5)…’ .
Now I will prove ‘a(n-1) + a(n-3) + a(n-5)…’ <= an.
=> ’ a(n-3) + a(n-5)…’ <= a(n-2). ’ because ‘an’ = ‘a(n-1) + a(n-2)’
following above repeatedly we get to the equality. Hence proved.


#6

you forgot about repetitions, so 2 * a(n-1) >= a(n)

so continuing your proof
2a(i) = a(i) + a(i-1) + a(i-2) = a(i+1) + a(i-2)
=> the 2 representations with 2
a(n-1)+… and a(n)+a(n-3)+… are equivalent in terms of count of fibonacci numbers