In life on the job market and pre-tenure academia, it can seem that no math is worth doing unless it results in a paper, preferably a very fashionable and serious one. This can be a real soul crusher when the inevitable setbacks occur. Pressure (internal and external) to produce serious mathematics, in order to build the CV, in order to get or keep a good job, can sometimes make the discipline feel like a monstrous machine instead of a wonderland. In that setting, it feels almost subversive to pursue problems that are just straight up entertaining, that may have been solved before but are truly fun to think about. So today I focus on this joyful act of rebellion against the machine: recreational mathematics.

Puzzles were my gateway drug to hard mathematics. They have also served to reinvigorate my interest in math when my research seemed too hard and when work that I thought was serious and useful suddenly looked trivial and unfashionable. Recreational math reminds me why I bothered doing this in the first place. Half an hour with a Martin Gardner book is better than a nap when I need a reset (and a nap is pretty good). And math packaged as a puzzle can certainly have application. Jennifer Beineke and Jason Rousenhouse remind us in the preface to the excellent 2015 collection The Mathematics of Various Entertaining Subjects: Research in Recreational Math, (volume 2 also out now)that probability, Latin squares, and graph theory were all born of recreation. Nothing useful there…

I feel like a jerk even bringing it up after bemoaning the pressures of “the machine”, but recreational math can even pay off in papers, even if it doesn’t become the foundation of a whole new branch of mathematics. Additionally, recreational mathematics problems make great gateways to research mathematics for undergraduates who might not have the mathematical tools to attack more formally phrased problems.  An example from my life: a few years ago, when I was in my second visiting position and felt extraordinarily stuck on two of my main research problems, I got an email from Judy Gilmore (my friend’s mom) about a problem she was having in her quilting circle. She and her four friends wanted to make quilts together in a sort of round robin.  Each person would start working on their own quilt, then pass it on to someone else in the group.  That person would add a border to the quilt, and pass it on again, until everyone had added a border on to every quilt. Judy wanted to set it up so that each person passed a quilt on to everybody else at some point during the process, but she couldn’t seem to make this work for the group of five.  There was a good reason Judy couldn’t do it: turns out there is no way to do this for five people. Oh, the fun I had proving that. Though I didn’t have the vocabulary or context to say it at the time, the fact that this is impossible is equivalent to the fact that there is no 5 by 5 row complete latin square.  My friend Katie Haymaker and I went on to look into the known and unknown aspects of row complete latin squares, essentially just for fun. We rediscovered a lot of known results and put together the pieces for a small extension of one, and eventually wrote a mostly expository paper about these objects and the quilt problem for Mathematics Magazine. This problem has given me a whole family of great research problems suited for undergraduate students who may not have had many upper-level math classes. Five years later, my students and I are still working on the questions that began with Judy’s email.

More examples of recreational math making papers: the whole family of puzzles that are based on shuffling cards. You could start with a pretty simple question (that a lot of people have, based on how quickly it comes up as an option when you start typing the query into Google): how many shuffles does it take to really randomize a deck of cards? As Diaconis and Bayer (here explained by Francis Su in Harvey Mudd’s Math Fun Facts) showed in 1992, seven shuffles is good.  But these are not “perfect shuffles”, i.e. perfect alternate interleaving for the cards in two halves of the deck.  Perfect shuffles insert no entropy, because they are fully deterministic.  In fact, 8 perfect shuffles of a deck will return it to its original order, as shown by Diaconis, Graham, and Kantor in 1983.

But again, you don’t have to write a paper about shuffling to get a lot of joy out of thinking about it.  Here’s a puzzle for you.  Like any good story, a quality puzzle gets passed around and changed, so can be hard to source. I got this from Joe Buhler, recreational mathematician extraordinaire and co-writer of the MSRI Emissary newsletter puzzle column, who got it from Stan Wagon, who got it from Colin McGregor. In any case, let’s say that a shuffle is any way of dividing the deck into two pieces and interleaving the cards so that all the cards in each piece stay in order relative to one another. Now say that you have a deck of n cards, and that you are a master shuffler—you can physically accomplish any shuffle with your deck of cards. What is the maximum number of shuffles required for the most efficient algorithm to put the deck in any requested order?  Every permutation will have some most efficient way to accomplish it, so we are basically looking for the worst case of this most efficient way over all permutations of n cards.

Okay, so that might be kind of hard to think about all at once.  So how about a warm up:

Q: How many shuffles are required to completely reverse the order of the deck?

A: I’ll first share my wordy answer to this simpler problem with you, then share someone else’s extremely elegant solution to the general problem. I spent a few very fun hours thinking about this, and here’s what I came up with: For n=2^k, you do the simplest thing possible–divide into two parts, and perfectly interleave the parts with the better card on top at each step. Repeat for a total of k shuffles to get the reversed deck. This is not so hard to prove (let’s call it an exercise!). If n is not a power of 2, you should be able to do this separately (ignoring the other cards) for the number of cards represented by each 1 in the binary expansion of n.  When each of these chunks are sorted, for every 1 in the binary expansion of n, we’ll have several chunks of cards such that the cards in each chunk are in order relative to one another. We can now interleave each smaller piece successively with the largest power of 2 part of the deck. So, this should take between log(n) and 2*log(n) shuffles, depending on the binary expansion of the number. I think the worst case scenario should be something like n=2^k-1.

After thinking about this for a while and talking with friends, I realized that you should really be able to do it in the ceiling of log(n) shuffles, because if 2^(k-1)<n<2^k, then you could just pretend like there were 2^k cards to sort, working with 2^k-n “phantom cards”.

Okay, so are you ready for the better answer?  Larry Carter explained it to me in about 30 seconds by explaining how an old IBM card sorter worked. These machines were physical implementations of radix sort.  In the machine, imagine that you start with a stack of n numbered cards in any order. The binary expansion of each number is at the top of the card, and this expansion is encoded using slots and punches.  A punch is a hole where you could put a rod through and pick up the card. A slot would be made by taking a punch and snipping up to the edge of the card, so you couldn’t pick up the card with a rod anymore.  For every 1 in the binary expansion there is a slot, and every 0 is a punch.  To sort the cards, line them all up.  Starting with the leftmost position (the ones place), slide a rod through the stack of cards and pick up all of the cards with a 0 in this position.  Bring these cards to the front of the stack.  Then repeat with the next position, and keep repeating until you have gone through all the log(n) positions.  Like magic, the cards will be perfectly sorted. All cards with 0 in the highest position will be in front of cards with a 1 in the highest position, and all cards with 0 in both highest positions will be in front of these, and so on. The genius idea is that because you could go from any permutation to sorted in log(n) steps, you could imagine just reversing these steps as shuffles!  So it can take at most log(n) steps to create any permutation of the n cards.

Alright, enough puzzle for one blog.  Hope everyone is enjoying summer, and finding plenty of great puzzles without my help.  What experiences have you had with recreational mathematics?  Please share in the comments!