Problem A. 881. (May 2024)
A. 881. We visit all squares exactly once on a \(\displaystyle n\times n\) chessboard (colored in the usual way) with a king. Find the smallest number of times we had to switch colors during our walk.
(Proposed by Dömötör Pálvölgyi, Budapest)
(7 pont)
Deadline expired on June 10, 2024.
We claim that if \(\displaystyle n\) is odd, the solution is \(\displaystyle 2n-2\), while if \(\displaystyle n\) is even, the solution is \(\displaystyle n-1\). Examples of these constructions are shown in the diagrams below with the green lines indicating the paths. Generally, what we do is traverse the rows in pairs from top to bottom, with each pair of rows being traversed diagonally as shown in the diagram. In this way, we only need to change color at the ends of the rows and when transitioning to the next pair. Thus, in the case of an even \(\displaystyle n\), we finish with a total of \(\displaystyle n-1\) color changes, while in the case of an odd \(\displaystyle n\), the bottom row is left out and is simply traversed straight, resulting in an additional \(\displaystyle n-1\) color changes.
Let's consider the lower bound to see why fewer color changes are not possible. Let \(\displaystyle n\) be fixed, and color the grid such that the top left corner is dark. Divide the grid into regions based on how many steps it takes the king to reach the edge of the board. Thus, the \(\displaystyle k\)-th region consists of those squares from which the king can reach the edge of the board in exactly \(\displaystyle k\) steps, but not fewer (the squares on the edge of the board form the 0th region). The diagrams above show what the regions look like, with the regions bounded by red lines. Let's call a square even if it is in an even-indexed region, otherwise, it is odd.
The main idea of the solution is as follows. There are far more even dark squares than odd ones, and generally, the king cannot move from an even dark square to another even dark square. Let's calculate this precisely, and we will obtain the exact estimate for which we have already shown a construction. As with the construction, the calculation here will also depend on the parity of \(\displaystyle n\).
Case 1. \(\displaystyle n\) is odd.
Let \(\displaystyle n=2k+1\). Notice that there are \(\displaystyle k+1\) regions, numbered from 0 to \(\displaystyle k\). Obviously, there is 1 dark square in the \(\displaystyle k\)-th region and 4 dark squares in the \(\displaystyle (k-1)\)-th region. It can be seen that as we move outward, there are always 4 more dark squares than in the previous level, i.e., at level \(\displaystyle (k-m)\) there are \(\displaystyle 4m\) dark squares for all \(\displaystyle 1 \leq m \leq k\). By induction, we can see that there are exactly \(\displaystyle (2k+1)\) more even dark squares than odd ones. This is clear for \(\displaystyle k=0\), so let's assume we have already proven it for \(\displaystyle (k-1)\). In a \(\displaystyle (2k+1) \times (2k+1)\) grid, if we disregard the outer 0th layer, we get a \(\displaystyle (2k-1) \times (2k-1)\) grid, in which we already know that there are \(\displaystyle (2k-1)\) more even dark squares than odd ones. However, if we add back the outer region, the regions that were even become odd and vice versa, so without the addition of the 0th region's dark squares, there are \(\displaystyle (2k-1)\) more odd dark squares. Adding the 0th region's \(\displaystyle 4k\) dark squares, we obtain a total of \(\displaystyle (2k+1)\) more even dark squares, as we wanted.
Assume there is a traversal of the king where it visits each square exactly once. We say that two adjacent squares are friends if the king steps from one to the other during its path, and a square's friends are those squares it is friends with. Thus, on the king's path, except for the start and end points (which have one friend each), every square has exactly two friends: one from which it arrived, and one to which it stepped. Let's examine the friends of the even dark squares. Let \(\displaystyle a\) be the number of even dark squares (we could easily calculate this exactly, but it is not necessary), then there are \(\displaystyle a-2k-1\) odd dark squares. Notice that the king cannot step from an even dark square to another even dark square. The \(\displaystyle a\) dark squares have at least \(\displaystyle 2a-2\) friends in total, counting multiplicity, while the odd dark squares have at most \(\displaystyle 2(a-2k-1)\) friends. Thus, there are at least
\(\displaystyle 2a-2-2(a-2k-1)=4k=2n-2\)
pairs of friends where one is an even dark square, and the other is not an odd dark square. This means the other pair must be a white square, which precisely means there were \(\displaystyle 2n-2\) color changes during the king's path.
Case 2. \(\displaystyle n\) is even.
Let \(\displaystyle n=2k\). This case works very similarly, with two minor differences: there are adjacent even dark squares, and the king's walk is guaranteed to end on a different color than it started. But these do not complicate the calculations, so we will not go into as much detail here.
In this case, the number of dark squares in the regions also increases by four as we move outward, so simple induction shows that there are \(\displaystyle 2k\) more even dark squares than odd ones. There are \(\displaystyle k\) regions, and each region contains exactly two pairs of dark squares that are adjacent to each other, except for the central \(\displaystyle (k-1)\)-th region, which has only one such pair. Again, let's take an arbitrary walk, using the terms introduced in the previous case, and let \(\displaystyle a\) be the number of even dark squares. Then there are \(\displaystyle a-2k\) odd dark squares. Since the king's walk cannot start and end on a dark square simultaneously, the \(\displaystyle a\) even dark squares have at least \(\displaystyle 2a-1\) friends in total, counting multiplicity.
If \(\displaystyle k\) is even, there are \(\displaystyle \frac{k}{2}\) even-indexed regions, and the central \(\displaystyle (k-1)\)-th region is not one of them, so there are \(\displaystyle k\) pairs of even dark squares that are adjacent. If \(\displaystyle k\) is odd, there are \(\displaystyle \frac{k+1}{2}\) even-indexed regions, including the central \(\displaystyle (k-1)\)-th region, so in this case too there are \(\displaystyle k\) pairs of even dark squares that are adjacent. Thus, the even dark squares have at most \(\displaystyle 2k\) even dark friends in total, counting multiplicity.
The odd dark squares have at most \(\displaystyle 2(a-2k)\) friends in total, counting multiplicity, so there are at least
\(\displaystyle (2a-1)-(2k)-2(a-2k)=2k-1=n-1\)
friends of even dark squares (counting multiplicity) that are neither even nor odd dark squares, i.e., they are white squares. This is exactly what we wanted to show.
Statistics:
14 students sent a solution. 7 points: Bodor Mátyás, Czanik Pál, Holló Martin, Kocsis 827 Péter, Varga Boldizsár. 6 points: Szakács Ábel, Wiener Anna. 5 points: 1 student. 3 points: 1 student. 2 points: 2 students. 0 point: 1 student. Not shown because of missing birth date or parental permission: 2 solutions.
Problems in Mathematics of KöMaL, May 2024