October 2025 - Solution
October 2025 Solution:
The numerical solutions are:1.148e1174 1.609e61571
Obtaining those solutions via brute-force counting is obviously unfeasible, but there are some beautiful tricks that can be applied. First, mazes as they are defined here are nondirected trees in a graph where the vertices represent cells, and there is an edge between two adjacent cells. This is a classical method to generate mazes: construct the graph, then run Kruskal's or Prim's algorithm on it (adding weights to the graph enables one to control the shape of the generated maze). However, in this problem we don't want to generate a maze, rather to count all mazes, hence count all spanning trees of the graph.
A beautiful theorem of basic graph theory is Kirchhoff's matrix tree theorem, which reduces the enumeration of spanning trees in a general (directed/non-directed) graph to the computation of the determinant of the graph's Laplacian matrix. This is further simplified if one knows the eigenvalues of the matrix; there is at least one zero eigenvalue, and if the rest of the eigenvalues for the n\times n matrix are \lambda_1,\ldots,\lambda_{n-1} then the number of spanning trees is \frac{1}{n}\lambda_1\lambda_2\cdots\lambda_{n-1}.
Directly applying the matrix tree theorem in this specific case is tricky, as the numbers were chosen so the resulting matrix is quite large. However, for the specific graph in question we can simply matters considerebly, since it can be seen as a product of two simple lines graphs. Let us denote by C_n the graph with vertices V=\{1,2,\ldots,n\} and edges E=\{(k,k+1)\ |\ 1\le k < n\}. Then the graph for the n\times m grid is C_{n,m}=C_n\square C_m where \square denotes the "box product" of graphs, where the vertices of G_1\square G_2= are V_1\times V_2 and the edges are \{(a,u),(b,v)\ | \ ((a,b)\in E_1\wedge u=v)\vee (a=b\wedge(u,v)\in E_2\} (conceptually, the box product of graphs corresponds to the notion of trversing both graphs at the same time, taking a step in only one of the graphs each time).
For box products G_1\square G_2, if \lambda_1\ldots,\lambda_n and \tau_1\ldots,\tau_m are the eigenvalues of both graph laplacians, then the eigenvalues of the laplacian of G_1\square G_2 are \{\lambda_i+\tau_j\ |\ 1\le i\le n, 1\le j\le m\}. Hence, the problem is reduced for finding the eigenvalues of the line graph C_n, and it can be shown using Chebyshev polynomials that these eigenvalues are of the form 4\sin^2\left(\frac{k\pi}{2n}\right) for 1\le k \le n-1. This leads us to the formula solving the puzzle for general n,m:
T(n,m) = \frac{1}{nm}\prod_{k=0}^{n-1}\prod_{h=0}^{m-1}\left(4\sin^2\left(\frac{k\pi}{2n}\right)+4\sin^2\left(\frac{h\pi}{mn}\right)\right)
This can be slighty simplified by noting that for h=0 we have \prod_{k=0}^{n-1}4\sin^2\left(\frac{k\pi}{2n}\right)=n (since this is the product of eigenvalues for C_n, which has only one spanning tree) and similarily for k=0, so the formula simplifies to
T(n,m) = \prod_{k=1}^{n-1}\prod_{h=1}^{m-1}\left(4\sin^2\left(\frac{k\pi}{2n}\right)+4\sin^2\left(\frac{h\pi}{mn}\right)\right)
See "[The Discrete Laplacian of a Rectangular Grid ](https://sites.math.washington.edu/~reu/papers/2013/tom/Discrete%20Laplacian%20of%20a%20Rectangular%20Grid.pdf)" by T. Edwards for further details.
Computing the product in practice can cause numeric problems; the usual approach in such situations is computing the logarithm of the expression (trasnforming the product into a sum) and exponentiating the result.