hang over

Hung Over?

A Martin Gardner Solution:

The drawing above illustrates the solution to a well-known puzzle. If you stack n bricks on a table, how far can you make them extend over the edge without toppling?

The answer given, for bricks of unit length, is one-half the nth harmonic number, the sum of the series 1/2 + 1/4 + 1/6 + 1/8 + … + 1/2n. Since this series diverges, the overhang can be as large as you please, given enough bricks (and a strong enough table).

The overhang for the harmonic stack is approximately equal to 1/2 ln n; it turns out other stacks achieve an overhang on the order of the cube root of n. This is an enormous improvement. For a million bricks, the harmonic stack can’t get beyond 13.8 bricklengths, whereas the cube-root stack extends 100 bricklengths beyond the edge.

There is reasonably new mathematical analysis showing exactly how large the overhang can be. Last year Mike Paterson of the University of Warwick and Uri Zwick of Tel Aviv University presented a paper at SODA (the Symposium on Discrete Algorithms) giving optimal solutions for n up to 30, and showing that the asymptotic rate of growth is n1/3. Now Peterson and Zwick, along with Yuval Peres (Berkeley), Mikkel Thorup (AT&T Labs) and Peter Winkler (Dartmouth) have proved that order n1/3 is the best that can achieved.

It can be shown that any n-block stack with an overhang of at least 6n1/3 is unbalanced, and must hence collapse. Thus we conclude that the maximum overhang with n blocks is of order n1/3.

Links to some more meaty research available at bit-player.org, a 2006 paper from Paterson-Zwick and from The American Mathematical Monthly.