Determine the smallest positive integer $k{}$ satisfying the following condition: For any configuration of chess queens on a $100 \times 100$ chequered board, the queens can be coloured one of $k$ colours so that no two queens of the same colour attack each other. Russia, Sergei Avgustinovich and Dmitry Khramtsov
Problem
Source: 2020 RMM Shortlist C3
Tags: combinatorics, Chessboard, RMM, RMM 2020, RMM Shortlist
10.10.2022 17:04
Very interesting combo.
18.02.2023 21:41
The answer is $k=5$. We first prove by induction on the number of queens that 5 colours always suffice. The base case, when there are at most 5 queens, is trivial. To perform the induction step, remove the leftmost queen $Q{}$ among the topmost ones. The remaining configuration can be coloured by the induction hypothesis. On the other hand, $Q{}$ attacks at most 4 queens; so, returning $Q{}$ back, one can assign it a colour none of its attackers has. It remains to exhibit an arrangement which admits no 4-colouring satisfying the problem requirements. We will prove that the arrangement shown in the left figure below is as desired; the queens should be placed onto the shaded squares. Assume, to the contrary, that the queens in this arrangement can be 4-coloured as required. Lemma. Either the queens $a_1, a_2, a_3, a_4, a_5$, or the queens $a_1, a_2', a_3', a_4', a_5'$ are assigned two colours alternately. Proof. Assume that the colours of $a_1, \ldots , a_5$ do not follow the pattern. Then three consecutive queens on this diagonal have three distinct colours, say, 1, 2, and 3. Notice that any four queens forming a diamond should have four distinct colours. This means that the north-east diagonals starting at the three queens should be coloured as shown in the middle figure below. In this colouring, each north-east diagonal contains only two colours, while each north-west diagonal contains three. Similarly, if the colours of $a_1, a_2', a_3', a_4', a_5'$ do not follow the pattern, then the north-west diagonals starting at three consecutive queens on this diagonal are coloured in a similar manner, but with reversed roles of the diagonals. So the two obtained colourings do not agree where they meet. Applying the lemma and using the symmetry of the arrangement, we assume that the queens $a_1, \ldots , a_5$ are assigned colours 1 and 2 alternately, so that $a_1{}$ and $a_5{}$ share colour 1. Then the queens $b{}$ and $c{}$ should have colours 3 and 4 (in some order), and hence the queens $d{}$ and $e{}$ should both have colour 2. This is impossible, since $d{}$ and $e{}$ attack each other. Comments. The problem calls for a proper colouring of a graph with queens as vertices, where two queens share an edge if they attack each other. In this setting, the argument in the first paragraph is an instance of a well-known fact stating that any $k{}$-degenerate graph is properly $(k + 1)$-colourable. For the remaining part of the solution, there are many different arrangements showing that $k\geqslant 5$. One of them is depicted in the right figure above. To show that it works, notice that either $a, b, c$ or $a, b', c'$ have three distinct colours (otherwise $c{}$ and $c'{}$ share the colour of $a{}$). Assuming the former, we get, as in the above lemma, that $a{}$ and the queens to the right of it are assigned two colours alternately, say 1 and 2. Then the queens $d, e$, and $f{}$ should all have colours 3 or 4, so two of them share the same colour. This is impossible.
18.02.2023 21:49
Nice solution. Is this the official one?
18.02.2023 21:57
R8kt wrote: Nice solution. Is this the official one? Yes, it is the official one (and I agree, it's very nice).
17.02.2024 11:10
Quite a easy problem.