A problem by Kagen Schaefer:
Suppose a king tours a chessboard, visiting each square once, never crossing his own path, and finishing where he starts. Inevitably he’ll have to make some horizontal and vertical moves; for example, in the tour above he makes 14 horizontal and 16 vertical moves.
Show that in any such tour of an 8 × 8 chessboard the sum of the horizontal and vertical moves must be at least 28.
|
SelectClick for Answer |
The king must visit the perimeter squares of the chessboard in order; if he skips any he’ll be unable to visit them and get home again without crossing his own path. And since the perimeter squares alternate colors, the path to each successive perimeter square must involve at least one horizontal or vertical move (diagonal moves alone won’t bring the king to a new color). There are 28 perimeter squares, so the task requires at least 28 horizontal or vertical moves. Here’s a tour that requires exactly 28:
(From John J. Watkins, Across the Board: The Mathematics of Chessboard Problems, 2004.)
|
