-----Original Message----- From: Michael B Greenwald [mailto:mbgreen@central.cis.upenn.edu] Sent: Thursday, May 29, 2003 12:25 PM To: math-fun Cc: Andy Latto Subject: Re: [math-fun] knight problems from Elkies and Stanley

Thu, 29 May 2003 10:39:44 -0400 Andy Latto <Andy.Latto@gensym.com>

Like many proofs by contradiction, I find that this proof that there is no knight's tour on a 4xn chessboard hides a bit of what's really going on. Here's a more direct version of the same proof that I find more perspicuous.

Call the squares in the top and bottom rows of a 4xn board the "extreme" squares.

Since you can't get in one knight's move from one extreme square to another, the maximum density of extreme squares in a knight's tour is 50%, and this is only attained if every other square in the tour is extreme.

No; if the first and last moves of the tour are extreme, then you can have two non-extreme squares in a row somewhere in the middle. Those two moves allow you to "switch parity". If the two consecutive non-extreme squares are in the center of the tour, then you can (in theory) have a tour that first covers the black extreme squares, then switches parity and does the mirror image tour to cover the white extreme squares (and black non-extreme).

Right. Both the original proof and my reworking of it only prove the (true) statement that there is no closed knight's tour on a 4xn board, and not the (false) statement that there is no open knight's tour. An analysis of either proof shows that if there is an open knight's tour on a 4xn board, then exactly one link in the the tour connects two non-extreme squares, and that this must be the middle link of the tour. Andy Latto andy.latto@pobox.com