I still remember the movie night when I first saw Good Will Hunting with my mother. Matt Damon played a janitor at the Massachusetts Institute of Technology. While cleaning the halls, he passed a blackboard with an advanced math problem written on it. He stopped and began to solve the problem. I watched mesmerized as he created seemingly unreadable structures of dots and lines—until suddenly a math professor emerged from a lecture hall and chased him away.
The audience was previously told that this problem was supposed to be incredibly difficult, taking years of expert thinking to solve, but it was quickly solved by Damon’s perceptive caretaker in just moments. At the time, I was fascinated by the idea that people could have a hidden talent that no one suspected was there.
As I got older and more mathematically savvy, I dismissed it all as Hollywood hokum. Good Will Hunting can tell a good story, but it is not very realistic. In fact, the mathematical challenge does not hold up under much scrutiny. With the awards ceremony for the Academy Awards this month, many people are thinking back to past winners – included Good Will Hunting. It is worth taking a closer look at the board of a film which in 1997 received nine nominations and won both for original screenplay and actor in a supporting role.
On supporting science journalism
If you like this article, please consider supporting our award-winning journalism by subscribes. By purchasing a subscription, you help secure the future of impactful stories about the discoveries and ideas that shape our world today.
Based on actual events
The film was inspired by a true story – one that I personally find far more compelling than the fairy tale version Good Will Hunting. The real story centers on George Dantzig, who would one day be known as “the father of linear programming.”
Dantzig was not always a top student. He claimed to have struggled with algebra in secondary school. But he wasn’t a layman when the event that inspired the film happened. At the time he was a graduate student in mathematics. In 1939, he arrived late for a lecture led by statistics professor Jerzy Neyman at the University of California, Berkeley. Neyman wrote two problems on the board, and Dantzig assumed they were homework.
Dantzig noted that the task seemed more difficult than usual, but he solved both problems and submitted his solutions to Neyman. As it turned out, he had solved what were then two of the most famous unsolved problems in statistics.
That feat was quite impressive. In contrast, the math problem used in the Hollywood movie is very easy to solve once you learn some of the jargon. In fact, I’m going to walk you through it. As the film presents it, the challenge is this: draw all homeomorphically irreducible trees of size n = 10.
Before we go any further, I want to point out two things. First, the presentation of this challenge is actually the hardest part about it. It is quite unrealistic to expect a layperson – regardless of mathematical talent – to be familiar with the technical language used to formulate the problem. But that brings me to the second thing to note: when you translate the technical terms, the task itself is simple. With a little patience and guidance, you can even give it to children.
Solving Good Will Hunting problem
Let’s get into the vocabulary. In mathematics, a tree is a type of graph – that is, a collection of points that are connected to each other. In particular, trees cannot contain loops, so you cannot connect the points in a way that makes them close together. The size of the tree is given in terms of the number of points, or nodes, in the graph. In this case, we know that we are meant to draw all possible tree graphs with 10 nodes.
The term “homeomorphic” basically refers to the idea that the nodes in this network always follow a certain sequence; the exact shape of the tree is not as important as the sequence of connections. When I draw a connection between nodes A and B, I can make that connection longer or shorter or rotated slightly, and it doesn’t matter as long as the overall structure of the network remains the same. The important part is that A connects to B.
To think of it another way, imagine a tree shaped like an X with five nodes and a tree shaped like a K with five nodes. These trees are considered to be same the tree because the number of nodes and the sequence of connections are unchanged between the two forms.
And “irreducible”, in this case, means that every node in the graph must be connected by either one line or by three or more lines, so that no node is connected by only two lines: if a node was connected by only two lines, it could be reduced to just a single line.
So in plain text, the task is to draw all trees with the specified properties that each have 10 nodes. There are several approaches to this. For example, you can write a computer program that solves the task in a fraction of a second. Or you can start drawing all the graphs that meet these criteria by hand. Turns out, you might just need a few minutes of doodling if you decide to go the latter route.
To demonstrate it, you can first draw a tree consisting of one central node radiating out with nine connections, giving us a total of 10 nodes. That design meets the necessary criteria—it is one of our homeomorphically irreducible trees of size n = 10. Good job!
Next, draw a tree with eight connections – you will find that this design leads to a dead end because you will not be able to add a node without either recreating the previous tree or introducing a reducible line. Proceed to draw a tree starting with a node that has seven connections. You still need to place two more nodes, but you might consider adding them to one of the seven you just drew. At this point, you should be able to continue scrolling through the options.
If you prefer an even more systematic approach – although it may take you a bit more time, depending on your comfort with graph theory – a smart solution involves considering what mathematical conditions the trees must meet and representing them with equations.
For this approach, we can define nk as the number of nodes n with k connections. Because the tree must be irreducible, there is no circumstance where n2 can exist, that is n2 = 0. Furthermore, we know that the tree must have 10 nodes in total – that means you will never have that n10 or n11and so on. The maximum is n9.
We can then represent what we know with a mathematical formula:
n1 + n3 + n4 + n5 + n6 + n7 + n8 + n9 = 10
Note that we skipped n2 because we know it is equal to 0.
There is another limitation we can express. Our tree with 10 nodes will eventually have 18 lines, or connections, between them if we count in such a way that the link between node A and node B counts twice, where one is AB, and the other is BA. We can use it to build an equation where we represent each connection and node individually. For example, if a node connects to another node, it creates one connection: 1n1. If a single node connects to three other nodes, there will be three connections made, so 3n3etc. This leads us to the next equation:
n1 + 3n3 + 4n4 + 5n5 + 6n6 + 7n7 + 8n8 + 9n9 = 18
Now you have created two equations that correct and limit our tree drawing options. But we need to combine them to identify the terms most relevant to our task. You can subtract the first equation from the second to produce:
2n3 + 3n4 + 4n5 + 5n6 + 6n7 + 7n8 + 8n9 = 8
This equation serves as a reference for drawing the different trees. The idea is to take terms that will add up to 8 when you add their first integer, or coefficient. Look at 8n9 for example. That tells us we only need one n9 to build our tree, which corresponds to the drawing where a single node has nine connections.
If you try to draw n8you will hit the dead end scenario, with no tree meeting our criteria. If you used our equation as a reference, you wouldn’t even bother trying to graph it because you’d see that you couldn’t combine 7n8 with another term so that the first number in each is equal to 8.
But a node with seven connections, n7can work if you combine it with n3which means you can combine a tree with seven connections (represented by 6n7 in the equation) and a tree with three connections (2n3) to find another solution to the problem. And you can continue the process from there!
There are better examples
I can understand why Good Will Hunting‘s filmmakers shied away from Dantzig’s actual work. The solution he developed was not short – and the trees are probably more visually appealing to a cinematographer.
But I still think the filmmakers chose this math problem poorly, even for a Hollywood movie. The history of mathematics has many wonderful stories, including true stories of actual lay people solving an open-ended problem, which would make great fodder for movies.
In geometry, for example, many breakthroughs regarding tiling the plane have been achieved by ambitious people who had not studied mathematics or anything similar. One of my personal favorites happened in 2022, when retired printing engineer David Smith finally found the long-sought “einstein tile,” a polygon that can fill a plane completely without holes and without the resulting pattern ever repeating itself.
This article originally appeared in Spectrum der Wissenschaft and was reproduced with permission. It was translated from the original German version with the help of artificial intelligence and reviewed by our editors.
