SAUDI ARABIAN MATHEMATICAL COMPETITIONS

Question

The 64 cells of an 8 8 chessboard have 64 different colours. A Knight stays in one cell. In each move, the Knight jumps from one cell to another cell (the 2 cells on the diagonal of an 2 3 board); also the colours of the 2 cells interchange. In the end, the Knight goes to a cell having common side with the cell it stays at first. Can it happen that: there are exactly 3 cells having the colours different from the original colours?

Accepted Answer

The answer is no. Suppose that there are exactly 3 cells having the colours different from the original colours. Assign each colour with an integer from

1

to

64

and colour again the chessboard by black and white as usual. Arrange the numbers from left to right and up to down, so each move gives us a new permutation of the set

S = {1, 2, \dots, 64}

. In each permutation, we call a pair

(x, y)

bad if

x

is in the left of

y

but

x > y

.

Claim 1. Each move interchanges 2 numbers in the old permutation, and the number of bad pairs changes the parity.

Claim 2. Each move the Knight goes from a black cell to a white cell or vice versa.

The first cell and the last cell the Knight stays have colours black and white different. So by claim 2, there were totally an odd number of moves. By claim 1, the number of bad pairs in the first permutation and the number of bad pairs in the last permutation have different parities.

On the other hand, there are exactly 3 positions change from the first permutation to the last permutation. We can check to see that, the difference of the numbers of bad pairs are always 2. That means the number of bad pairs in the first permutation and the number of bad pairs in the last permutation have the same parity. A contradiction.

□