An Optimal Algorithm for a Parallel Cutting Problem

Suppose we are given a set of sticks of various integer lengths, and that we have a knife that can cut as many as \(w\) sticks at a time. We wish to cut all the sticks up into pieces of unit length. By what procedure should the sticks be cut so that the total number of steps required is minimum? In this paper we show that the following natural algorithm is optimal: at each stage, choose the \(w\) longest sticks (or all sticks of length \(> 1\) if there are fewer than \(w\) of them) and cut them all in half (or as nearly in half as possible).