Chris Lamb

Optimal solution for the block stacking problem found


I attended an interesting seminar on the block stacking problem today given by Professor Mike Paterson of the University of Warwick.

Like all good problems, it can be stated simply: how far can a stack of *n* identical blocks be made to hang over the edge of a table?

The answer was widely believed to be of order log n (like the white shaded example above), but Mike Paterson and Uri Zwick previously constructed overhangs of order n^{1/3}.

In the seminar today, Paterson and his co-authors presented their proof that order *n^{1/3}* is indeed the upper bound possible, resolving a long-standing mathematical problem. Professor Paterson is an excellent orator, highly recommended.

Chris Lamb is a freelance software developer and the current Debian Project Leader. You can read other posts by me, see software I have written or read more about me. You can also follow me @lolamby.

Planets: ALUG UWCS Debian WUGLUG

Tuesday 9th October 2007

Four comments