{"id":89,"date":"2021-01-07T21:43:57","date_gmt":"2021-01-07T21:43:57","guid":{"rendered":"http:\/\/blogs.ams.org\/jmm2021\/?p=89"},"modified":"2021-01-08T16:08:45","modified_gmt":"2021-01-08T16:08:45","slug":"social-distancing-in-catan-and-on-the-chessboard","status":"publish","type":"post","link":"https:\/\/blogs.ams.org\/jmm2021\/2021\/01\/07\/social-distancing-in-catan-and-on-the-chessboard\/","title":{"rendered":"Social distancing in Catan and on the chessboard"},"content":{"rendered":"
<\/div>

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 <\/span>Catan<\/span><\/i> and chess, taking inspiration from social distancing in a way only mathematicians can.<\/span><\/p>\n

Catan<\/span><\/i> 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 <\/span>Catan<\/span><\/i>, part of the fun comes from the fact that the board is different every time. For mathematicians, it\u2019s natural to ask how many arrangements of the board are possible.\u00a0<\/span><\/p>\n

\"Screenshot

Since each game of Catan involves randomizing the locations of the resource tiles, number tokens, and ports, it lends itself naturally to fun combinatorics.<\/p><\/div>\n

In a 2019 paper<\/a>, 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\\times10^{28}$ possibilities. But this computation ignored a subtle rule of the game of <\/span>Catan<\/span><\/i>: 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 \u201csocially distanced.\u201d<\/span><\/p>\n

In their talk today, \u201cCounting Socially-Distanced Catan Configurations,\u201d Austin, Kronenthal, and Miller sketched out their approach to the refined problem of counting all legal (socially distanced) arrangements of the <\/span>Catan<\/span><\/i> 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.<\/span><\/p>\n

\"A

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.<\/p><\/div>\n

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 <\/span>Catan<\/span><\/i> board. If you played one game of <\/span>Catan<\/span><\/i> every second, you would need 4.9 trillion lifetimes of the universe to get through every socially distanced configuration.\u00a0<\/span><\/p>\n

As a side note, what\u2019s the probability that a <\/span>Catan<\/span><\/i> 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.\u00a0<\/span><\/p>\n

Satisfied that my relatives are right when they say that every game of <\/span>Catan<\/span><\/i> is different, I moved on to the next talk, \u201cSocial Distancing on the Chessboard\u201d 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.\u00a0<\/span><\/p>\n

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\u2019s 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.<\/span><\/p>\n

\"An

A chessboard with pawns on some squares can be thought of as an undirected graph.<\/p><\/div>\n

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.)<\/span><\/p>\n

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\u2019s adjacency matrix $A$, it\u2019s easy to calculate the diameter of the graph: It’s the minimum $k$ for which $I+A+A^2+\\dots + A^k$ has no zero entries.<\/span><\/p>\n

Chantham used a simple algorithm to have a computer find the value of $p$ (which he called the \u201cdiameter separation number\u201d) for given values of $n$ and $d$. The results are below.<\/span><\/p>\n

\"Table

The (queen) diameter separation number for some values of n<\/em> and d<\/em>.<\/p><\/div>\n

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

\"Two

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.<\/p><\/div>\n

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?<\/span><\/p>\n

In neither talk did the speakers address why anyone should care about their results. To an audience of fellow math fans, it\u2019s 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 \u201cserious\u201d math are worthwhile.\u00a0<\/span><\/p>\n

A lot of people enjoy <\/span>Catan<\/span><\/i> or chess—including many people who don\u2019t like math (or at least think they don\u2019t 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 <\/span>Catan<\/span><\/i> 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.\u00a0<\/span><\/p>\n

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.<\/p>\n","protected":false},"excerpt":{"rendered":"

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 … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":650,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-89","post","type-post","status-publish","format-standard","hentry","category-welcome"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/pcvtdI-1r","_links":{"self":[{"href":"https:\/\/blogs.ams.org\/jmm2021\/wp-json\/wp\/v2\/posts\/89","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ams.org\/jmm2021\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ams.org\/jmm2021\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/jmm2021\/wp-json\/wp\/v2\/users\/650"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/jmm2021\/wp-json\/wp\/v2\/comments?post=89"}],"version-history":[{"count":8,"href":"https:\/\/blogs.ams.org\/jmm2021\/wp-json\/wp\/v2\/posts\/89\/revisions"}],"predecessor-version":[{"id":102,"href":"https:\/\/blogs.ams.org\/jmm2021\/wp-json\/wp\/v2\/posts\/89\/revisions\/102"}],"wp:attachment":[{"href":"https:\/\/blogs.ams.org\/jmm2021\/wp-json\/wp\/v2\/media?parent=89"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ams.org\/jmm2021\/wp-json\/wp\/v2\/categories?post=89"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ams.org\/jmm2021\/wp-json\/wp\/v2\/tags?post=89"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}