I nonetheless bear in mind the film evening after I first watched Good Will Searching with my mother. Matt Damon performed a janitor on the Massachusetts Institute of Know-how. Whereas mopping the hallways, he walked previous a blackboard with a complicated math downside written on it. He stopped and began fixing the issue. I watched, mesmerized, as he created seemingly illegible constructions of dots and features—till all of the sudden a math professor got here out of a lecture corridor and chased him away.
The viewers was beforehand instructed that that downside was meant to be extremely troublesome, taking years of knowledgeable pondering to resolve, but it was shortly labored out by Damon’s insightful janitor in simply moments. On the time, I used to be fascinated by the concept that folks may possess a hidden expertise that nobody suspected was there.
As I obtained older and extra mathematically savvy, I dismissed the entire thing as Hollywood hokum. Good Will Searching would possibly inform a terrific story, but it surely isn’t very life like. In actual fact, the mathematical problem doesn’t maintain up underneath a lot scrutiny. With the award ceremony for the Oscars this month, many individuals are pondering again on previous winners—together with Good Will Searching. It’s price taking a better have a look at the blackboard in a movie that, in 1997, took 9 nominations and gained for each authentic screenplay and actor in a supporting position.
On supporting science journalism
If you happen to’re having fun with this text, think about supporting our award-winning journalism by subscribing. By buying a subscription you might be serving to to make sure the way forward for impactful tales concerning the discoveries and concepts shaping our world at the moment.
Based mostly on Precise Occasions
The movie was impressed by a real story—one I personally discover much more compelling than the fairy story model in Good Will Searching. The actual story facilities George Dantzig, who would in the future turn out to be generally known as the “father of linear programming.”
Dantzig was not all the time a prime pupil. He claimed to have struggled with algebra in junior highschool. However he was not a layperson when the occasion that impressed the movie occurred. By that point, he was a graduate pupil in arithmetic. In 1939 he arrived late for a lecture led by statistics professor Jerzy Neyman on the College of California, Berkeley. Neyman wrote two issues on the blackboard, and Dantzig assumed they had been homework.
Dantzig famous that the duty appeared tougher than standard, however he nonetheless labored out each issues and submitted his options to Neyman. Because it turned out, he had solved what had been then two of essentially the most well-known unsolved issues in statistics.
That feat was fairly spectacular. In contrast, the mathematical downside used within the Hollywood movie may be very simple to unravel when you study a number of the jargon. In actual fact, I’ll stroll you thru it. Because the film presents it, the problem is that this: draw all homeomorphically irreducible bushes of measurement n = 10.
Earlier than we go any additional, I wish to level out two issues. First, the presentation of this problem is definitely essentially the most troublesome factor about it. It’s fairly unrealistic to anticipate a layperson—no matter their mathematical expertise—to be aware of the technical language used to formulate the issue. However that brings me to the second factor to notice: when you translate the technical phrases, the precise activity is easy. With a bit of persistence and steerage, you possibly can even assign it to youngsters.
Fixing the Good Will Searching downside
Let’s get into the vocabulary. In arithmetic, a tree is a kind of graph—that’s, a group of factors which can be linked to 1 one other. Bushes, notably, can not comprise loops, so you can not join the factors in a manner that causes them to shut into one. The dimensions of the tree is given by way of the variety of factors, or nodes, within the graph. On this case, we all know we’re meant to attract all attainable tree graphs with 10 nodes.
The time period “homeomorphic” principally refers to the concept that the nodes on this community all the time observe a selected sequence; the precise form of the tree will not be as essential because the sequence of connections. Once I draw a connection between nodes A and B, I could make that hyperlink longer or shorter or rotated barely, and it gained’t matter as long as the general construction of the community stays the identical. The essential half is that A connects to B.
To consider that another way, think about a tree formed like an X with 5 nodes and a tree formed like a Ok with 5 nodes. These bushes are thought-about to be the identical tree as a result of the variety of nodes and sequence of connections are unchanged between the 2 shapes.
And “irreducible,” on this case, implies that each node within the graph have to be linked by both one line or by three or extra strains such that no node is linked by solely two strains: if a node was linked by solely two strains, it could possibly be diminished into only a single line.
So in plain language, the duty is to attract all bushes with the desired properties that every have 10 nodes. There are a number of approaches to this. For instance, you possibly can write a pc program that solves the duty in a fraction of a second. Or you possibly can begin drawing all of the graphs that fulfill these standards by hand. It seems that you could be solely want a couple of minutes of doodling when you determine to go together with the latter route.
To show that, you possibly can first draw a tree consisting of 1 central node that radiates out with 9 connections, giving us a complete of 10 nodes. That design meets the required standards—it’s one in every of our homeomorphically irreducible bushes of measurement n = 10. Good work!
Subsequent, draw a tree with eight connections—you’ll discover this design results in a useless finish since you gained’t have the ability to add a node with out both re-creating the earlier tree or introducing a reducible line. Transfer on to drawing a tree that begins with a node that has seven connections. You’ll nonetheless want to put two extra nodes, however you possibly can think about including them to one of many seven you’ve simply drawn. At this level, it’s best to have the ability to preserve doodling by means of the probabilities.
If you happen to desire an much more systematic strategy—although it might take you a bit extra time, relying in your consolation with graph principle—one intelligent answer includes contemplating which mathematical situations the bushes should fulfill and representing them with equations.
For this strategy, we are able to outline nk because the variety of nodes n with okay connections. As a result of the tree ought to be irreducible, there is no such thing as a circumstance the place n2 can exist, so n2 = 0. Moreover, we all know the tree will need to have 10 nodes complete—which means you’ll by no means have n10 or n11, and so forth. The utmost is n9.
We are able to then characterize what we all know with a mathematical components:
n1 + n3 + n4 + n5 + n6 + n7 + n8 + n9 = 10
Word that we skipped n2 as a result of we all know that might equal 0.
There’s one other constraint that we are able to categorical. Our tree with 10 nodes will in the end have 18 strains, or connections, between them if we depend in such a manner that the hyperlink between node A and node B counts twice, with one being A-B, and the opposite being B-A. We are able to use that to construct an equation the place we characterize every connection and node individually. For instance, if a node hyperlinks to 1 different node, it creates one connection: 1n1. If a single node hyperlinks to 3 different nodes, there will probably be three connections created, so 3n3, etcetera. This leads us to the following equation:
n1 + 3n3 + 4n4 + 5n5 + 6n6 + 7n7 + 8n8 + 9n9 = 18
Now you’ve created two equations that corral and constrain our tree-drawing choices. However we have to mix them to establish the phrases most related for our activity. You’ll be able to subtract the primary equation from the second to supply:
2n3 + 3n4 + 4n5 + 5n6 + 6n7 + 7n8 + 8n9 = 8
This equation serves as a reference for drawing your numerous bushes. The concept is to take phrases that, collectively, will equal 8 while you sum their first integer, or coefficient. Take a look at 8n9 for instance. That tells us we solely want one n9 to construct our tree, which corresponds to the drawing during which a single node has 9 connections.
If you happen to attempt to attract n8, you’ll hit the dead-end situation, with no tree that meets our standards. If you happen to had been utilizing our equation for reference, you wouldn’t even hassle making an attempt to attract it since you’d see you couldn’t mix 7n8 with one other time period such that the primary quantity in every would equal 8.
However a node with seven connections, n7,can work when you mix it with n3,that means you possibly can mix a tree with seven connections (represented by 6n7 within the equation) and a tree with three connections (2n3) to seek out one other answer to the issue. And you may keep it up with the method from there!
Higher Examples Exist
I can perceive why Good Will Searching’s filmmakers shied away from Dantzig’s precise work. The answer he devised was not brief—and the bushes are in all probability extra visually interesting for a cinematographer.
However I nonetheless suppose the filmmakers selected this explicit math downside poorly, even for a Hollywood movie. The historical past of arithmetic has many wonderful tales, together with true tales of precise laypeople fixing an open downside, that could possibly be nice fodder for movies.
Within the area of geometry, for instance, many breakthroughs relating to tiling the airplane have been achieved by formidable individuals who hadn’t studied arithmetic or something comparable. Considered one of my private favorites occurred in 2022, when retired print technician David Smith lastly discovered the long-sought “einstein tile,” a polygon that may fill a airplane utterly with none gaps and with out the ensuing sample ever repeating itself.
This text initially appeared in Spektrum der Wissenschaft and was reproduced with permission. It was translated from the unique German model with the help of synthetic intelligence and reviewed by our editors.
