Problem of the Week 977

Anything Goes

Consider the following 3x3 chess board with black knights at the top and white knights at the bottom

| BN |    | BN |
|    |    |    |
| WN |    | WN |

The idea is to make ordinary chess moves, moving knights out of turn if desired, and end up in a position so that the black knights are in the two lower corners, and the white knights are in the two upper ones. In this form, the problem is a classic, and was used as a PoW years ago. But there is a new twist:

Do it so as to minimize the number of "move sequences", where a move sequence consists of a sequence of moves of a single knight. In short, you are trying to minimize the number of times you pick up and then let go of a single piece. Proof of optimality is not required, so we will tell you that it can be done using seven move sequences.

The title refers to the Cole Porter song, whose lyrics include something like: "Black's white today and white's black today...."

Source: A beautiful article by Noam Elkies and Richard Stanley in the latest issue of The Mathematical Intelligencer (Winter 2003). Their article contains some very original problems and observations relating chess situations with graph theory.
© Copyright 2003 Stan Wagon. Reproduced with permission.

13 February 2003