Thank you, Thane! That was the Winter '03 "Mathematical Entertainments" column in the Intelligencer; Ravi Vakil (a sometimes math-fun lurker) and I are editors. Our stated goal is to publish the kind of things that people find cool enough that they want to go spread them to other people -- your mail to math-fun makes it clear we succeeded! My favorite item from the column, though, has got to be the gorgeous proof that there is no knight's tour on the 4xn chessboard, for any n. I'll put a synopsis below, in case anyone wants to think about it before reading the elegant solution. Stanley and Elkies have been "working on" a book on math and chess for, oh, probably most of a decade by now, maybe longer. When Ravi and I took over the Intelligencer post, I was delighted to be in a position where I could get some of that material in print despite the book's long-term "forthcoming" status. --Michael Kleber kleber@brandeis.edu Stop reading here, if you so desire. Otherwise: first let's prove the seemingly unrelated fact that, on a standard 8x8 chessboard, the most knights you can put on with no two attacking each other is 32. It's easy to see how to attain 32: cover all the white or all the black squares with knights; each knight move changes color, so these 32 are clearly non-attacking. Now to show that these are the unique two configurations that attain this maximum: we already know that there is a knight's tour on the 8x8 board (a picture of Euler's solution is included in the article, for example). Given any two squares which are used consecutively in the knight's tour, at most one of them can be covered by a knight from a "no two attacking" configuration, of course. Therefore the only way to pack 32 knights is to place one on every other square in the knight's tour -- which means all the black or all the white squares, since again, knight moves alternate colors. Nice proof of the wrong theorem. But now apply the same proof to the 4xn board, and we see that if a knight's tour existed, then the only way to fit 2n nonattacking knights on a 4xn board would be to use all the squares of a single color. But that's manifestly not the case: on a 4xn board, cover the entire top row and the entire bottom row with knights; 2n of 'em, no pair attacking. QED. On Thursday, May 29, 2003, at 02:26 AM, Thane Plambeck wrote:
I found the following in a review by Philip D. Straffin (College Mathematics Journal, May 2003) of Noam Elkies and Richard Stanley's "The Mathematical Knight," The Mathematical Intelligencer 25:1 (Winter 2003) 22-34: ******** "...there are also discussions and problems for the reader (with answers at the end) that lead in less familiar directions. Here are some of my favorites:
1) Determine the knight distance from (0,0) to (m,n) on an infinite board 2) If you plot the 4! shortest knight paths from (0,0) to (6,0) you get an elegant projection of the edges of the 4-dimensional hypercube. Explain..." ***** It's hard not to pick up pencil and pad when you read stuff like that!
Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/home.htm