Maximum overhang, optimum reward

Mar 04, 2011 By Janie Chang, Microsoft Research
The key to the classic problem uses the harmonic series of 1 + 1/ 2 + 1/ 3 + 1/ 4 … sums logarithmically to infinity to create a "harmonic" stack of n bricks which extend out approximately 1/2 log n.

Yuval Peres, principal researcher at Microsoft Research Redmond and manager of the Theory Group, always advocates both healthy skepticism and an open mind when it comes to problem solving. Even so, Peres was pleasantly surprised when a paper he co-authored won the prestigious David P. Robbins Prize from the Mathematics Association of America (MAA) for taking a completely new approach to a problem mathematicians had considered solved for decades.

Maximum Overhang—by Mike Paterson of the University of Warwick, Peres, Mikkel Thorup of AT&T Labs, Peter Winkler of Dartmouth College, and Uri Zwick of Tel Aviv University—builds on a paper titled Overhang, by Paterson and Zwick, the other paper cited in the prize. Together, the papers revisit a classic problem in mathematics: how to stack blocks on a table to achieve the maximum possible overhang—the farthest horizontal distance from the edge of the table.

“Like most people,” Peres recalls, “I had thought it seemed sensible to stack just one block at each level, which leads to the classical solution. I did not think of other possibilities. It’s good to retain some healthy skepticism of accepted wisdom.”

The David P. Robbins Prize is awarded for novel research in algebra, combinatorics, or discrete mathematics. The winning paper must be on a topic that is broadly accessible, written in a way that provides a simple statement of the problem and with clear exposition of the work. It certainly helped that the maximum-overhang problem has been a source of fascination for more than 150 years.

“Initially, it's surprising,” Peres says, “that it is possible at all to get farther than one block of overhang away from the edge of the table without any glue. Once one finds the classical solution, related to the harmonic series, it seems so beautiful and satisfying. It seems counterintuitive that one could do much better—that’s one source of fascination.”

A classic stack of 30 blocks (in orange) compared to the same number of blocks configured as a jagged wall (in gray) held stable by counterweights (in blue).

The topic fits into a general theme of crucial importance at Microsoft Research: constrained optimization.

“Optimization problems occur repeatedly in applications,” Peres says. “Scheduling jobs to different machines to minimize waiting times, deciding how frequently to crawl different websites when refreshing a search-engine index, setting up a network that will connect a set of processors at minimal cost—these can all be recast as optimization problems. Thus, developing new tools and insights pertinent to optimization is a key concern in the Theory Group at Research.”

The prize-winning papers offer a different approach, first, by stacking blocks to resemble a badly built wall, with holes, jagged edges, and a solid stack that acts as a counterweight. This extends the overhang beyond what the classic stack can achieve using the same number of blocks.

Then, to push results even farther out, the team sought a solution that optimized for a large number of blocks and devised a radical shape that yielded exponentially better results than the classic approach.

It was Zwick who then noticed a connection between the block-stacking problem and “random walk,” a fundamental tool used in areas of computer science such as web algorithms, distributed networks, and theory.

“Since I have worked on many problems involving random walks,” Peres says, “he approached me to help expand on the work. The principles of statics allowed us, together with our co-authors, to relate the overhang problem to the following, seemingly unrelated problem: Starting with a unit of mass at the origin, how many moves does it take to move half the mass to distance n, where in each move a node k between -n and n is chosen and the mass at k is split evenly between k-1 and k+1. It is easy to see that order n3 moves suffice, and a key step of the Maximum Overhang paper was to show that this number of moves is also necessary.”

In its citation, the MAA applauds the researchers for presenting both problem and arguments in a manner accessible even to math undergraduates, despite the inherently complex mathematics of the solution. For Peres, this criterion for the award is significant.

“It’s always great to get recognition,” he says. “But this award, besides being about mathematics, is also about exposition. As mathematicians, I think it is very important that we think more often about outreach and connecting to other people with different interests and motivations, to share our excitement and love of mathematics.”

The papers’ many illustrations are effective in communicating the work, a strategy familiar to Peres, whose webpage features beautiful, computer-generated images of mathematical constructs, courtesy of talented colleagues.

An "oil lamp" stack, whose results astonished even the researchers.

“I think images and simulations can play a major role in motivating mathematical research,” he says. “Those images hold an intrinsic beauty for both mathematicians and outsiders. You often hear about the beauty of mathematics, and, for me, some of that beauty is due to the unexpected patterns you find. Their mechanism gives no indication of why these patterns happen, so a lot of the math we do tries to explain the patterns. So far, the patterns are winning, because we can only explain a small part of what we see in the images. We are still very much challenged by them.”

The ongoing challenge of his research is one of the things Peres relishes most in his life.

“I enjoy cracking a hard problem,” he says, “preferably by bringing in perspectives from unexpected areas. I also love mentoring talented students, helping them become mathematicians. Best of all is when I can combine both these endeavors.”

He admits that he enjoys work so much he doesn’t spend enough time on hobbies such as hiking and swimming. Rather ruefully, he recalls overhearing his son, 6 at the time, asking a friend: “Do you have a religion? You know, a religion, like Jewish, or Christian, or Mathematics?”

“My wife would take our sons to synagogue on Saturday mornings,” he explains. “I used the time to go to the office and think about math. So he must have figured that whatever you choose to do on your Saturday mornings, that’s your religion.”

The proof in Maximum Overhang uses ideas from random walks: Start with mass 1 at the origin. How many mass-balanced splits are needed to get half the mass to distance d?

Peres has regarded the world through the lens of mathematics from a young age. His paternal grandfather, Julius Posener, was a physicist, educator, and violinist who took the time to discuss with Peres the mathematics of music and how mathematicians of the Renaissance solved cubic and quartic equations.

“I was 12,” Peres recalls, “when he explained to me the geometry of complex numbers. I remember emerging into the sunlight and thinking that now I had a new way to understand the world—and it would never look the same again. At 13, I inherited my grandfather’s scientific books, many of them probability books, and by 14, I was pretty sure I wanted to be a .”

Equally crucial to the way Peres regards his work has been the influence of his maternal grandmother.

“Though not formally educated in math,” Peres says, “she was a calculating whiz. Her favorite saying was, ‘Why should I be surprised when I can simply disbelieve?’ She taught me the virtues of skepticism—and also of keeping an open mind.”

The work on the maximum-overhang problem epitomizes a situation in which skepticism and an open mind have challenged conventional wisdom and have delivered new results.

“The point is that we need to be willing to re-examine some natural assumptions,” Peres says. “It seems so natural to stack each block one level above the other. Why would you place several blocks at the same level? If you follow that natural assumption, then yes, the classic solution is the best one.

“But if you think outside the box, you can obtain unexpected insights. I think the lesson, the whole philosophical point, is about the nature of problem solving. It’s about finding and re-examining the hidden assumptions we make before we even start to think seriously about a problem.”

Explore further: F1000Research brings static research figures to life

Source: Microsoft Corporation

4.4 /5 (14 votes)
add to favorites email to friend print save as pdf

Related Stories

Famous 40-Year-Old Math Problem Solved

Nov 23, 2005

For some, spending more than three years working to solve a more than 40-year-old math problem sounds like a nightmare. For University of Missouri-Columbia mathematics professor Steve Hofmann, solving a problem posed by one ...

YouTube chief says ad sales soaring

Dec 08, 2009

(AP) -- YouTube's chief executive says ad sales are soaring, but there is still no word on whether the popular video-sharing site is making money.

Fundamental algorithm gets first improvement in 10 years

Sep 27, 2010

The maximum-flow problem, or max flow, is one of the most basic problems in computer science: First solved during preparations for the Berlin airlift, it’s a component of many logistical problems and a staple ...

Recommended for you

F1000Research brings static research figures to life

7 hours ago

F1000Research today published new research from Bjorn Brembs, professor of neurogenetics at the Institute of Zoology, Universitaet Regensburg, in Germany, with a proof-of-concept figure allowing readers and reviewers to run ...

How science can beat the flawed metric that rules it

9 hours ago

In order to improve something, we need to be able to measure its quality. This is true in public policy, in commercial industries, and also in science. Like other fields, science has a growing need for quantitative ...

User comments : 20

Adjust slider to filter visible comments by rank

Display comments: newest first

Quantum_Conundrum
1.3 / 5 (15) Mar 04, 2011
This seems almost ridiculous that this is considered "research".

You mean to tell me that "mathematicians" have been working on this problem for centuries or something?

This is something I figured out at like a few years old. I wasn't aware this was an un-solved problem...

I'm sure any carpenter or brick layer, or even a librarian with a stack of books, would realize this immediately.

Is this some sort of joke?

This is like first grade or something, even common knowledge, or so I thought.

It's ridiculous that this is somehow "noteworthy"...
Quantum_Conundrum
1.4 / 5 (11) Mar 04, 2011
You can very easily pass the harmonic solution's maximum within just a few layers, just by making rough "guesstimates" with a stack of books, such as encyclopedias.

Even just guessing, with no measuring instrument, you can beat the harmonic using fewer blocks.

Just guessing, I was able to get an overhang exceeding 1.25 block widths on the third layer, with just 5 blocks total.
that_guy
1.4 / 5 (9) Mar 04, 2011
I think that this kind of theory and thinking can be helpful for different types of equations,...but a smart 5 year old could figure out aspects of this...I mean seriously, did mathematicians really box themselves in so far that they ignored basic physics...weight and counterweight...I don't know, it just seems incredibly stupid that mathematicians couldn't find a better way until now...I want to think that maybe this is a semantic issue, because I can't believe that that many people would seriously tackle this problem and not come out with a better solution if there hadn't been rules against it in the first place.
Quantum_Conundrum
1 / 5 (8) Mar 04, 2011
I'm not convinced his mathematical solution is the best either.
Quantum_Conundrum
1 / 5 (7) Mar 04, 2011
Yeah, this is wrong and ridiculous.

I can beat his overhang of 10 using far fewer blocks, and can prove it mathematically.

Just by making a symetrical inverted "triangular stack" with no gaps, and letting an overhang which is arbitrarily close to 1/2 on the first block (0.499...), and then every block thereafter is placed precisely offset by half from the center of that block, then we use two additional blocks on an N+1 layer to hold the last pieces of the previous layer.

Then the overhang, O, after N layers, when N is greater than 1, is:

O = 0.5(N - 1) + 0.499...

The weight after N layers is:

W = (N*(N+1)/2) + 2

So to beat an overhang of 10, implying 10.49r, we have:

10.49r = 0.5(N-1) + 0.49r

10 = 0.5(N-1)

20 = N-1

21 = N

W = ((21*22)/2) + 2

W = 21*11 + 2

W = 233

N = 21

O = 10.49r

Which EASILY destroys the PHD guy's allegedly optimized solution, using about 1/4th as many blocks...
Quantum_Conundrum
1 / 5 (6) Mar 04, 2011
So when do I get a prestigious P. Robbins Prize?

What is the dollar value of it? I would like to claim it now, thanks. I beat him by a factor of 4 inside a few minutes.
J-n
5 / 5 (1) Mar 04, 2011
I'm having a difficult time picturing your solution would you care to draw or even better take a picture of your design?
mike352
4.3 / 5 (6) Mar 04, 2011
If you looked at the paper itself, following the link in the beginning, you'd see that the authors consider the inverted triangle idea and show how it's unstable. They consider other simple ideas as well. You might want to check it out, after all, it's supposed to be very readable according to the article.
Quantum_Conundrum
1 / 5 (7) Mar 04, 2011
I'm having a difficult time picturing your solution would you care to draw or even better take a picture of your design?


Just make a perfectly symetrical pyramid and turn it upside down, with center of gravity very close to the edge of the table, but not passed it.

so:

.
.
.
**********
*********
********
*******
******
*****
****
***
**
*

Here, each star represents half of a blok width, and the other half of the structure is off the page. This is because the site won't preserve the formatting to put it all on here.
Quantum_Conundrum
1 / 5 (8) Mar 04, 2011
If you looked at the paper itself, following the link in the beginning, you'd see that the authors consider the inverted triangle idea and show how it's unstable. They consider other simple ideas as well. You might want to check it out, after all, it's supposed to be very readable according to the article.


It isn't unstable.

It's perfectly symetrical, so it cannot be unstable.

I did it with a stack of books already and proved it works in the real world.

Even if you are concerned with instability, you can add a few additional blocks over the center of gravity to ensure it doesn't fall apart.

Even if you made a diamond to guarantee the outter parts don't fall off, you would still beat his solution by a factor of 2...
Quantum_Conundrum
1 / 5 (7) Mar 04, 2011
Here's another point.

His solution cannot be the best anyway, because when you look at the pictures, every several layers has at least one or two blocks which are hanging over in the "overhang" direction, and yet end up not contributing to the overall overhang width, which therefore means their weight being out on the overhang must be a waste.

In some cases, layers do not even go as far out as previous layers, which must also be a waste, because you are essentially "starting over" from a smaller width. This MUST be less efficient than a pyramid or diamond which always increases in width or stays the same.
J-n
not rated yet Mar 04, 2011
"I did it with a stack of books already and proved it works in the real world."

I know it'd be a hassle, but would you be able to take a picture and upload it to imageshack.us or wherever so we can see your accomplishments?
CrossMan
5 / 5 (5) Mar 04, 2011
Unfortunately, the inverted triangle solution does not work for more than two layers: at three layers, it becomes unbalanced (despite the symmetry). The rightmost brick on the third layer exerts more torque on the rightmost brick on the second layer than does the middle brick on the third layer (it's split between the two middle bricks). The same thing happens on the left side, and the triangle will collapse. This is pointed out on pages 5-6 (and Fig. 7) in their paper, arxiv:0710.2357

Similarly, the authors point out that diamonds over nine layers are similarly unstable.

Finally, it may be possible to build stable inverted triangles using bricks (or other material objects) due to friction (which contributes torque). The bricks in the paper are frictionless.
fmfbrestel
5 / 5 (8) Mar 04, 2011
Sorry QC, I dont know why your in such a mood today, but your wrong. Very wrong. It doesnt matter how angry and indignant you sound, your still wrong. Inverted pyramids and diamonds are not stable. Even with significant friction, going beyond 10 layers will be neigh impossible without glue. But CrossMan is exactly right, these blocks are frictionless. I can already hear your retort "but real blocks have friction!!!!!!" but it doesnt matter, were not talking about building a structure, we are talking optimization strategies within a given set of constraints. Friction = 0 is one of the constraints so go complain somewhere else.
fmfbrestel
5 / 5 (4) Mar 04, 2011
I mean, so long as using friction to cheat is ok, give me some velcro blocks and i'll build you something with a crazy overhang. friction is all that holds velcro together.
fmfbrestel
5 / 5 (2) Mar 04, 2011
And my velcro block overhang will be perfectly symmetrical to, since you seem to think symmetry validates the balance.
ab3a
5 / 5 (3) Mar 04, 2011
The blocks are of the same length and friction is considered to be negligible. Please, everybody, this problem is of a more subtle nature than most people realize. It is a popular problem among civil engineers.
epsi00
not rated yet Mar 05, 2011
"I did it with a stack of books already and proved it works in the real world."

I know it'd be a hassle, but would you be able to take a picture and upload it to imageshack.us or wherever so we can see your accomplishments?


J-n, you mean you want him to prove, with a picture, that his solution is not a solution. I don't think he is that stupid. He likes to speculate a lot and then pull a no show when it counts.
Vendicar_Decarian
not rated yet Mar 07, 2011
"I can beat his overhang of 10 using far fewer blocks, and can prove it mathematically." - Quantum KookFart

You seem to be putting a lot of effort into your failed analysis.

The problem must be beyond your comprehension.
J-n
not rated yet Mar 07, 2011

J-n, you mean you want him to prove, with a picture, that his solution is not a solution. I don't think he is that stupid. He likes to speculate a lot and then pull a no show when it counts.


Well he DID say he built one... lol... which i'm sure he didn't. Ever since his overtly derogatory (read: homophobic, racist) comments in another post i've been unsure if anything he's ever said on Physorg means anything more than those ads i keep reporting.