Given is a board $n \times n$ and in every square there is a checker. In one move, every checker simultaneously goes to an adjacent square (two squares are adjacent if they share a common side). In one square there can be multiple checkers. Find the minimum and the maximum number of covered cells for $n=5, 6, 7$.
Problem
Source: Bulgaria JBMO TST 2017 P4 Day 1
Tags: combinatorics proposed, combinatorics
13.02.2020 15:56
Ignore this.
09.08.2024 17:03
A chessboard coloring shows that we have at least one empty square when \( n \) is odd. By grouping the squares into pairs that share a side, we see that the minimum number of empty squares is \( 1 \) when \( n \) is odd and \( 0 \) when \( n \) is even. From now on, we will only discuss the maximum number of empty squares. The key is the following argument. Let's color the board in a checkerboard pattern, with the corner squares being black - itis clear that each pawn moves to a square of the opposite color. If \( M_1 \) is a set of black squares, none of which share a neighboring (white) square, then after the move, we necessarily have at least \( |M_1| \) white squares with a pawn; similarly, if \( M_2 \) is a set of white squares without a common (black) neighbor, then after the move, we necessarily have at least \( |M_2| \) black squares with a pawn. Thus, the number of empty squares is at most \( n^2 - |M_1| - |M_2| \). a) Here we have \( M_1 \) with 5 squares (the corner ones and the central one) and \( M_2 \) with 4 squares (many variations), so the empty squares are at most 16. One possible construction with 16 empty squares is placing the pawns from the black squares in the following 5 white ones: the 4th of the first row, the 1st and 3rd of the second row, the 5th of the fourth row, and the 2nd of the fifth row; and placing the pawns from the white squares in the following 4 black ones: the 2nd and 4th of the second row and the 2nd and 4th of the fourth row. b) Here we can choose \( |M_1| = |M_2| = 6 \), taking from the white squares: the first and fifth from the first and fifth row, the third from the third and sixth row; similarly for the black squares. One possible construction with 24 empty squares is placing the pawns from the first and third rows into the second, and then swapping the pawns in pairs within the second row; similarly for the fourth, fifth, and sixth rows. c) Similar to the previous cases; the maximum number of empty squares is \( 49 - 8 - 7 = 34 \).