January 28, 2009

Overhang

Suppose you want to pile identical bricks on the edge of a table so that the stack juts out as far as possible past the table's edge.

One solution is to pile the bricks one on top of the other, with each brick sticking out slightly farther than the one beneath it. Ideally, assuming vertical forces and no friction, the top brick juts out from the one below it by half its length, the second by a quarter, the third by a sixth, and so on. The nth brick from the top would overhang the one below it by 1/2n. The number of brick lengths by which the nth brick extends beyond the table edge is ½(1 + ½ + 1/3 + . . . 1/n)


Credit: Paterson and Zwick, American Mathematical Monthly

In principle, you can make the stack stick out as far as you want, but it could take a huge number of bricks to achieve the desired overhang.

Many people assume that this solution is optimal, but that’s true only if the bricks are stacked one on top of the other. What if more than one brick can lie atop another brick?

Mike Paterson of the University of Warwick and Uri Zwick of Tel Aviv University have now demonstrated that, when you allow such multiple stacking, you can get more overhang for the same number of bricks. They report their results in the article "Overhang," published in the January American Mathematical Monthly.

"Without this restriction, blocks can be used as counterweights, to balance other blocks," Paterson and Zwick write. "The problem then becomes vastly more interesting, and an exponentially larger overhang can be obtained."

The resulting optimal patterns for given numbers of bricks are fascinating—and somewhat unpredictable.


Optimal stacks for eight, nine, and ten bricks. The lightly shaded bricks in these stacks form the support set, while the darker bricks form the balancing set.

Paterson and Zwick used numerical methods to find the optimal stacks for up to 30 bricks. "While there seems to be a unique optimal placement of the blocks that belong to the support set of an optimal stack, there is usually a lot of freedom in the placementmof the balancing blocks," they remark.

Constructions of n bricks described as "parabolic," "vase," and "oil lamp" produce the best overhang, with each construction having an overhang of order n1/3.


A parabolic stack of 111 bricks produces an overhang of three bricks.

Paterson and Zwick, now joined by Yuval Peres of the University of California, Berkeley, Mikkel Thorup of AT&T Labs–Research, and Peter Winkler of Dartmouth College, describe additional findings on the stacking problem in their article "Maximum Overhang," to be published in the Monthly.

No comments: