Suppose you have a checkerboard with two opposite corner squares removed, like this:
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?
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ Hamiltonian path problem $\endgroup$– ratchet freakMay 16, 2014 at 20:15
-
3$\begingroup$ Pedantic: Your chessboard is sideways :) $\endgroup$– Kendall FreyMay 16, 2014 at 21:03
-
3$\begingroup$ White on the right, I know, but it doesn't matter for this question. $\endgroup$– user88May 16, 2014 at 21:04
-
$\begingroup$ Follow up: Can you place 31 2x1 dominos so as to cover all of these squares exactly once? $\endgroup$– John BupitMay 19, 2014 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$– user88May 19, 2014 at 14:48
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
