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

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

“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.”

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 mathematician.”

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:**
Famous 40-Year-Old Math Problem Solved

## Quantum_Conundrum

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

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

## Quantum_Conundrum

## Quantum_Conundrum

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

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

## mike352

## Quantum_Conundrum

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

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

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

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

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

## fmfbrestel

## fmfbrestel

## ab3a

## epsi00

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

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

The problem must be beyond your comprehension.

## J-n

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.