The Overhang Problem (2007) [pdf] | Hacker News Reader

The Overhang Problem (2007) [pdf]

math.dartmouth.edu

77 pointsf5ve16 comments

"How far can a stack of n identical blocks be made to hang over the edge of a table? The question has a long history and the answer was widely believed to be of order logn. Recently, Paterson and Zwick constructed n-block stacks with overhangs of order n^1/3 , exponentially better than previously thought possible. We show here that order n^1/3 is indeed best possible, resolving the long-standing overhang problem up to a constant factor."

(from intro)

Thank you from a mobile browser user!

Imagine being this author's parents at parties. "Yes, our son is a Computer Scientist. No, not the well-paid kind, the kind that solves problems. No, not that sort of problem; the ones like how many bricks it takes to make a wall sturdy. No, not a regular wall; a curved one. I don't know who wants a curved brick wall. Yes, I suppose he could just use rebar and mortar."

https://en.wikipedia.org/wiki/Mike_Paterson

I'm sure they could barely contain their shame. The man was a computer scientist before anyone bothered to string those two words together. He was literally a pioneer in the field. Or did you mean to denigrate generally all people who pursue their passion at their own expense?

That's cool. At some point, he was an awkward nerd who wouldn't stop talking about his dissertation. And no matter how many Turing Awards you win, your parents will still never understand what you do.

Just discovered this -- it contains the optimal constructions for up to N=20. They don't prove optimality but they do claim it.

https://www.maa.org/sites/default/files/pdf/upload_library/2...

These diagrams remind me of Lemmings and the builders that would build staircases over gaps you needed to cross.

It mentioned that the harmonic stacks arise from the restriction that the blocks should be stacked in one-on-one fashion. A related restriction might be that the blocks must be stacked one-by-one, i.e. each additional block must maintain balanced state.

I think trying to reproduce some of the diagrams with physical blocks would be difficult unless multiple blocks are placed at the same time.

The diagrams shown might be possible with that restriction if we allow "Jenga-like" moves: first, create a single vertical stack with the full height. Then, to widen a row with an extra tile, push the row exactly half a tile length to the left, and slide the new tile into the gap. (Since the tiles are frictionless, this would be much easier than real Jenga!) At every point, the stack should be balanced, even if it is not stable. Continue widening individual rows until the final pattern has been generated.

Intuitively, it looks like there should be a valid sequence of row widenings that generates the "brick-wall" stacks, though I am not 100% certain. Assuming there is, the next question would be whether asymmetric patterns such as that "oil-lamp" stacks can be generated, or whether in general the optimal pattern can always be generated.

> I think trying to reproduce some of the diagrams with physical blocks would be difficult unless multiple blocks are placed at the same time.

Might be easier to build the entire stack on its side and lift the entire stack using a large flat board. I'm too dumb to figure out if the weight loading from the top blocks during the rotation/lift would balance the forces pulling the ends out. At worse some pressure on the top would be needed.

It looks like https://www.maa.org/sites/default/files/pdf/upload_library/2... (linked by f5ve) has a partial answer to this question, near Figure 18:

> Can parabolic d-stacks be built incrementally by laying one brick at a time? The answer is no, as the bottom three rows of a parabolic stack form an unbalanced inverted 3-triangle. The inverted 3-triangle remains unbalanced when the first block of the fourth row is laid down. Furthermore, the bottom six rows, on their own, are also not balanced. These, however, are the only obstacles to an incremental row-by-row and block-by-block construction of parabolic stacks and they can be overcome by the modified parabolic stacks shown in Figure 18. We simply omit the lowest block and move the whole stack half a block length to the left. The bricks can now be laid row by row, going in each row from the center outward, alternating between the left and right sides, with the left side, which is over the table, taking precedence. The numbers in Figure 18 indicate the order in which the blocks are laid. Thus, unlike with harmonic stacks, it is possible to construct an arbitrarily large overhang using sufficiently many blocks, without knowing the desired overhang in advance.

arxiv link, since the Dartmouth math website is having a bad evening: https://arxiv.org/pdf/0707.0093.pdf

I often use this example when teaching calculus: https://youtu.be/BjmypdFCl-Q

So some scientists get to play with jenga on taxpayers' dime and students' tuition fee.

(I'm not angry, I'm envious.)

I wonder how close the historical examples come to the 20 or 30 block 'ideal'?

I came across this paper while I was looking for a compilation of constructions (especially the current record-holders), but I wasn't able to find one.

If anyone has seen such a thing please do post.

Reply on news.ycombinator.com