Problem

Source: CAPS Match 2023 P6

Tags: combinatorics



Given is an integer $n \geq 1$ and an $n \times n$ board, whose all cells are initially white. Peter the painter walks around the board and recolors the visited cells according to the following rules. Each walk of Peter starts at the bottom-left corner of the board and continues as follows: - if he is standing on a white cell, he paints it black and moves one cell up (or walks off the board if he is in the top row); - if he is standing on a black cell, he paints it white and moves one cell to the right (or walks off the board if he is in the rightmost column). Peter’s walk ends once he walks off the board. Determine the minimum positive integer $s$ with the following property: after exactly $s$ walks all the cells of the board will become white again.