# Overhang

Award: Lester R. Ford

Year of Award: 2010

Publication Information: The American Mathematical Monthly, vol. 116, no. 1, January 2009, pp. 19-44.

Summary: The problem of how far off the edge of a table one can reach by stacking n identical, friction free, blocks of unit length first appeared in the Monthly in 1923 and has been considered elsewhere many times. Conventional wisdom says that the optimal solution is asymptotic to log (n)/2 as n increases, and is obtained by the harmonic stacking. This result is correct under the implicit added hypothesis that each block can rest on only one block below it. The authors investigate this problem without the one-on-one restriction.

About the Authors: (From the Prizes and Awards booklet, MathFest 2010)

Mike Paterson is emeritus professor of Computer Science at Warwick University in the UK and is a Fellow of the Royal Society. His BSc and PhD in mathematics are from Cambridge University. Paterson started his teaching career at Massachusetts Institute of Technology and continued at Warwick where he has remained for nearly forty years. He was president of the Trinity Mathematical Society as a student, and of the European Association for Theoretical Computer Science somewhat later. He co-invented Sprouts with John Conway and received the Dijkstra Award in Distributed Computing. His interests have been mainly in algorithmic complexity, beginning from his early years at MIT, but have extended broadly within that area to include distributed algorithms, algorithmic game theory and, of course, the work recognised by this award.

Uri Zwick is a professor of Computer Science at Tel Aviv University, Israel. He received his BSc in Computer Science from the Technion, Israel Institute of Technology, and his MSc and PhD in Computer Science from Tel Aviv University. His main research interests are: algorithms and complexity, combinatorial optimization, mathematical games, and recreational mathematics. Zwick spent two years as a PostDoc at Warwick University after completing his PhD and has been collaborating with Mike Paterson ever since.

MSC Codes:
97Mxx
Author(s):
Mike Paterson (Warwick University ) and Uri Zwick (Tel Aviv University)
Flag for Digital Object Identifier:
Publication Date:
Friday, August 13, 2010
Publish Page:
Summary:

The problem of how far off the edge of a table one can reach by stacking n identical, friction free, blocks of unit length first appeared in the Monthly in 1923 and has been considered elsewhere many times. Conventional wisdom says that the optimal solution is asymptotic to $$\log n/2$$ as $$n$$ increases, and is obtained by the harmonic stacking. This result is correct under the implicit added hypothesis that each block can rest on only one block below it. The authors investigate this problem without the one-on-one restriction.