Overhang

How far off the edge of the table can we reach by stacking n identical blocks of length 1? A classical solution achieves an overhang of (1/2)H_n, where H_n=1/1+1/2+...+1/n is the n-th harmonic number. This solution is widely believed to be optimal. We show, however, that it is exponentially far from optimal by giving explicit constructions with an overhang of Omega(n^{1/3}). Together with Yuval Peres, Mikkel Thorup and Peter Winkler, we have recently shown that no larger overhangs are achievable.