Hi all,

Can someone please provide the proof of the greedy step in the “Shifting Spoons” problem in the January Lunchtime. The greedy step seems to be intuitive here but I came across many problems where my greedy intuition was wrong. If anyone of you has come up with a proper mathematical proof, I will be very grateful if you can post the proof itself or an outline of the proof.

I’m not sure but I’ll try. If you find any mistake please tell.

At any stage, let’s say the value at first index is A and there are two values x and y (assume A<x<y). Now if want to add some value to the first index, we’ll pick the x and not y because y>A and there’s no way to reduce y. On the other hand, we can pick x, add to x-A to y and add A to A.

Also, let’s say there are 3 values x<y<z, now the question arises should the residual x-A be added to y or z. Adding to y is more beneficial because ideally we want A to be as greater as possible and other values to be as less as possible.

Also, to make 2^{nd} argument clear, here’s an example-

Say, A=3, x=5, y=5, z=11

If we add the residual to z, array becomes- 6, 0, 5,13 and in next iteration it becomes- 11, 0, 0, 13 and we can’t do anything here.

If we add the residual to y, array becomes- 6, 0, 7,11 and in next iteration it becomes- 12, 0, 0, 12 and can now add z to A and finally the array would become- 24,0,0,0.

Thanks for the help. I think you might need to replace **A-x** with **x-A**. I was actually looking for a more mathematical argument.

oops

Also, let’s say there are 33 values x<y<z,x<y<z, now the question arises should the residual x-Ax−A be added to yy or zz. Adding to yy is more beneficial because ideally we want AA to be as greater as possible and other values to be as less as possible.

This is the same intuitive reason i was thinking . However is their better mathematical prove ? @chenreddy did you found the proof ?

No, I didn’t find any rigorous mathematical proof. Currently, I am waiting for the editorial.

One more intuitive way i see is : Whenever we use two other piles say a<x<y where a is size of current pile , x and y are sizes of other two piles .We are shifting some amount of pile to the right side i.e 2*a , 0 , y+x-a . The larger number we choose , more amount of pile will accumulate on right side and thus that would be bad .

Though it’s not an mathematical proof.

This was exactly my intuition when I solved the problem. Hope the editorial will be out soon.