AoPS - Problem

Source: 44th International Tournament of Towns, Junior A-Level P4, Fall 2022

Tags: combinatorics, board, Tournament of Towns

oVlad

16.02.2023 18:10

Let $n>1$ be an integer. A rook stands in one of the cells of an infinite chessboard that is initially all white. Each move of the rook is exactly $n{}$ cells in a single direction, either vertically or horizontally, and causes the $n{}$ cells passed over by the rook to be painted black. After several such moves, without visiting any cell twice, the rook returns to its starting cell, with the resulting black cells forming a closed path. Prove that the number of white cells inside the black path gives a remainder of $1{}$ when divided by $n{}$.

Here is a solution using the Peak formula, but without much details. Let's introduce a coordinate system (a checkered grid) with the beginning in the center of the cell where the rook stands and the axes containing the horizontal and vertical in which the rook stands. Then, with each move, the rook moves to a horizontal or vertical vector of length $n$, thereby limiting some polygon $M$ with vertices at the nodes of the lattice. According to the peak formula, its area is $A=I+B/2-1$. First, $n|A$, since it is possible to split all sides of $M$ into segments of length $n$ and draw a vertical or horizontal line from each such point so that $M$ splits into squares with side $n$ Further, $2n|B$, because the sum of vertical segments and the sum of horizontal segments is a multiple of $2n$. Then $n|A-B/2=I-1$, which, in fact, we wanted to prove.