Maximum overhang problem

A recent talk at the Combinatorics Study Group featured Mikkel Thorup, who was visiting the Centre from AT&T Labs-Research. He spoke about the solution of the 150-year old “Maximum Overhang Problem”, which asks: How far can a stack of n identical blocks be made to hang over the edge of a table? The most natural attempt leads to a “harmonic” stack in which the ith block adds an overhang of 1/2i, so the total overhang has order \log n. This was widely believed to be the correct order of magnitude, to the extent that there was even a physics “proof” purporting to show this.

However, Paterson and Zwick recently showed that in fact an overhang of order n^{1/3} can be achieved, which is exponentially larger! As Mikkel said in his talk, the key idea is to realise that a wall is much more effectively counterbalanced than a bridge. This may sound obvious in retrospect, but sometimes a breakthrough just needs a simple idea in an unexpected context. So what is the true order of magnitude? It turns out that n^{1/3} is the correct answer – this was proved by Paterson, Peres, Thorup, Winkler and Zwick.

Mikkel left us with a nice open problem, which would reduce the 3d problem to the 2d problem, but is also independently interesting. Is it possible to  create a stable stack of frictionless homogeneous 3d blocks in which there are horizontal forces? For example, you might think that a circle of dominoes can lean against each other in a stable fashion, but apparently it will fall over (very slowly). Mikkel conjectures that no such stack exists. However, if this is true, the proof must use the “rectangular” nature of blocks, as such stacks do exist using triangles.

I’ll add this to the problem page, where anyone interested in thinking about it collaboratively can start a comment thread.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s