From the 2001 Moscow Mathematical Olympiad:
Two stones, one black and one white, are placed on a chessboard. A move consists of moving one stone up, down, left, or right. The two stones may not occupy the same square. Does a sequence of moves exist that will produce every possible arrangement of the stones, each occurring exactly once?
|
SelectClick for Answer |
No. Call an arrangement even if the stones occupy squares of the same color, odd otherwise. In the sequence we’re seeking, the number of odd arrangements can differ from the number of even arrangements by at most 1.
The number of odd arrangements is 64 × 32 — choose any square for the black stone and then any square of the opposite color for the white. But the number of even arrangements is 64 × 31, since the two stones can’t occupy the same square. So the task is impossible.
|
