Selected Papers on Fun and Games

by Donald E. Knuth (Stanford, California: Center for the Study of Language and Information, 2010), xvii+741pp.
(CSLI Lecture Notes, no. 192.)
ISBN 978-1-57586-585-0 (cloth), 978-1-57586-584-3 (paperback)

This is the eighth in a series of eight volumes that contain archival forms of my published papers, together with new material. (The first book in the series was Literate Programming; the second was Selected Papers on Computer Science; the third was Digital Typography; the fourth was Selected Papers on Analysis of Algorithms; the fifth was Selected Papers on Computer Languages; the sixth was Selected Papers on Discrete Mathematics; the seventh was Selected Papers on Design of Algorithms.) The Fun and Games volume is characterized by the following remarks quoted from its preface.

I've never been able to see any boundary between scientific research and game-playing. ... The topics treated here were often inspired by patterns that are visually compelling, or by paradoxical truths that are logically compelling, or by combinations of numbers and/or symbols that fit together just right. These were papers that I couldn't not write.
I believe that the creation of a great puzzle or a great pattern is a scholarly achievement of great merit, an important contribution to world culture, even though the author of such a breakthrough is often an amateur who has no academic credentials. Therefore I'm proud to follow in the footsteps of the pioneers who have come up with significant new “mind-benders” as civilization developed.
Many years ago I wrote an essay that asked “Are toy problems useful?” [reprinted as Chapter 10 in Selected Papers on Computer Science] in which I discussed at some length my view that students are best served by teachers who present them with well-chosen recreational problems. And I've carried on in the same vein ever since, most recently on pages 7--9 of The Art of Computer Programming, Volume 4A, in a section entitled “Puzzles versus the real world.”
Thus it's not surprising that many of the chapters in the present book have resulted from my attempts to answer puzzling questions that have no immediately obvious relation to any practical applications of mathematics or of computer science. Or that sometimes I had an urge to embellish or extend the answers to classical enigmas that had previously been resolved. And of course I've also come up with a few new puzzles in the process, several of which I don't yet know how to tackle.
In other words, I believe that diversions are useful, and I've tried in this book to provide useful diversions that meet high standards of quality. Of all the papers that I've written, the ones included here have given me the most personal pleasure---in fact, sheer joy at times! The various chapters include my earliest work as well as my latest. Many of them have an autobiographical flavor, because they're associated with some of the most memorable moments of my life.
Actually I've had great fun with these papers not only when writing them but also when revisiting them, as I was preparing this collection. Now, as I write this preface, I can't help but celebrate the fact that I've finally been able to put together the book that I've always dreamed of writing, a book that best expresses the quirky things that I enjoy. I'm quite sure that this book isn't for everybody; but if you're anything like me, you will enjoy it too, at least in part.

... And then the preface continues by describing the other chapters, which can be summarized more succinctly by quoting from the hype on the back cover:

The present volume, which is the eighth and final book in Knuth's series of collected papers, is the one that he has saved up for dessert: It's a potpourri devoted to recreational aspects of mathematics and computer science, filled with the works that gave him most pleasure during his 50-year career. Here you'll find puzzles, paradoxes, and appealing patterns: visual, numerical, and musical.
Nearly fifty of Knuth's works are collected in this book, beginning with his famous first paper in MAD Magazine, and containing several similarly delightful spoofs written "in a jugular vein." Knuth's well-known introduction to the "dancing links" algorithm for combinatorial searches is accompanied by several chapters that shed new light on the age-old problem of knight's tours on a chessboard. There are chapters about word games, computer games, and even basketball, together with topics of modern folk culture such as traffic signs, license plates, and geek art. ... All are found here, together with more than 700 newly created illustrations.

Here's the table of contents:

  1. The potrzebie system of weights and measures [P1]
  2. Official tables of the potrzebie system
  3. The revolutionary potrzebie [R4a]
  4. A MAD crossword [rejected sequel to P1]
  5. Counterexample to a statement of Peano
  6. The complexity of songs [Q48]
  7. TPK in INTERCAL
  8. Math ace: The plot thickens [R4c,d]
  9. Billiard balls in an equilateral triangle [P14]
  10. Representing numbers using only one 4 [P18]
  11. Very magic squares [P31]
  12. The Gamov--Stern elevator problem [P35]
  13. Fibonacci multiplication [P117]
  14. A Fibonacci-like sequence of composite numbers [P119]
  15. Transcendental numbers based on the Fibonacci sequence [P13]
  16. Supernatural numbers [P95]
  17. Mathematical vanity plates [Q210]
  18. Diamond signs
  19. The orchestra song
  20. Gnebbishland
  21. A carol for advent
  22. Randomness in music
  23. Basketball's electronic coach
  24. The triel: A new solution [P58]
  25. The computer as Master Mind [P81]
  26. Move it or lose it [Q223]
  27. Adventure
  28. Ziegler's Giant Bar
  29. Th5E4 CH3EmIC2Al2 Ca3P4Er [R4b]
  30. N-ciphered texts [Q99]
  31. Disappearances [Q54]
  32. Lewis Carroll's WORD-WARD-WARE-DARE-DAME-GAME [Q51]
  33. Blood, sweat, and tears [Q52]
  34. Biblical ladders [Q172]
  35. ETAOIN SHRDLU non-crashing sets [Q139]
  36. Quadrata obscura (Hidden Latin squares)
  37. 5x5x5 word cubes by computer [Q131]
  38. Dancing links [P159]
  39. Nikoli puzzle favors
  40. Uncrossed knight's tours [Q23]
  41. Celtic knight's tours
  42. Long and skinny knight's tours
  43. Leaper graphs [P147]
  44. Number representations and dragon curves [P37]
  45. Mathematics and Art: The dragon curve in ceramic tile [P59]
  46. Christmas cards
  47. Geek art
  48. Remembering Martin Gardner [Q228]
  49. An earthshaking announcement [Q227]

(Numbers like P1 and Q99 in this list refer to the corresponding papers in my list of publications. Seventeen of these chapters are published here for the first time; fourteen others appeared in publications of limited circulation and are difficult to find in libraries.)

This book can be ordered from the publisher (CSLI), and also from the distributor (University of Chicago Press).

Links

Several chapters of the book refer to Internet pages for more detailed information. I've copied the relevant links here so that you can simply click instead of typing a long URL:

Errata

As usual, I promise to deposit 0x$1.00 ($2.56) to the account of the first person who finds and reports anything that remains technically, historically, typographically, or politically incorrect.

Errata to the First Printing (2010)

Here is a list of all nits that have been picked so far in the first printing (2010); an asterisk (*) marks technical errors that are not merely typographical:

page 8, line 8 (7 February 2011)
change "19 November 19" to "19 November"
page 10, lines 4 and 5 (8 May 2011)
change "mtn" to "mn" (twice)
page 25, lines 12 and 13 from the bottom (2 February 2011)
change "décimale" to "décimales" (twice)
*page 36, lines 11--14 (7 February 2011)
insert a blank space before each right single quote mark (four times)
page 58, line 2 from the bottom (8 May 2011)
change "Weights of Measures" to "Weights and Measures"
*page 66, line 7 (6 February 2011)
change $theta$ to $\theta$
page 77, lines 12 and 13 (8 May 2011)
change "that that" to "that"
page 101, lines 4 and 7 (14 February 2011)
change "Academie" to "Académie" (twice)
page 120, lines 4 and 5 from the bottom (24 February 2011)
change "nombres surnaturel" to "nombres surnaturels"
page 121, replacement for lines 3 and 4 (28 March 2011)
[An abridgment of this chapter was published in The Mathematical Intelligencer 33,1 (Spring 2011), 33--45.]
page 123, line 9 (07 April 2012)
change "Wisconsonites" to "Wisconsinites"
page 155, line 13 (18 February 2012)
change "to appear" to "265--284"
page 160, insert a new third paragraph to the addendum (14 April 2011)
Mark Manasse has a wonderful license plate that I learned about too late to include in my original article: His is I DID F9, commemorating the successful factorization of the ninth Fermat number $2^{512}+1$ [see Mathematics of Computation 61 (1993), 319--349; 64 (1995), 1357].
page 160, also insert a new fourth paragraph (06 July 2011)
Ron Fagin tells me that, when he was a student at Dartmouth in the mid-1960s, John Kemeny proudly had the New Hampshire license plates LOGIC and SETS.
page 160, bottom line (04 October 2011)
change "2010." to "2010; and on 4 October 2011, Eugene Miya saw P♥THON. “What a grin.”
page 169, line 3 after the illustrations (24 February 2011)
change "my collection" to "our collection"
page 170, line 4 after the illustrations (24 February 2011)
change "my collection" to "our collection"
page 175, line 5 after the illustrations (24 February 2011)
change "my collection" to "our collection"
page 177, line 4 after the illustrations (24 February 2011)
change "my collection" to "our collection"
*pages 190 and 191 (12 December 2010)
the final two chords of this music should change, and several other minor errors should be fixed; see the corrected copy
page 194, line 2 from the bottom (24 February 2011)
change "Des arts nouveaux! où Le hasard" to "Du Hasard"
page 194, bottom line (27 February 2011)
change "Revue des Revues" to "La Revue des revues"
page 247, replacement for line 13 (14 August 2012)
default_msg[TOSS] = default_msg[DROP];
page 262, line 14 (13 March 2011)
omit "ditto(ENTER);"
page 262, line 5 from the bottom (13 March 2011)
omit "ditto(OUT);"
page 304, line 11 from the bottom (14 August 2012)
change 'check,""' to 'check,0'
page 307, line 4 (09 March 2011)
change prop[t] to place[t]
page 313, line 10 (14 August 2012)
change "hides his treasure" to "leaves his treasure"
page 320, line 6 (09 March 2011)
change "of that motion" to "of that action"
page 321 and following (09 March 2011)
(several functions, such as lookup and is_at_loc, are erroneously listed as type void in the mini-indexes)
page 324, line 10 from the bottom (14 Aug 2012)
change "printf" to "if (p) printf"
page 329, line 12 (14 August 2012)
change "wish to quit" to "want to quit"
page 331, replacement for line 1 (14 August 2012)
report("Peculiar. Nothing unexpected happens.");
page 344, line -4 (10 August 2012)
change "change_to(EAT)" to "verb=EAT" (and also remove "change_to" from the mini-index on page 345)
page 346, line 4 (15 August 2012)
delete "k=1;"
page 384, right column, change_to entry (10 August 2012)
change "122, 129" to "122"
page 391, left column, TOSS entry (14 August 2012)
change "14, 99" to "14"
page 400, line -16 (22 August 2011)
change "Club" to "Club, developed by Murl Deusing,"
page 400, lines -11 through -9 (22 August 2011)
change "I've been unable ... Brazier." to "The handsome host who appears in Figure 3 was Art Whitfield."
page 419, line 6 from the bottom (01 March 2011)
change "slow to fast, flat" to "flat"
page 432, line 10 (01 March 2011)
change "there 179" to "there are 179"
page 448, line 5 below Table 1 (27 February 2011)
change "memory" to "memory accesses"
page 486, line 3 from the bottom (02 March 2011)
change "obtaining by" to "obtained by"
page 528, line 13 from the bottom (15 February 2011)
change "the closed states" to "the 167 closed states"
page 531, line 14 from the bottom (23 February 2011)
change "which we already know" to "for which we already know $G(\beta)$"
page 616, line 6 (13 March 2011)
change "need for" to "needed for"
page 684, line 18 (7 February 2011)
change "Vive" to "Vive la"
page 703, line 18 (7 February 2011)
change "Hector" to "Héctor"
*page 703 (16 January 2011)
Addendum
I forgot to mention that Edmé Simonot had already implemented Vandermonde's idea of knotted-string knight's tours in his Polygraphile of 1872. In fact I encountered two examples of that remarkable puzzle during a visit to the Cleveland Public Library in May 2010, shortly after having designed Figures 33 and 34.
page 705, lines 3 and 4 (4 March 2011)
change "tributes to be published in ... (March 2011)" to "tributes published in ... (March 2011), 218--220"
page 715 (15 December 2010)
insert the picture after line 3
page 718, left column, new entry (25 February 2011)
agile methods, 711.
page 722, left column, new entry (06 July 2011)
Dartmouth College, 160.
page 724, left column, new entry (25 February 2011)
extreme methods, 711.
page 724, new entry (14 April 2011)
factorization, 160.
page 724, new entry (06 July 2011)
Fagin, Ronald, 160.
page 724, right column, new entry under Fermat (14 April 2011)
  numbers, 160.
page 724, right column, new entry (19 April 2011)
Fischer, Alexander, 484.
page 728, right column, new entry (06 July 2011)
Kemény, János György (= John George), 160.
page 730, right column, new entry (14 April 2011)
Manasse, Mark Steven, 160.
page 735, left column, new entry (04 October 2011)
Python language, 160.
page 737, right column, new entry (25 February 2011)
silver bullets, 711.
page 737, right column, new entry (25 February 2011)
Simonot, Edmé, 703.
page 740, left column, Vandermonde entry (25 February 2011)
add page 703
page 740, right column, new entry (20 September 2011)
Whitfield, Arthur Raymond “Whit”, 399--400.

Errata to the Third Printing (2012)

*page 105, line -15 (1 November 2013)
change $10^{2^{10^{80,000,000,000,000,003}}}$ to $10^{2^{10^{80,000,000,000,000,000}+3}}$
page 107, line 4 (27 March 2014)
change "subjection" to "subject"
*page 198, line 5 after Variation 3 (14 January 2014)
change "melody note." to "melody note and force the desired chord."
*page 332, lines 6--9 (3 September 2012)
move line 6 ("if (toting... crash*/") to line 9 between "smash:" and "prop"

I hope the book is otherwise error-free; but (sigh) it probably isn't, because each page presented me with hundreds of opportunities to make mistakes. Please send suggested corrections to knuth-bug@cs.stanford.edu, or send snail mail to Prof. D. Knuth, Computer Science Department, Gates Building 4B, Stanford University, Stanford, CA 94305-9045 USA. In either case please include your postal address, so that I can mail an official certificate of deposit as a token of thanks for any improvements to which you have contributed.

I may not be able to read your message until many months have gone by, because I'm working intensively on The Art of Computer Programming. However, I promise to reply in due time.

DO NOT SEND EMAIL TO KNUTH-BUG EXCEPT TO REPORT ERRORS IN BOOKS! And if you do report an error via email, please do not include attachments of any kind; your message should be readable on brand-X operating systems for all values of X.

Don Knuth's home page

Don Knuth's other books

Valid HTML 4.01 Transitional