The Math Problems from Good Will Hunting, w/ solutions

How do you like them apples?

The Math Problems from Good Will Hunting, w/ solutions
Photo: © 1997 Miramax Pictures

The purpose of this article is to narrate you through solutions to the two math problems solved by the fictional character Will in the 1997 Academy Award-winning movie Good Will Hunting. The narration is based largely on the excellent paper Mathematics in Good Will Hunting II: Problems from the Students Perspective by Horváth, Korándi and Szabó (2010).

Spotify mood music. Happy reading!

Plot

Quickly summarized Good Will Hunting tells the story of the imaginary character Will Hunting, who despite his exceptional intelligence works as a janitor at the Massachusetts Institute of Technology in Boston. There, he one day spots a problem on blackboard in a hallway posed by a Fields Medal award-winning professor named Gerald Lambeau. Gifted with an eidetic memory, Will memorizes the problem and solves it on the mirror in his bathroom at home in South Boston. Back at MIT the next day, he can’t help himself but provide his solution anonymously on the blackboard.

When the next day none of Lambeau’s students claim credit, the professor poses another, more difficult problem. Will again solves it but gets caught in the act of writing out his solution by the professor, who is shocked to realize that the most brilliant young mathematician at MIT is an uneducated janitor.

The First Problem

Professor Gerald Lambeau (portrayed by Stellan Skarsgård) looking over Will’s proposed solution. Photo: © 1997 Miramax Pictures

Problem 1: Given the graph G, find1. The adjacency matrix, A
2. The matrix giving the number of 3 step walks
3. The generating function for walks from i → j
4. The generating function for walks from 1 → 3

Figure 1: The graph G

The first problem, in graph theory, asks for the number of walks from a vertex ito vertex j in a graph G. For this, let G be a graph with set of vertices V = {1, 2, 3, 4} and set of edges E = {(1,2), (1,4), (2,4), (2,3),(2,3)} where (2,3) is a double edge.

Solutions to Problem 1

Problem 1.1
Given the graph G, find the adjacency matrix A

An adjacency matrix is a square matrix used to represent a finite graph. The elements of the adjacency matrix L indicate whether pairs of vertices in the graph are adjacent or not. For a simple graph with a set of vertices V, the adjacency matrix is a square |L| × |L| matrix such that its element Lᵢⱼ is 1 when there is one edge from vertex i to vertex j, 2 when there are two, and zero when there are no edges from vertex i to vertex j. The diagonal elements of the matrix are all zero, since edges from a vertex i to itself (loops) are not allowed in simple graphs. For all step walks of length 1 along the edge set E, this gives us the following adjacency matrix for the graph G:

Solution 1.1. Edge elements from vertices i to j and adjacency matrix of graph G, showing the number of edges between vertices i and j

Problem 1.2
Find the matrix giving the number of 3 step walks

The second task in problem 1 asks to find the matrix which encodes all possible walks of length 3 (Knill, 2003). That is, to find the number of different sequences of edges which join every distinct sequence of vertices.

An n + 1 step walk from i to j consists of an n step walk from i to k and then a 1 step walk from k to j. That is, the ij entry of Lⁿ⁺¹ is given by the sum:

Equation 1

Which in English for this problem states that “the number of walks of length 3 from vertex i to j" is equal to the sum of “the number of walks of length 2 from vertex i to k” multiplied by “the number of walks of length 1 from vertex to j” for k = 1,2. By matrix multiplication, for all step walks of length 3 from i to j this gives the following matrix:

Solution 1.2. The matrix representing the number of 3 walks from vertex i to j in graph G

Problem 1.3
Find the generating function for walks from i → j

The third task in problem 1 asks for the generating function from vertex i to j. To answer this question, Horváth et al (2010) consider an analytic generating function defined by a power series

Equation 2

Where the coefficient zⁿ denotes the number of n step walks from i to j. From task 1.3, we found that ω_n(i → j) is the ij entry of the matrix Lⁿ. The problem asks for the generating function that gives all the entries simultaneously, and so it makes sense to consider a matrix L given by the familiar power series (Horváth et al, 2010):

Equation 3

Where Lⁿ is the matrix containing the number of step walks from each vertex to (the general case of the solution to problem 1.2). The sum can be calculated using the familiar identity for geometric power series, that is:

Equation 4

To calculate the inverse of ( z × L) we can use Cramer’s rule. According to Horváth et al (2010) for a matrix M let Mᵢⱼ denote the matrix obtained from Mby removing the ith column and the jth row. If we do so, we obtain a matrix N whose ij entry is

Equation 5

By Cramer’s rule, if M is invertible (there exists some n×n matrix N such that M×N = N×M = I_n) then

Equation6

That is, the ij entry of of the inverse matrix M is:

Equation 7

Applied to compute the inverse of M = ( z × L), we obtain:

Equation 8

Substituting for M:

Solution 1.3. The generating equation for walks from i to j

As Horváth et al (2010) notes, this is Will’s solution in the movie, except his solution omits the term (−1)^(i+j) (likely due to notation), and he denotes the identity matrix with 1 instead of the more common I.

Problem 1.4
Find the generating function for walks from 1 → 3

To solve task 1.4, we simply apply the general formula for walks from i to j (from task 1.3) to the case of walks from 1 → 3:

Equation 9.

Whose determinants are trivial to find:

Equation 10 and 11. Determinants of (I − zL) and its minor/reduced determinant (I₁₃ − zL₁₃)

Giving the following expressions, obtain by using the definition of a determinant:

Equation 12. Formula for determining the generating function for walks from vertex 1 to 3.
Equation 13. Formula for determining the values of the generating function for walks from vertex 1 to 3, solved

To obtain the coefficients of this power series, one computes the Taylor series of the function:

Equation 14. Function for calculating the Taylor series of f(z), the Maclaurin series, where fⁿ(0) is the nth derivative of f at 0.

For our expression f(z), we can use the quotient rule where g(z) = 2z² and h(z) = 4z³− 6z² −z +1. In the movie, Will provides the values for the first six derivatives of the f(z) expansion, which are:

Solution 1.4. Taylor expansion for determining the values of the generating function for walks from vertex 1 to 3

The Second Problem

A shocked Professor Lambeau gazes at the correct solution to the second problem, provided by the anonymous janitor he had just chased away. Photo: © 1997 Miramax Pictures

As Will didn’t sign his work on the board for his solution to the first problem, Professor Lambeau posed a second problem, of which he states to his class “took us more than two years to prove”. The problem again regards tree structures:

Problem 2
a. How many trees are there with n labeled vertices?
b. Draw all homomorphically irreducible trees with n = 10

Solutions to Problem 2

As Horváth et al (2010) points out, task 2a actually just asks for Cayley’s formula that for every positive integer the number of trees on n-labeled vertices is nⁿ⁻². The formula is named after Arthur Cayley, but has been known since it was discovered by Carl Wilhelm Borchardt in 1860. In Cayley’s 1889 note A theorem on trees in the Quarterly Journal of Pure and Applied Mathematics, he extended the formula by taking into account the degrees of the vertices, and so it has since bore his name. There are several known proofs of the result.

The final task, problem 2b asks for drawings of all the homomorphically irreducible trees with n = 10. A homomorphically irreducible tree is one with no points of degree 2. The problem was likely inspired by the paper The Number of Homomorphically Irreducible Trees, and Other Species by Harary & Prins (1959).

We can group the homomorphically irreducible trees by labelling their vertices by 1,…., 10 and the degrees of their vertices by d₁, …,d₁₀ (Horváth et al, 2010). As the trees have 10 vertices, we know they have 9 edges. We can categorize these various trees by their number of leaves (nodes/vertices of vertex degree 1):

  • If there are 9 leaves and 1 non-leaf, then we obtain a “star”, a single vertex connected to every leaf:
  • If there are 8 leaves and 2 non-leaf, then d₁ + d₂ = 10 and d₁ ≥ d₂ ≥ 3, so either: a) d₁ =7 and d₂ = 3 (one tree), or b) d₁ = 6 and d₂ = 4 (one tree), or c) d₁ = d₂ = 5 (one tree).
Homomorphically irreducible trees with 8 leaves
  • If there are 7 leaves , then d₁ + d₂ + d₃ = 11 and d₁ ≥ d₂ ≥d₃ ≥ 3, so either a) d₁ = d₂ = 5 and d₃ = 3 (two trees), or b) d₁ = 5 and d₂ = d₃ = 3 (three trees).
a) Homomorphically irreducible trees with 7 leaves and d₁ ) d₂ = 5 and d₃ = 3
b) Homomorphically irreducible trees with 7 leaves and d₁ = 5 and d₂ = d₃ = 3
  • If there are 6 leaves, then d₁ + d₂ + d₃ +d₄ = 3.
Homomorphically irreducible trees with 6 leaves and d₁ = d₂ = d₃ = d₄ = 3

That totals to 10 trees with n=10. On the blackboard in the movie, only 8 appear, either because Will was interrupted by Professor Lambeau or due to an oversight on the filmmakers’ part.

Backstory

In early versions of the script for Good Will Hunting, the character Will was a physics prodigy, but Sheldon Glashow at Harvard suggested it be about a mathematician instead, as modern physics is “typically a group project” whereas “doing some mathematical theorem is a singular undertaking very often” (London, 2016). The film’s mathematics consultant was Professor of physics at the University of Toronto, the late Patrick O’Donnell.

It has been speculated that the character of Will is based on child prodigy William Sidis (1898–1944), known for his exceptional mathematical abilities.

Acknowledgement

The narration provided in this essay is based largely on the wonderful paper Mathematics in Good Will Hunting II: Problems from the students perspective by Horváth, Korándi and Szabó (2010). I encourage everyone interested to read their original, in-depth paper available here which also includes discussions of the other pieces of mathematics shown in various scenes throughout the movie.