Maths Olympiad Prep

Library / /41 of 69

Combinatorics Difficulty 6.2 National olympiad Prove it Mongolia

Find all positive integers nn for which checkers can be placed on the cells of an n×nn \times n chessboard in such a way that each cell has exactly two neighboring cells with checkers. Two cells are considered neighbors if they share a common side.

Solution

Answer: nn even.

Let's start by proving that any even number nn is a good number.
For the n=2kn = 2k case we can construct a checkered pattern that all the cells of the frame contains checker and contains 2k42k - 4 case in the middle. The figure below illustrates this construction:

Now, let's show that for an odd number n=2k+1n = 2k + 1, each cell of the board cannot have exactly two checkered neighbors.
To demonstrate this, we will focus on the diagonal cells of the table. Consider the neighbors of the cells (i,i)(i, i) for i[n]i \in [n].
Starting with cell (1,1)(1, 1), since it has exactly two neighbors, we place checkers in those neighboring cells, which are (1,2)(1, 2) and (2,1)(2, 1). Now, these cells become neighbors of cell (2,2)(2, 2), so we do not place checkers in cells (2,3)(2, 3) and (3,2)(3, 2). We continue this process for cells (1+2j,2+2j)(1+2j, 2+2j) and (2+2j,1+2j)(2+2j, 1+2j), where jj ranges from 0 to k2k-2. As a result, cells (1+2j,2+2j)(1+2j, 2+2j) and (2+2j,1+2j)(2+2j, 1+2j) have checkers, while cells (2+2j,3+2j)(2+2j, 3+2j) and (3+2j,2+2j)(3+2j, 2+2j) do not contain checkers.
The figure below illustrates this construction:
Figure 1
Now, consider cells (2k,2k+1)(2k, 2k+1) and (2k+1,2k)(2k+1, 2k). Since these cells are neighbors of the corner cell (2k+1,2k+1)(2k+1, 2k+1), they should be checkered. However, we have already established that these cells cannot be checkered. This leads to a contradiction.
Therefore, the number n=2k+1n = 2k + 1 is not a good number.

In conclusion, we have shown that an even number is a good number, while an odd number is not a good number.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.