MathDB

6

Part of 2010 Baltic Way

Problems(1)

Attacking rooks on a coloured chessboard

Source: Baltic Way 2010

11/19/2010
An n×nn\times n board is coloured in nn colours such that the main diagonal (from top-left to bottom-right) is coloured in the first colour; the two adjacent diagonals are coloured in the second colour; the two next diagonals (one from above and one from below) are coloured in the third colour, etc; the two corners (top-right and bottom-left) are coloured in the nn-th colour. It happens that it is possible to place on the board nn rooks, no two attacking each other and such that no two rooks stand on cells of the same colour. Prove that n=0(mod4)n=0\pmod{4} or n=1(mod4)n=1\pmod{4}.
modular arithmeticcombinatorics proposedcombinatorics