How far can a stack of n identical blocks be made to hang over the edge of a table? The question has a long history and the answer was widely believed to be of order log n. Recently, Paterson and Zwick constructed n-block stacks with overhangs of order n1/3, exponentially better than previously thought possible. We show here that order n1/3 is indeed best possible, resolving the long-standing overhang problem up to a constant factor.

2016 Dec 21