The motivation for this post is to respond to some questions about a recent video presentation titled, “Why you haven’t caught Covid-19,” presented by Anne Marie Knott, a professor in the Washington University St. Louis Olin Business School. The gist of the presentation is an argument against the “non-pharmaceutical interventions,” or stay-at-home orders, etc., in response to the current pandemic.

I am not interested in arguing about government policies, or even epidemiological models here. Frankly, this video is too easy a target. The error made in this video is a mathematical one– an error so simple, and yet so critical to the presenter’s argument, that it’s not worth bothering with the remainder of the presentation. Instead, I’d like to use this video as an excuse to rant about mathematical notation.

The problem starts at about 3:38 in the video, where the presenter attempts to analyze the COVID-19 outbreak on the aircraft carrier USS Theodore Roosevelt as a realization of the so-called “final size equation,” a model of the end-game, steady state extent of an epidemic in a closed system (since the sailors were isolated onboard the ship for a significant period of time). The final size equation is

where is the “final size” of the pandemic, or the fraction of the population that is eventually infected, and is the basic reproduction number, essentially the average number of additional people infected through contact with a person already infected, in the situation where everyone in the population is initially susceptible to infection.

As the presenter explains, there is a critical difference between a reproduction number less than one, resulting in “extinction” of the disease, and a value greater than one, resulting in an epidemic. Using the fact that 856 of the 4954 sailors onboard the Roosevelt eventually tested positive for COVID-19, corresponding to , we can estimate by solving for it in the final size equation, yielding

It’s a simple exercise to verify that the resulting estimate of is about 1.1. It’s also a relatively simple exercise to verify that this estimation technique cannot possibly yield an estimate of that is less than one.

Despite this, the presenter manages– conveniently for her argument that the contagiousness of the virus is overblown– to compute a value of of about 0.48… by computing the base 10 logarithm instead of the natural logarithm in the formula above.

It’s interesting to try to guess how the presenter managed to make this mistake. My guess is that she did this in an Excel spreadsheet; that is the only environment I know of where log(x) computes the base 10 logarithm. In any other programming environment I can think of, log(x) is the natural logarithm, and you have to work at it, so to speak, via log10(x), or log(x)/log(10), to compute the base 10 logarithm.

The mathematical notation situation is a bit of a mess as well. Sometimes I’m a mathematician, where means the natural logarithm, and any other base is usually specified explicitly as . But sometimes I am an engineer, where usually means base 10, but sometimes in a communications context it might mean base 2. Other times I am a computer scientist, where is a common shorthand for base 2, and can mean pretty much anything, including “I don’t care about the base.”

Introduction

Jacob Brazeal describes the following interesting puzzle in a recent MAA article (see reference below): starting with four rooks in the four corner squares of a chessboard, as shown in the figure below, move the rooks into the four center squares… where each single move is constrained to sliding a single rook, either horizontally along its rank or vertically along its file, as far as possible, “blocked” only by another rook or the edge of the board.

Starting configuration (left) and goal configuration (right) of sliding rooks puzzle.

Note that going in the other direction is easy– we can move the rooks from the center out to the corners in just 8 moves. But this problem is harder; it’s a nice programming exercise to determine the minimum number of moves required. The motivation for this post is to describe a slightly different approach to the problem than presented in the article, as well as a variant of the problem using queens instead of rooks that also has some interesting mathematical structure.

All of the code is available on GitHub.

Breadth-first search

We can view this problem as a directed graph, with a vertex for each possible state of the board, and a directed edge if we can move a single rook in state to obtain state . The goal is to find a minimum-length path from the starting vertex with the rooks at the corners to the goal vertex with the rooks in the center of the board.

It’s an interesting question whether there is a convenient admissible heuristic estimate of the number of moves required from a given board state, that would allow a more efficient informed search. I couldn’t come up with one; fortunately, simple breadth-first search turns out to be acceptably efficient for this problem:

from collections import deque

def bfs(neighbors, root):
    """Breadth-first search.

    Given a graph neighbors:V->V* and a root vertex, returns (p, d),
    where p[v] is the predecessor of v on the path from the root, and
    d[v] is the distance to v from the root.
    """
    queue = deque([root])
    parent = {root: None}
    distance = {root: 0}
    while queue:
        vertex = queue.popleft()
        for neighbor in neighbors(vertex):
            if neighbor not in parent:
                parent[neighbor] = vertex
                distance[neighbor] = distance[vertex] + 1
                queue.append(neighbor)
    return (parent, distance)

It turns out that a minimum of 25 moves are required to solve the puzzle. That’s a lot– too many, really, so that this would probably not be very fun to explore by hand with an actual chess board (more on this shortly). And there are other configurations that are even more difficult to reach. The board that is “farthest” from the initial rooks-in-the-corners state is shown below, requiring 32 moves to reach:

The most difficult sliding rooks configuration, requiring 32 moves to reach.

Symmetry group action

How large is the directed graph that we need to explore? The referenced article describes a graph with =635,376 vertices, one for each possible subset of four squares in which to place the rooks. This graph has some interesting structure, with one really large strongly connected component explored by the above search algorithm, containing 218,412– over one-third– of all possible board states. The remainder is made up of a large number of much smaller unreachable components: the next largest component contains just 278 vertices!

However, these numbers count configurations of rooks that are not usefully distinct. For example, the figure above shows just one of eight “different” vertices, all of which require 32 moves to reach from the initial vertex… but the other seven board states are merely rotations and/or mirror reflections of the board shown in the figure, and thus are reachable by correspondingly rotated and/or reflected versions of the same sequence of 32 moves.

In other words, let’s consider the dihedral group of symmetries of the board acting on the set of possible board states, and construct the (smaller) directed graph with a vertex for each orbit of that group action.

A standard trick for implementing this approach is to represent each orbit by one of its elements, chosen in some natural and consistent way; and a standard trick for making that choice is to impose some convenient total order on the set, and choose the least element of each orbit as its representative. In the case of this problem, as we encounter each board state v during the search, we “rename” it as min(orbit(v)), the lexicographically least tuple of rotated and/or reflected coordinates of the rook positions:

def orbit(pieces):
    """Orbit of dihedral group action on rooks on a chess board."""
    for k in range(4):
        yield pieces
        yield tuple(sorted((n - 1 - x, y) for (x, y) in pieces))    # reflect
        pieces = tuple(sorted((n - 1 - y, x) for (x, y) in pieces)) # rotate

This search space is almost– but not quite– eight times smaller. From the initial rooks-in-the-corners board state, we can reach 27,467 configurations unique up to rotations and reflections, out of a total of 79,920 possible configurations. We can compute the latter number without actually enumerating all possible board states: the cycle index of the dihedral group acting on the squares of an board (assuming is even) is

and the number of possible board states with rooks is

Sliding queens instead of rooks

Finally, I think perhaps a more “fun” variant of this problem is to consider four queens in the corners, and try to move them to the four center squares as before, using the same “maximal” moves, but allowing diagonal moves as well as horizontal and vertical. This is more tractable to solve by hand, requiring only 12 moves to complete.

And the structure of the corresponding graph is also rather interesting: the large connected component is even larger, so that we can now reach 77,766 of the 79,920 possible configurations of four queens… but the remaining 2,154 configurations are all singleton components! That is, from any one of these 2,154 “lone” configurations, we can move into the large component with just a single move, and from there reach any of those 77,766 configurations… but we can’t get back, nor can we reach any of the other 2,153 lone unreachable configurations!

This was interesting enough that I wondered if it was true in general for other board sizes. It’s trivially true for 2×2 and 4×4 (since there are no unreachable board states), as well as 6×6, 8×8, and even 10×10… but unfortunately the pattern does not continue; the 12×12 board has larger-than-singleton connected components not reachable from the initial queens-in-the-corners state.

Reference:

1. Brazeal, J., Slides on a Chessboard, Math Horizons, 27(4) April 2020, p. 24-27 [link]