9
$\begingroup$

Suppose you have a checkerboard with two opposite corner squares removed, like this:

mutilated chessboard

Can you move a pawn on the board only horizontally and vertically, one square at a time, and have it touch every square exactly once?

$\endgroup$
  • 1
    $\begingroup$ Hamiltonian path problem $\endgroup$ – ratchet freak May 16 '14 at 20:15
  • 2
    $\begingroup$ Pedantic: Your chessboard is sideways :) $\endgroup$ – Kendall Frey May 16 '14 at 21:03
  • 3
    $\begingroup$ White on the right, I know, but it doesn't matter for this question. $\endgroup$ – Joe Z. May 16 '14 at 21:04
  • $\begingroup$ Follow up: Can you place 31 2x1 dominos so as to cover all of these squares exactly once? $\endgroup$ – Mohit Punjabi May 19 '14 at 14:38
  • 2
    $\begingroup$ The domino problem is the most common formulation of this problem. I wanted to post one that was different but followed the same principle. $\endgroup$ – Joe Z. May 19 '14 at 14:48
21
$\begingroup$

No.

Every move the pawn makes it switches from a white to a black square or vice versa. Therefore it must either touch an equal number of white and black squares with an even number of moves, or one more square of either color with an odd number of moves. (A move including initially placing it on the board.)

Because there are two more white squares than black squares (32 and 30) there is no way it can touch each square exactly once.

The same argument applies to show that the Knight's Tour cannot be completed on this board either.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.