# Firing games and greedoid languages

In an earlier post, I described the dollar game played on a finite graph $G$, and mentioned (for the “borrowing binge variant”) that the total number of borrowing moves required to win the game is independent of which borrowing moves you do in which order. A similar phenomenon occurs for the pentagon game described in this post.

In this post, I’ll first present a simple general theorem due to Mikkel Thorup which implies both of these facts (and also applies to many other ‘chip firing games’ in the literature). Then, following Anders Björner, Laszlo Lovasz, and Peter Shor, I’ll explain how to place such results into the context of greedoid languages, which have interesting connections to matroids, Coxeter groups, and other much-studied mathematical objects.

# Some Mathematical Gems from John Conway

John Horton Conway died on April 11, 2020, at the age of 82, from complications related to COVID-19. See this obituary from Princeton University for an overview of Conway’s life and contributions to mathematics. Many readers of this blog will already be familiar with the Game of Life, surreal numbers, the Doomsday algorithm, monstrous moonshine, Sprouts, and the 15 theorem, to name just a few of Conway’s contributions to mathematics. In any case, much has already been written about all of these topics and I cannot do justice to them in a short blog post like this. So instead, I’ll focus on describing a handful of Conway’s somewhat lesser-known mathematical gems.

To motivate the discussion, consider the following question. Let $F = \{ 0,1,4,9,16,25,\ldots \}$ be the sequence of squares, and let $G = \{ 2,3,5,6,7,8,10,\ldots \}$ be its complement in ${\mathbb N} = \{ 0,1,2,3,\ldots \}$. What is the $n^{\rm th}$ term of the sequence $G$? In other words, can we give a formula for the $n^{\rm th}$ non-square? One might imagine that no simple formula exists, but in fact Lambek and Moser showed that the $n^{\rm th}$ non-square is equal to $n + \{ \sqrt{n} \}$, where $\{ x \}$ denotes the closest integer to $x$. Similarly, if $T = \{ 0,1,3,6,10,\ldots \}$ denotes the set of triangular numbers, the $n^{\rm th}$ element of the complement of $T$ is equal to $n + \{ \sqrt{2n} \}$.