Social distancing in Catan and on the chessboard

This afternoon, I dropped by the MAA Contributed Paper Session on Recreational Mathematics: Puzzles, Card Tricks, Games, and Gambling. The first two talks focused on the board game Catan and chess, taking inspiration from social distancing in a way only mathematicians can.

Catan lends itself to fun combinatorics: The board consists of 19 hexagonal resource tiles, 18 number tokens placed on the resource tiles, and 9 ports. The arrangement of these components is randomized for each game. As my family members often comment when we play Catan, part of the fun comes from the fact that the board is different every time. For mathematicians, it’s natural to ask how many arrangements of the board are possible. 

Since each game of Catan involves randomizing the locations of the resource tiles, number tokens, and ports, it lends itself naturally to fun combinatorics.

In a 2019 paper, Jathan Austin, Brian Kronenthal, and Susanna Miller computed the number of nonequivalent boards (boards that cannot be transformed into each other via rotations and reflections), arriving at a staggering $1.5404939\times {10}^{28}$ possibilities. But this computation ignored a subtle rule of the game of Catan: four of the number tokens are red, and no two red tokens can be placed on adjacent resource tiles. In the language of our post-2020 world, the red tokens must be “socially distanced.”

In their talk today, “Counting Socially-Distanced Catan Configurations,” Austin, Kronenthal, and Miller sketched out their approach to the refined problem of counting all legal (socially distanced) arrangements of the Catan board. They viewed the board as a trio of concentric rings—the center tile, the middle ring of six tiles, and the outer ring of 12 tiles—which broke the possible configurations of the red tokens into five cases. From there, the counting arguments needed for each case were fairly straightforward, involving simple combinations and the use of the principle of inclusion-exclusion.

The number of allowable configurations of the red tokens can be counted by considering five cases. In each ordered triple in the leftmost column, the first entry is the number of red tokens on the center tile, the second is the number of red tokens on the middle ring, and the third is the number of red tokens on the outer ring.

It turns out that there are 532 possible configurations of the red tokens. Combining this result with techniques from their earlier work, the speakers arrived at a total of $2.1144034\times {10}^{27}$ legal configurations of the Catan board. If you played one game of Catan every second, you would need 4.9 trillion lifetimes of the universe to get through every socially distanced configuration. 

As a side note, what’s the probability that a Catan board arrangement chosen completely at random will satisfy the red token social-distancing rule? Dividing the number of legal configurations by the total number of configurations, you get about 0.137. 

Satisfied that my relatives are right when they say that every game of Catan is different, I moved on to the next talk, “Social Distancing on the Chessboard” by Doug Chatham of Morehead State University. On an otherwise empty $n\times n$ chessboard, a rook or a queen can move between any two squares in at most two moves. But if you add some pawns to the board, you can cause certain squares to be separated by a larger number of moves. 

Chatham translated this situation into the language of graph theory. A given arrangement of pawns on an $n\times n$ chessboard determines a graph whose vertices are empty squares and whose edges are the pairs of squares $(A,B)$ for which a queen can move directly from $A$ to $B$. Then the distance between squares $A$ and $B$ is the minimum length of a queen’s path from $A$ to $B$, and the diameter of a given queen graph is the maximum distance between two squares, running through all pairs of squares on the chessboard.

A chessboard with pawns on some squares can be thought of as an undirected graph.

With this set-up, Chantham asked the following question: How many pawns $p$ are needed so that some placement of those pawns on an empty $n\times n$ chessboard produces a board with a queens graph of diameter $d$? (He also studied the same question for rooks.)

As those readers familiar with graph theory will know, the structure of an undirected graph can be encoded in an adjacency matrix where each entry corresponds to a pair of vertices. A 1 represents an edge connecting the vertices, and a 0 represents no edge connecting them. From a graph’s adjacency matrix $A$, it’s easy to calculate the diameter of the graph: It’s the minimum $k$ for which $I+A+A^2+\cdots +A^k$ has no zero entries.

Chantham used a simple algorithm to have a computer find the value of $p$ (which he called the “diameter separation number”) for given values of $n$ and $d$. The results are below.

The (queen) diameter separation number for some values of n and d.

Chantham also stated (without proof) two propositions. The first was that for any $n\ge 4$, only one pawn (when properly placed) is needed to yield a diameter separation number of 3. The second was that for any $n\ge 4$, three pawns (when properly placed) yield a diameter separation number of 4.

Left: a board with one pawn and a diameter separation number of 3. Right: a board with three pawns and a diameter separation number of 4.

The graph theory of queens and pawns on a chessboard is rich with variations to explore. What happens to the diameter separation number for fixed $d$ as $n$ increases? What happens if the board is rectangular but not square, or if we use bishops instead of queens or rooks?

In neither talk did the speakers address why anyone should care about their results. To an audience of fellow math fans, it’s obvious: The problem was there and it could be solved using math, so the process of arriving at the solution is inherently interesting. But I would add another reason why recreational problems with no apparent applications to “serious” math are worthwhile. 

A lot of people enjoy Catan or chess—including many people who don’t like math (or at least think they don’t like math). Fun puzzles like the social-distancing problems discussed today could be great educational and outreach tools that connect math with something that people already understand and enjoy. The Catan puzzle is an unconventional combinatorics problem accessible to students who are learning about counting and combinations. The chessboard puzzle offers a hands-on exploration of graph theory, with plenty of room for people to form their own conjectures and try to prove them or find counterexamples. 

After the JMM session recordings are posted, I hope to go back and watch some of the talks on recreational math that I missed and see what other education and outreach activities they inspire.