Maximum OverhangMike Paterson∗Yuval Peres†Mikkel Thorup‡Peter Winkler§Uri Zwick¶February 1, 2008AbstractHow far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be of order logn. 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/3is indeed best possible, resolving the long-standing overhang problem up to a constant factor.1IntroductionThe problem of stacking n blocks on a table so as to achieve maximum overhang has a long history. It appears in physics and engineering textbooks from as early as the mid 19th century (see, e.g., [P1850],[W1855], [M1907]). The problem was apparently first brought to the attention of the mathematical com-munity in 1923 when J.G. Coffin posed it in the “Problems and Solutions” section of the American Math- ematical Monthly [C1923]; no solution was presented there.Figure 1: Optimal stacks with 3 and 4 blocks, compared to the corresponding harmonic stacks. The 4 block solution is from [A1979]. Like the harmonic stacks it can be made stable by minute displacements.The problem recurred from time to time over subsequent years, e.g., [S1953, S1954, S1955, J1955, GS1958, E1959, G1964, G1971, A1979, D1981, GKP1988, H2005], achieving much added notoriety from its appear-ance in 1964 in Martin Gardner’s “Mathematical Games” column of Scientific American [G1964, G1971].∗Department of Computer Science, University of Warwick, Coventry CV4 7AL, UK. E-mail: msp@dcs.warwick.ac.uk†Department of Statistics, University of California, Berkeley, California 94710, USA. E-mail: peres@stat.berkeley.edu‡AT&T Labs - Research, 180 Park Avenue, Florham Park, NJ 07932, USA. E-mail: mthorup@§Department of Mathematics, Dartmouth College, Hanover, NH 03755-3551, USA. E-mail: peter.winkler@dartmouth.edu¶School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel. E-mail: zwick@cs.tau.ac.il1arXiv:0707.0093v1 [math.HO] 1 Jul 2007blocks = 20 overhang = 2.32014blocks = 30 overhang = 2.70909Figure 2: Optimal stacks with 20 and 30 blocks from [PZ2006] with corresponding harmonic stacks in the background.Most of the references mentioned above describe the now classical harmonic stacks in which n unit-length blocks are placed one on top of the other, with the ithblock from the top extending by1 2ibeyond the block below it. The overhang achieved by such stacks is1 2Hn=1 2Pn i=11 i∼1 2lnn. The cases n = 3 and n = 4 are illustrated at the top of Figure 1 above, and the cases n = 20 and n = 30 are shown in the backgroundof Figure 2. Verifying that harmonic stacks are balanced and can be made stable (see definitions in the next section) by minute displacements is an easy exercise. (This is the form in which the problem appears in [P1850], [W1855], [M1907].) Harmonic stacks show that arbitrarily large overhangs can be achieved ifsufficiently many blocks are available. They have been used by countless teachers as an introduction to recurrence relations, the harmonic series and simple optimization problems (see, e.g., [GKP1988]).1.1How far can you go?Many readers of the above mentioned references were led to believe that1 2Hn(∼1 2lnn), the overhang achieved by harmonic stacks, is the maximum overhang that can be achieved using n blocks.This is indeed the case under the restriction, explicit or implicit in some of these references, that the blocks should be stacked in a one-on-one fashion, with each block resting on at most one other block. It has been known for some time, however, that larger overhangs may be obtained if the one-on-one restriction is lifted. Three blocks, for example, can easily be used to obtain an overhang of 1. Ainley [A1979] found that four blocks can be used to obtained an overhang of about 1.16789, as shown at the bottom right of Figure 1, and this is more than 10% larger than the overhang of the corresponding harmonic stack. Using computers, Paterson and Zwick [PZ2006] found the optimal stacks with a given limited number of blocks. Their solutions with 20 and 30 blocks are shown in Figure 2.Now what happens when n grows large? Can general stacks, not subject to the one-on-one restriction, improve upon the overhang achieved by the harmonic stacks by more than a constant factor, or is over- hang of order logn the best that can be achieved? In a recent cover article in the American Journal of Physics, Hall [H2005] observes that the addition of counterbalancing blocks to one-on-one stacks can dou- ble (asymptotically) the overhang obtainable by harmonic stacks. However, he then incorrectly concludes that no further improvement is possible, thus perpetuating the order logn “mythology”.Recently, however, Paterson and Zwick [PZ2006] discovered that the modest improvements gained for small values of n by using layers with multiple。