Overhang

ABSTRACT

How far off the edge of the table can we reach by stacking n identical blocks of length 1? A classical solution achieves an overhang of 1/2Hn, where Hn = Σⁿi=1 1/i ~ ln n is the n^th harmonic number, by stacking all the blocks one on top of another with the i^th block from the top displaced by 1/2i beyond the block below. This solution is widely believed to be optimal. We show that it is exponentially far from optimal by giving explicit constructions with an overhang of Ω(n^1/3). We also prove some upper bounds on the overhang that can be achieved. The stability of a given stack of blocks corresponds to the feasibility of a linear program and so can be efficiently determined.

REFERENCES

• 1: {A79} S. Ainley, Finely balanced, Mathematical Gazette 63 (1979) p. 272.
• 2: {C23} J. G. Coffin (New York City), Problem 3009, American Math. Monthly 30(2) (1923) p.76.
• 3: {J55} P. B. Johnson, Leaning Tower of Lire, Amer. J. Phys. 23 (1955) p. 240.
• 4: {HP64} J. E. Hearnshaw and M. S. Paterson, Problems Drive, Eureka (Journal of the Archimedeans, the Mathematics Society of the Univ. of Cambridge) 27 (1964) pp. 6--8 and 39--40. On-line at http://archim.org.uk/eureka/27/problems.html and ... /27/solutions.html
• 5: Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete Math, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 6: Uri Zwick, Jenga, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.243-246, January 06-08, 2002, San Francisco, California

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

General Terms:
Algorithms, Theory