[MATH] The Mosaic Problem
| GitHub Repo š¾ | YouTube Video šŗ | Scope: āāā |
Academic Beginnings
My academic story begins on a long flight across the Atlantic, shortly before my freshmen year. Bored out of my mind, I sketched out the following problem on the back of a cheap sketchpad. Take the following six tiles
and create a $n \times m$ rectangular grid using them. Letās call these grids mosaics. For example, below is a $(7,5)-$mosaic.
Clearly there are $6^{nm}$ possible mosaics. The question I asked on that flight was for a given $n$ and $m$, how many mosaics contain at least one connected āloopā, like below?
I would later learn that these loops are called self-avoiding polygons, or SAPs, so that is what we will call them from now on.
Initial Work
Letās defined $t_{n,m}$ to be the number of mosaics that contain at least one self-avoiding polygon. Similarly, let $p_{n,m} = \frac{t_{n,m}}{6^{nm}}$ be the probability a random $(n,m)-$mosaic contains at least one SAP.
We can compute the first couple values of $t_{n,m}$ by hand, sketching out each case. For example, $t_{2,2}=1$, as the only SAP one can make is
As this is the smallest SAP one can make, we know that $t_{n,1}=t_{1,m}=0$. We can do some casework to determine other small values of $t_{n,m}$. For $t_{3,2}$ we have the following three cases.
Here we denote cells that can be any tile with a dot, and refer to them as an open. As we have $6$ distinct tiles, we conclude that $t_{3,2} = 1 + 6^2 + 6^2 = 73.$ If we were to continue similarly with $t_{4,2}$ with the following $7$ cases, we would incorrectly conclude that there are $3962$ in total.
This is because the right-most case is counted in both the fourth-from-left case and sixth-from-right case. This means we should subtract this case, and so we conclude that $t_{4,2=3960}.$
The last value I calculated on the plane was $t_{3,3}=31998$, which is left as an excersize to the reader. Additionally, a basic symmetry argument gives $t_{n,m}=t_{m,n}$, so we can write the following table to summarize our calculations.
| $t_{n,m}$ | 1 | 2 | 3 | 4 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 1 | 73 | 3960 |
| 3 | 0 | 73 | 31998 | ? |
| 4 | 0 | 3960 | ? | ? |
This table was as far as I got on that plane ride, as the other values just seemed too complicated to compute by hand. But the problem really stuck with me. I wanted to know more values of $t_{n,m}$, and especially wanted a formula for these values. Unfortunately, I would have to wait to obtain new skills in my undergraduate before I could get further.
Advancements in Undergraduate
The first course that helped me was MATH 3160: Probability. This course formally taught me the generalization of the double-counting issue we encountered with $t_{4,2}$, which is known as the inclusion-exclusion principle. I found myself understanding the topic well in class thanks to my work on this problem!
The next course that helped me was CSE 1010: Intro to Programming. This course taught me how to program in Python. After many attempts and improvements, I was able to write an algorithm that computed values of $t_{n,m}$ directly.
...
def mosaics_help(plane, memoize, saps_list, opens, depth, h, w):
return_val = 0
for i in range(h-1):
for j in range(w-1):
if plane[i][j] == 0:
...The algorithm isnāt very efficient, but did allow me to complete the table I sketched out a year prior.
| $t_{n,m}$ | 1 | 2 | 3 | 4 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 1 | 73 | 3960 |
| 3 | 0 | 73 | 31998 | 10414981 |
| 4 | 0 | 3960 | 10414981 | 20334816290 |
The course that really opened up this problem to me was MATH 3250: Combinatorics. This course taught me all about linear recurrence relations, and more importantly how to solve them using generating functions. These concepts allowed me to write and prove Theorems 1 and 2.
Theorem 1. Setting $m=2$ gives
\[T_2(x) = \sum_{n \geq 2}t_{n,2}x^n = \frac{x^2}{(1-36x)(1-37x+37x^2)}.\]This can be solved for $n \geq 2$ to give
\[t_{n,2}= 6^{2n} - \frac{1}{\beta-\alpha}((36\beta-35)\beta^{-n+1} - (36\alpha - 35)\alpha^{-n+1})\]where $\alpha = \frac{1}{2} + \frac{1}{2}\sqrt{\frac{33}{37}}$ and $\beta = \frac{1}{2} - \frac{1}{2}\sqrt{\frac{33}{37}}$.
Proof. We prove that $t_{n,2}$ has \(t_{n,2} = 36t_{n-1,2} + \sum_{i=2}^{n}(6^{2(n-i)}-t_{n-i,2}).\)
Split $t_{n,2}$ into $S_n$ and $S_n^c$. $S_n$ contains the mosaics that have just $1$ SAP that contains the left-most two cells. This means $S_n^c$ contains all mosaics that contain multiple SAPs and mosaics that contain only $1$ SAP, but that does not contain the two left-most cells.
The subset $S_n$ can be split further by the length of each SAP $i$.
As $S_n$ counts the number of mosaics that only contain $1$ SAP, the blank space in the figure above must have no SAPs. The number of mosaics that have no SAPs is $6^{2(n-i)}-t_{n-i,2}$. As a SAPās width can range from $2$ to $n$, we have $|S_n| = \sum_{i=2}^{n}(6^{2(n-i)}-t_{n-i,2}).$
Now consider $S_n^c$. The mosaics that belong to this set can be represented by the following diagram,
where the red dot in the left most cells indicate any marking. We can conclude that $|S_n^c| = 6^{2}t_{n-1,2}$. Combining $S_n$ and $S_n^c$ gives the recurrence relation. Standard techniques then give the generating function and formula.
Theorem 2. Setting $m=3$ gives
\[T_3(x) = \sum_{n \geq 2}t_{n,3}x^n = \frac{(73-414x)x^2}{(1-216x)(1-228x+2699x^2-7758x^3)}\]Proof. For $t_{n,3}$ we directly compute the generating function $T_3(x)=\sum_{n \geq 2}t_{n,3}x^n$ using the following recurrence relation \(t_{3,n} = 6^3 t_{n-1,3} + \sum_{i = 2}^{n}(6^{3(n-i)} - t_{n-i,3})f_{i},\) where $f_{i}$ is the number of mosaics in an $i \times 3$ grid that contain just one SAP that has cells in the left-most column. We similarly split $t_{n,3}$ into $S_n$ and $S_n^c$. Here let $S_n$ be the set that contains the mosaics that have just $1$ SAP that has cells in the left-most column. Therefore $S_n^c$ contains all mosaics that contain multiple SAPs and mosaics that contain $1$ SAP that does not have cells in the left-most column.
Similarly for the $n=2$ case, $S_n^c$ can be easily enumerated.
It is clear to see that $|S_n^c| = 6^3 t_{n-1,3},$ and so
\[\sum_{n \geq 2} |S_n^c|x^n = 6^3 xT(x).\]To enumerate $S_n$, as in the $n=2$ case, the SAP starts in the first column and ends at column $i$, after which there are no SAPs. This allows us to conclude that $|S_n| = \sum_{i = 2}^{n}(6^{3(n-i)} - t_{n-i,3})f_{i},$, where $f_i$ is the number of ways the cells to the left of and including column $i$ can contain $1$ SAP that includes the left-most column. To find the identity of $f_i$, we study the $4$ cases below.
It is easy to see that $a_2 = 36$ and $a_3 = 216$. As $i$ increases, one can see that the enumeration of $a_i$ is related to smaller values of $a_i$ and $b_i$, more specifically
\[a_i = 6a_{i-1} + 6^2 b_{i-2}.\]We find similar relations with the other $3$ cases, namely
\[b_n = 6b_{n-1} + 6^2 d_{n-2}\]where $b_2 = 0$ and $b_3 = 6$
\[c_n = 6c_{n-1} + 6^2 b_{n-2}\]where $c_2 = 0$ and $c_3 = 0$
\[d_n = 6d_{n-1} + 6^2 b_{n-2}\]where $d_2 = 1$ and $d_3 = 6.$ Combining these $4$ cases, and accounting for the appropriate symmetries, we arrive at
\[f_i = 2a_i + 4b_i + 2c_i + d_i.\]Solving this series of recurrence relations using generating functions gives
\[F(x) = \sum_{i \geq 2} f_i x^i = \frac{73 - 414x}{1-12x+43x^2}\]This allows us to write \(\sum_{n \geq 2} |S_n|x^n = \left(\frac{1}{1-6^3x}-T(x)\right)F(x).\) Combining these two generating functions and simplifying gives the result.
A YouTube Contest
A year after my undergraduate, I decided that I would enter the third Summer of Math Exposition contest. I had already been making YouTube videos about math, and I decided all the lessons I learned with this problem would make for a good story. I also knew that many people would also be using Manim for the contest, so I decided to ask my girlfriend to create some hand-made animations to set my video apart visually.
I will fondly remember the long nights working on the video and finally submitting it. After participating in the judging of many other contestant videos, and waiting nervously, I was delighted to see that it was chosen as one of the honorable mentions! I received a $500 cash prize, and recognition on the 3Blue1Brown YouTube channel.
My favorite part was the feedback I received on my video from Grant Sanderson himself, the contestās judges, and other participants. It was a very personally-rewarding project, and I enjoyed every minute of the process. But even the money and feedback was not the best part of the process. It would turn out to be that the video moved the mosaic problem to completion.
A Complete Solution
About a year after I published the video, I received a comment claiming to have a method for computing $t_{n,m}$ for small fixed $m$. The comment came from a user called Farstar31, who suggested a new method that we were able to generalize into a final solution.
After some discussions over twitter and email, we worked out a method to compute $6^{nm} - t_{n,m}$ for any $n$ and $m$.
Theorem 3. Let
\[M(2) = \begin{bmatrix} 6^2 & 1 \\ -1 & 1 \end{bmatrix}\]For $n \geq 2$, then if
\[M(n) = \begin{bmatrix} M_1 & M_2 \\ M_3 & M_4 \end{bmatrix}\]then
\[M(n+1) = \begin{bmatrix} 6M_1 & 6M_2 & \frac{1}{6}M_1 & M_2 \\ 6M_3 & 6M_4 & 0M_3 & M_4 \\ -\frac{1}{6}M_1 & 0M_2 & \frac{1}{6}M_1 & M_2 \\ M_3 & M_4 & -M_3 & 6M_4 \\ \end{bmatrix}\]where $M_i$ is a sub-matrix of the block matrix $M(m)$. For the given $m$, define the rows and columns of $M(m)$ as
\[M(m) = \begin{bmatrix} r_1 \\ r_2 \\ ... \\ r_{2^{m-1}} \\ \end{bmatrix} = \begin{bmatrix} c_1 & c_2 & ... & c_{2^{m-1}} \end{bmatrix}\]Then $6^{nm} - t_{n,m} = r_1 M(m)^{n-2}c_1 .$
Proof. The proof is lengthy, so the full writeup can be found here.
A Similar Published Problem
Even though I made this problem up independently, a very similar problem was studied in 2018. The paper Bounds on Multiple Self-Avoiding Polygons by Hong and Oh [1] studies the following similar problem. Consider the following $7$ tiles
The authors considered the number of shapes that had no āhanging connectionsā, like so.
Amazingly, by sheer coincidence, the authors also chose to call these shapes mosaics. The authors called the number of these polygon mosaics $p_{n,m}$, and provided the following upper and lower bounds.
\[2^{n+m-3} \left(\frac{17}{10}\right)^{(n-2)(m-2)} \leq p_{n,m} + 1 \leq 2^{n+m-3} \left(\frac{31}{16}\right)^{(n-2)(m-2)}.\]Our method also was able to exactly enumerate these mosaics.
Theorem 4. Let
\[M(2) = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}\]for $n \geq 2$. Then for $m \geq 2$, if
\[M(m) = \begin{bmatrix} M_1 & M_2 \\ M_3 & M_4 \end{bmatrix}\]define
\[M(m+1) = \begin{bmatrix} M_1 & M_2 & M_1 & M_2 \\ M_3 & M_4 & 0M_3 & M_4 \\ M_1 & 0M_2 & M_1 & M_2 \\ M_3 & M_4 & M_3 & M_4 \\ \end{bmatrix},\]where $M_i$ is a sub-matrix of the block matrix $M(m)$. Next define the rows and columns of $M(m)$ as
\[M(m) = \begin{bmatrix} r_1 \\ r_2 \\ ... \\ r_{2^{m-1}} \\ \end{bmatrix} = \begin{bmatrix} c_1 & c_2 & ... & c_{2^{m-1}} \end{bmatrix}\]Then $p_{n,m}+1 = r_1 M(m)^{n-2}c_1 .$
Proof. The proof is also lengthy and can be found here.
Thank you for reading!
Citations
- Hong, K., & Oh, S. (2018). Bounds on Multiple Self-avoiding Polygons. Canadian Mathematical Bulletin, 61(3), 518ā530.