Study Finds Most NYT Games End in Rage Quits [solution]

Solution for the week of 5/18

Last week we trying analyzing a new game Lines’n’Gons (check this link if you need a refresher on the rules).

You want to analyze how users play the game, but your initial analysis shows that many people don’t complete their games. To aid your analysis, you consider grouping and counting every final board configuration—finished and un-finished—so that all your subsequent analysis is speedy. Before you begin, you decide you want to determine how many distinct final board configurations there are. Every board has a predetermined ‘bottom’ so we can consider a board distinct if it has the same configuration once the bottom is properly positioned. For example, these two hexagonal game boards would be considered distinct.

Note the bolded side on the bottom. These two hexagonal configurations would be considered distinct despite their rotational symmetry. Also note that they are unfinished boards.

Final board configurations can include any number of player moves (including 0). By final board configuration, we just mean the configuration the board was in when the players stopped, so we don’t need to concern ourselves with the order of moves or anything like that.

The question this week is, how many distinct final board configurations are possible with an octagon board? How about an n-gon board?

Shout out to Vamshi Jandhyala and Josh Arnold for their correct submissions. They both arrived at the correct answer of 903. So how do we get that?

Well, I found that this problem was a bit easier if we [kinda] work backward. let’s imagine we have a completed board—that is to say an octagon that’s fully triangulated. How many such boards are there?

Let’s label the vertices 1,2,…,n counter-clockwise and define the “bottom” to be the edge (1,n). We will begin our triangulation with this edge. Basically we draw two diagonals, one starting at vertex 1 and another starting at vertex n and both going to a vertex i forming a base triangle (1,i,n) for some 2≤i≤n−1. That triangle splits the n-gon into two smaller polygons:

• a left polygon with i vertices, whose triangulations are counted by T(i);

• a right polygon with n−i+1 vertices, whose triangulations are counted by T(n−i+1).

Because these two choices are independent, T(n) satisfies the convolution recurrence

\(T(3)=1,\qquad T(n)=\sum_{i=2}^{n-1} T(i)\,T(n-i+1)\quad(n\ge 4). \)

To make things a little clearer, we’ll define m=n−2 and k=i−2. Does this recursion look familiar?

\(C_0=1,\qquad C_m=\sum_{k=0}^{m-1} C_k\,C_{m-1-k}\quad(m\ge 1), \)

This is the recurrence relationship for the Catalan numbers! The proof of the closed form of the Catalan numbers is a little lengthy and well-documented (and I think we’ve gone over it in previous puzzles) so I will omit it and just leave you with

\({\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}.}\)

Ok, now that we have the number of complete boards, we’ll take a little bit of an intuitive leap. Consider for a moment what would happen if we started with a completed octagon board, and added a new vertex between two existing vertices? Obviously, this new vertex wouldn’t be part of any diagonal. We would have just constructed an incomplete nonagon board (9-gon). Specifically it would be one move short of a complete board. What if we continue adding vertices? We can create any incomplete board that has exactly 5 diagonals (the number of diagonals in a complete octagonal board). Reversing this thinking a bit, this also means that any incomplete octagonal board can be constructed by adding vertices to a sufficiently small complete board. For example, if we want the octagonal board with only 1 diagonal on it, we would start with a completed square board and add 4 vertices.

And since we already know the number of complete boards of any size, we can use this to to help with our counting! We just need to figure out how many different ways we can add the extra vertices. So where can we place these extra vertices in a way to ensures we generate unique boards? Well, it isn’t sufficient just to pick a random edge between two vertices of the existing board and place on there. The image below illustrates why this is the case.

We selected two different edges to place the new vertex but they results in the same subdigon.

So how do we select the spots? Well, one way to distinguish a board is by listing the different sub-polygons that make up the larger polygon (which I’ll call the subdigon). From that perspective, what we care about isn’t which edge the new vertex gets placed on, but which sub-polygon it will now be a part of. A board with k diagonals will have k+1 different sub-polygon faces that we could add that vertex to. In other words, we’re adding some number of new vertices m to k+1 existing regions. This is precisely the situation when we’d employ the classic Stars-and-Bars formula. (We'll redefine the variables a bit for convenience. 'n' will now be the size of the whole subdigon after we've added the m vertices and k will remain as the number of diagonals present)

\(\begin{align*} &\text{Starts-and-Bars} = \binom{a+b-1}{b-1} \\ &\Rightarrow \text{#ways to add vertices} = \binom{(n-2k)+(k+1)-1}{(k+1)-1} = \binom{n-k}{k} \end{align*}\)

Of course, we need to be careful about the symmetry here: the stars-and-bars count treats the polygon’s perimeter as a linear sequence that starts at a specific edge. Rotating the same board one step around the n boundary edges gives a different linear description but does not change the underlying subdivision. As such, we must divide the raw count by n to obtain the number of distinct (rotation-equivalent) boards. Pulling this together with the number of complete boards (which we already know) yields

\(F(n,k) = \frac{1}{n} \frac{1}{k+1} \binom{2k}{k} \binom{n-k}{k}\)

We simply sum this over all of the possible values 0≤k≤n-3 with n=8 to get our answer 903.

Extra Credit - The Hyper-Catalan Numbers

For anyone that may have peeped the paper, or even just the title, you may be expecting an introduction to the generalized hyper-Catalan number. The problem above introduced us to the standard Catalan number and a subset of the general hyper-Catalan’s known as the Kirkman-Cayley numbers which are special cases of a more general class of numbers sometimes called the hyper-Catalan numbers. The hyper-Catalans count (among other things) the number of ways of subdividing an n-gon into some fixed set of polygons. It’s argument can be thought of a vector that represents the number of polygons of size i that compose the larger n-gon. For example, the octagon can be composed of

\(\begin{align*} \text{6 triangles} &\rightarrow \textbf{f} = (6,0,0, ...) \\ \text{4 triangles, 1 quadrilateral} &\rightarrow \textbf{f} = (4,1,0, ...) \\ \text{3 triangles, 1 pentagon} &\rightarrow \textbf{f} = (3,0,1, ...) \\ \text{2 triangles, 2 quadrilaterals} &\rightarrow \textbf{f} = (2,2,0, ...) \\ \vdots \\ \text{1 heptagon, 1 triangle} &\rightarrow \textbf{f} = (1,0,0,0,1,0, ...) \\ \text{1 octagon} &\rightarrow \textbf{f}=(0,0,0,0,0,1,0 ...) \end{align*}\)

These are, of course, the same numbers we asked for in the extra credit

For extra credit, find a way to compute the number of final boards that are separated into exactly d₃, d₄, … , d_n polygons where d_i is the number of i-gons (polygons with i sides). For example, the figure above would be (d₃=2, d₄=1, d_n-1=0, d_n=0).

To tackle that extra-credit, it helps to look at the dual of any dissection (the faces become the vertices and faces that shared an edge become edges) . Basically, we’ll be transforming out particular subdigon into a tree and leveraging some other results from graph theory.

But I have run out of time for this write-up, and this is a pretty involved proof so I will add rest of this solution later as an addendum.

---

Addendum

By the way, I wasn’t really expecting folks to come up with this solution on their own. I tried a number of times and made minimal progress. I finally had to give up and refer to this paper by Schuetz and Whieldon. The point of including this was more so to get you thinking about the structure of the problem, doing a little bit of math, and—for the extra curious solvers—digging into some of the literature on the topic.

As we mentioned above, we’re going to convert this subdigon into a tree, which there are known formulas for counting. The tree can be constructed as follows:

The subdigon we’re be constructing the tree from.

1. draw the midpoint of every edge in the subdigon including outside edges and diagonals,

Subdigon with the midpoints added.

1. starting from the midpoint of the root edge of your subdigon (the very bottom edge), draw a line from this point to each of the midpoints of the edges that belong to the same sub-polygon that the root edge belongs to,

Starting with the bottom edge, we iteratively draw lines to the midpoints of each other edge in that particular sub-polygon. This constructs out tree.

1. This completes the tree, the image below just re-visualizes it in a more standard way.

Now the question becomes, how valid unique trees are there? Here again, the proof is rather lengthy and at the far reaches of my mathematical ability so I will point the interested reader to this paper by Kreweras if you would like the details. Long story short, the derivation yields the following expression.

\(C_{\mathbf{f}} \;=\; \frac{\bigl(2f_{2}+3f_{3}+4f_{4}+\dots\bigr)!} {\bigl(1+f_{2}+2f_{3}+3f_{4}+\dots\bigr)!\; f_{2}!\,f_{3}!\,f_{4}!\,\cdots}\)

---

Given that I’m a bit behind, I won’t be posting a new puzzle for this week (6/1). Thanks everyone for bearing with me during the delays and incomplete solutions. This project of attempting to puzzle-ify the results from A Hyper-Catalan Series Solution to Polynomial Equations, and the Geode had been challenging. I hope you all have found it interesting! Let me know in the comments if you like this kind of thing or prefer the more standard style of puzzle.