Maximum overhang

ABSTRACT

How 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 log n. However, at SODA'06, Paterson and Zwick constructed n-block stacks with overhangs of order n^1/3. Here we complete the solution to the overhang problem, and answer Paterson and Zwick's primary open question, by showing that order n^1/3 is best possible. At the heart of the argument is a lemma (possibily of independent interest) showing that order d³ non-adaptive coinflips are needed to propel a discrete random walk on the number line to distance d.

We note that our result is not a mainstream algorithmic result, yet it is about the solution to a discrete optimization problem. Moreover, it illusrates how methods founded in theoretical computer science can be aplied to a problem that has puzzled some mathematicians and physicists for more than 150 years.

REFERENCES

• 1: {A1979} S. Ainley, Finely balanced, Mathematical Gazette 63 (1979), p. 272.
• 2: {C1923} J. G. Coffin, Problem 3009, American Math. Monthly 30(2) (1923), p. 76.
• 3: {D1981} J. E. Drummond, On stacking bricks to achieve a large overhang (Note 65.8)., Mathematical Gazette 65 (1981), pp. 40--42.
• 4: {E1959} L. Eisner, Leaning Tower of the Physical Review, American Journal of Physics 27 (1959), p. 121.
• 5: {G1964} M. Gardner, Mathematical games: Some paradoxes and puzzles involving infinite series and the concept of limit, Scientific American (Nov. 1964), pp. 126--133.
• 6: {G1971} M. Gardner, Martin Gardner's Sixth Book of Mathematical Games from Scientific American (W.H. Freeman, 1971), Chapter 17: Limits of Infinite Series, p. 167.
• 7: Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete Math, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 8: {GS1958} G. Gamow and M. Stern, Puzzle-Math (Viking, 1958), Building-Blocks, pp. 90--93.
• 9: {H2005} J. F. Hall, Fun with stacking blocks, American Journal of Physics 73(12) (2005), pp. 1107--1116.
• 10: {J1955} P. B. Johnson, Leaning Tower of Lire, American Journal of Physics 23(4) (1955), p. 240.
• 11: {JP2001} C. P. Jargodzki and F. Potter, Mad About Physics: Braintwisters, Paradoxes, and Curiosities (Wiley, 2001), Challenge 271: A staircase to infinity, p. 246.
• 12: {M1907} G. M. Minchin, (1907) A Treatise on Statics: With Applications to Physics, 6th Ed., (Clarendon, Oxford, 1907) p. 341.
• 13: {PPTWZ2007} M. Paterson, Y. Peres, M. Thorup, P. Winkler and U. Zwick, Maximum overhang, arXiv:0707.0093 {math.HO}.
• 14: Mike Paterson , Uri Zwick, Overhang, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.231-240, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109584]
• 15: {PZ2007} M. Paterson and U. Zwick, Overhang, arXiv:0710.2357 {math.HO}. To appear in American Mathematical Monthly.
• 16: {P1850>} J. B. Phear (1850) Elementary Mechanics (MacMillan, Cambridge, 1850), pp. 140--141.
• 17: {P1947} R. L. Plackett, Limits of the Ratio of Mean Range to Standard Deviation, Biometrika 34:1/2. (1947), pp. 120--122.
• 18: {S1953} R. T. Sharp, Problem 52, Pi Mu Epsilon Journal 1 (1953), p. 322.
• 19: {S1954} R. T. Sharp, Problem 52, Pi Mu Epsilon Journal 2 (1954), p. 411.
• 20: {S1955} R. Sutton, A Problem of Balancing, American Journal of Physics 23(8) (1955), p. 547.
• 21: {W1855} W. Walton, A Collection of Problems in Illustration of the Principles of Theoretical Mechanics, 2nd Ed., (Deighton, Bell, and Co., Cambridge, 1855) p. 183.