![](\"https:\/\/i0.wp.com\/blogs.ams.org\/phdplus\/files\/2018\/07\/Punch_card_sorter.jpg?resize=640%2C480\")
The IBM card sorter! Why is this relevant? See exciting puzzle below. \u00a0 Photo by waelder [GFDL (http:\/\/www.gnu.org\/copyleft\/fdl.html), CC-BY-SA-3.0 (http:\/\/creativecommons.org\/licenses\/by-sa\/3.0\/) or CC BY 2.5 (https:\/\/creativecommons.org\/licenses\/by\/2.5)], from Wikimedia Commons<\/p><\/div>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.<\/p>\n
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).\u00a0And 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<\/a><\/em>, (volume 2 also out now)<\/a>that probability, Latin squares, and graph theory were all born of recreation. Nothing useful there\u2026<\/p>\n I feel like a jerk even bringing it up after bemoaning the pressures of \u201cthe machine\u201d, but recreational math can even pay off in papers, even if it doesn\u2019t 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. \u00a0An 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\u2019s 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.\u00a0 Each person would start working on their own quilt, then pass it on to someone else in the group.\u00a0 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\u2019t seem to make this work for the group of five.\u00a0 There was a good reason Judy couldn\u2019t do it: turns out there is no way to do this for five people. Oh, the fun I had proving that. Though I didn\u2019t 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.\u00a0 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\u2019s email.<\/p>\n 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\u2019s Math Fun Facts<\/a>) showed in 1992, seven shuffles is good.\u00a0 But these are not \u201cperfect shuffles\u201d, i.e. perfect alternate interleaving for the cards in two halves of the deck.\u00a0 Perfect shuffles insert no entropy, because they are fully deterministic.\u00a0 In fact, 8 perfect shuffles of a deck will return it to its original order, as shown by Diaconis, Graham, and Kantor<\/a> in 1983.<\/p>\n But again, you don’t have to write a paper about shuffling to get a lot of joy out of thinking about it. \u00a0Here’s a puzzle for you. \u00a0Like 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<\/a>\u00a0newsletter puzzle column, who got it from Stan Wagon<\/a>, who got it from Colin McGregor<\/a>. In any case, let\u2019s 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\u2014you 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?\u00a0 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.<\/p>\n Okay, so that might be kind of hard to think about all at once.\u00a0 So how about a warm up:<\/p>\n Q:<\/strong> How many shuffles are required to completely reverse the order of the deck?<\/p>\n A:<\/strong> I\u2019ll 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\u2019s 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.\u00a0 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.<\/p>\n 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 \u201cphantom cards\u201d.<\/p>\n Okay, so are you ready for the better answer?\u00a0 Larry Carter<\/a> explained it to me in about 30 seconds by explaining how an old IBM card sorter<\/a> worked. These machines were physical implementations of radix sort<\/a>.\u00a0 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.\u00a0 A punch is a hole where you could put a rod through and pick up the card.\u00a0A slot would be made by taking a punch and snipping up to the edge of the card, so you couldn\u2019t pick up the card with a rod anymore.\u00a0 For every 1 in the binary expansion there is a slot, and every 0 is a punch.\u00a0 To sort the cards, line them all up.\u00a0 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.\u00a0 Bring these cards to the front of the stack.\u00a0 Then repeat with the next position, and keep repeating until you have gone through all the log(n) positions.\u00a0 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!\u00a0 So it can take at most log(n) steps to create any permutation of the n cards.<\/p>\n Alright, enough puzzle for one blog. \u00a0Hope everyone is enjoying summer, and finding plenty of great puzzles without my help. \u00a0What experiences have you had with recreational mathematics?\u00a0 Please share in the comments!<\/p>\n