The Mathematics of Various Entertaining Subjects volume 2
Recreational mathematics, puzzles and games have by now a long tradition and there are many books, papers, and columns devoted to these topics. Many love the challenges of the puzzles and games and solving the problem is rewarded with a dopamine rush when a solution is finally reached. They love it as a pastime or a hobby. However, solving the problem in a systematic way may require some more serious mathematical research. With the increasing popularity of recreational mathematics new mathematical challenges emerged which transcended the recreational aspect. In fact, historically speaking, some well established branches of mathematics like for example probability theory and graph theory, grew out of trying to solve a recreational problem. Another example mentioned by the editors in their foreword is the development of a theory for combinatorial games which have led Elwyn Berlekamp, John Conway and Richard Guy to compiling their multivolume work Winning Ways for Your Mathematical Plays.
In 2013 the first MOVES (Mathematics Of Various Entertaining Subjects) conference was organized, which was the start of a series of biennial meetings with an increasing number of participants. This is volume two, a sequel to the book with the same title. The first book can be considered as a kind of proceedings for the 2013 MOVES conference and the present one collects nineteen research papers most of which were presented at the 2015 conference. Berlekamp, Conway and Guy were all three participating as invited speakers then. The difference with the usual books collecting papers about this subject is that here the authors have included the "serious mathematics" behind the recreational aspect. The contributions are organized in five different parts: (1) Puzzles and brain teasers, (2) Geometry and topology, (3) Graph theory, (4) Games of chance, and (5) Computational complexity. Those familiar with recreational mathematics will recognize that most of the problems they know will fall under one (or more) of these headings. One may miss logic as a popular subject, but that falls under the first category. Among the contributors are some well known names:. R. Guy, J. Rosenhouse, P. Stockmeyer, E. and M. Demaine, J. Conway, N. Elkies, and many others.
In order to give an idea of the type of contributions, let me discuss some examples. I will pick one from each of the five parts. In the part about Puzzles and brain teasers, Tanya Khovanova wrote about Dragons and kasha. The setting is as follows: On each face of a cube sits a four armed dragon with a bowl of kasha. Each minute they grab one fourth of the kasha from the bowls of their four neighbours. Given an initial distribution of kasha in the six bowls, what is the asymptotic distribution? The problem is not difficult to solve and the result is that each dragon will end up with the same amount of kasha, whatever the initial distribution. The nice thing about the paper is that it relates the solution to Markov chains, random walks, eigenvalue problems, but the real purpose is by defining a "stealing operator" and replacing kasha by complex numbers, this can be linked to intertwining operators, group actions, and group representations. The added value of this paper is that such abstract concepts are introduced in an easily accessible and playful way. This is an example of a paper that is playful and does not require much mathematical skills from the reader.
Jill Bigley Dunham and Gwyneth R. Whieldon have a paper in the Geometry and topology part on counting the solutions to a paper cutting and folding problem proposed by Martin Gardner. Given is a square piece of paper subdivided by a regular 3 x 3 gird. It is black on one side and white on the other. Cutting and folding is allowed only along grid lines, and the cutting should not result in disjoint pieces. The challenge is by cutting and folding to wrap this around a 1 x 1 cube showing black faces on all sides. The problem is not so difficult to solve, but many much more complicated variants can be imagined. The way in which the nine grid squares are connected can be represented by a graph: each 1 x 1 square is a vertex and vertices are connected by an edge when the squares are connected. A cut between two neighbouring grid squares corresponds to removing an edge in the graph. Cutting and folding structures and wrapping sequences can be enumerated and programmed. Because the number of possibilities, given the constraints, is not too large, all possibilities can be checked. By this enumeration, a theorem can be proved: A wrapping solution exists for a cutting pattern if and only if there exists a non-self-intersecting sequence of four moves to adjacent squares starting at the centre square. Some patterns allowed several wrappings, some of them are mono-coloured other mix black and white. Thus a complete enumeration of all possible solutions and a list of cutting patterns that do not allow any solution can be listed by a computer program.
More graph theory in the paper by Dominic Lanphier from the part on Graphs. Suppose you are attending a sequential duel, which means that duelist 1 aims at duelist 2 and fires. If he misses (with probability 1 − p, then number 2 fires at number 1 and hits with probability q. If he misses, the first duelist fires again etc. The problem is to find out which one has the most chance to survive. The problem can be made more complicate if more than two shooters fire at each other in some order, which could be cyclic or not. What if after one has been shot, the survivors have to continue until there is only one survivor. If you are one of the shooters in a large pool, you better learn the necessary statistics, generating functions and asymptotics discussed in this paper to maximize your chance to survive. It requires some more mathematics and computations than the two previous examples, but it is still very accessible for anyone who would need it. More advanced mathematics is needed for the paper by Noam Elkies from the same part in which the number of crossings in a complete graph is computed. If in a planar graph every vertex is connected to every other vertex, the edges will necessarily cross a minimal number of times. Counting these crossings in not so difficult when it concerns plane graphs, but it is less trivial if these graphs live on another topology like a sphere, a toroid, a projective plane, a Moebius strip,...
When in part four chance and probability become an essential element in the game, then dice naturally come to the foreground. They literally do in the first contribution of this part authored by Robert Bosch, Robert Fathauer and Henry Segerman. If it is true that for fair dice every face has an equal chance to land on top, then we could number faces in any configuration. In practice however they are always numerically balanced, that is they always have opposite faces numbered (1,6), (2,5) and (3,4). In the paper this phenomenon is investigated for the 20-sided (icosahedral) dice where opposite sides sum to 21. Each of the 12 vertices is common to five triangular faces. Optimal numerical balancing could consider not only the opposite sides, but also the vertex sum (the sum of the 5 adjacent faces), or the face sum (the sum of the 3 adjacent faces) with or without including the number on the face itself, or the sum of the equatorial bands (the sum of the 10 faces on the equator if two opposite vertices are selected as north and south pole). Solving such problems requires integer constrained programming to find a solution and is related to magic squares. Generalisations from d20 to d30 and d120 dice are also considered.
In the computational complexity part, we find a relatively long paper by Aviv Adler, Erik Demaine and others who give a proof of the fact that Clickomania is a hard problem even if there are only two colours and two columns. The game is a popular computer game that starts with a rectangular grid tiled with coloured squares. With one click you can remove a connected structure of tiles with the same colour. The empty space is filled with tiles higher up in the same column. Isolated singletons can not be removed and empty columns collapse so that their left and right neighbours join. Either the target is to remove all tiles or to get the highest possible score. Each click adds to your score which is about the square of the number of tiles you remove in that click. The theorem says that if the target is to remove all tiles, then this is an NP-complete problem, unless we have the trivial situation of only one column and one colour. The score variant is NP-complete if there is more than one column and more than one colour, and trivial (and hence in complexity class P) if there is only one colour. Proving this theorem requires first of all a speed course in complexity theory to define the terminology and the process of reduction has to be explained, that is how a problem, known to be NP-complete, can be transformed (in polynomial time) into another one, in order to conclude that the latter will be NP-complete too. Given all this basic material, then the proof itself is far from trivial. And if the problem is indeed NP-complete, then one still wants to find a good approximation. Such approximations and variants are also discussed and, for the ambitious reader, there are still many open problems left to be solved.
It should be clear from this selection that the papers cover not only a very diverse set of problems, but also that they are not always at the same level of complication. Nevertheless all authors have attempted to reach a general public with a certain mathematical training. We could conclude that this is a book on recreational mathematics for the mathematician. This does indeed reflect the audience that attended the MOVES conference in 2015. I suppose these participants will be interested in a copy of this book but even more so those who could not be there but would have loved to. They can still get an idea of what kind of problems were discussed.