An optimal algorithm for a parallel cutting problem. (Q2715973)

Several sticks of celery with various integer lengths are to be cut into pieces of unit length by a knife that can cut at most \(w\) sticks at a time. What is the minimum number of cuts to do it and by what procedure it can be achieved? The authors prove that the following algorithm is optimal: at each stage cut the \(w\) longest sticks (or all sticks longer than 1 if there are fewer than \(w\) of them) in half or as nearly in half as possible. Example: \(w=3\) and the sticks are \(9,6\). One obtains \(5,4,3^2\) by cut one, \(3^2,2^4,1\) by cut two, \(2^5,1^5\) by cut three, \(2^2, 1^{11}\) by cut four, and \(1^{15}\) by cut five.