5 ms·

The Overhang Problem (2007) [pdf]

77 points by f5ve 3y ago

_a_a_a_ 3y ago
"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)
- yccs27 3y ago
  Thank you from a mobile browser user!
PlunderBunny 3y ago
I wonder how close the historical examples come to the 20 or 30 block 'ideal'?
- f5ve 3y ago
  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.
mav88 3y ago
These diagrams remind me of Lemmings and the builders that would build staircases over gaps you needed to cross.
jojobas 3y ago
So some scientists get to play with jenga on taxpayers' dime and students' tuition fee. (I'm not angry, I'm envious.)
stephencanon 3y ago
arxiv link, since the Dartmouth math website is having a bad evening: https://arxiv.org/pdf/0707.0093.pdf https://arxiv.org/pdf/0707.0093.pdf
kisonecat 3y ago
I often use this example when teaching calculus: https://youtu.be/BjmypdFCl-Q https://youtu.be/BjmypdFCl-Q
omoikane 3y ago
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.
- LegionMammal978 3y ago
  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.
- bentcorner 3y ago
  > 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.
- LegionMammal978 3y ago
  It looks like https://www.maa.org/sites/default/files/pdf/upload_library/22/Robbins/Patterson1.pdf 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.
f5ve 3y ago
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/22/Robbins/Patterson1.pdf https://www.maa.org/sites/default/files/pdf/upload_library/2...
trhr 3y ago
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."
- f5ve 3y ago
  https://en.wikipedia.org/wiki/Mike_Paterson 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?
  - trhr 3y ago
    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.

77 points by f5ve 3y ago

"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)

yccs27 3y ago
Thank you from a mobile browser user!

PlunderBunny 3y ago

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

f5ve 3y ago
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.

mav88 3y ago

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

jojobas 3y ago

So some scientists get to play with jenga on taxpayers' dime and students' tuition fee. (I'm not angry, I'm envious.)

stephencanon 3y ago

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

kisonecat 3y ago

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

omoikane 3y ago

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.

LegionMammal978 3y ago
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.
bentcorner 3y ago
> 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.
LegionMammal978 3y ago
It looks like https://www.maa.org/sites/default/files/pdf/upload_library/22/Robbins/Patterson1.pdf 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.

f5ve 3y ago

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/22/Robbins/Patterson1.pdf https://www.maa.org/sites/default/files/pdf/upload_library/2...

trhr 3y ago

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."

f5ve 3y ago
https://en.wikipedia.org/wiki/Mike_Paterson 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?
- trhr 3y ago
  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.