MathDB
Japan MO Finals 2021 P2

Source: Japan MO Finals 2021 P2

February 14, 2021
gamecombinatoricsJapan

Problem Statement

Let n2n\geq 2 be an integer. Players AA and BB play a game using n×2021n\times 2021 grid of square unit cells. Firstly, AA paints each cell either black of white. BB places a piece in one of the cells in the uppermost row, and designates one of the cells in the lowermost row as the goal. Then, AA repeats the following operation n1n-1 times: ・When the cell with the piece is painted white, AA moves the piece to the cell one below. ・Otherwise, AA moves the piece to the next cell on the left or right, and then to the cell one below. Find the minimum possible value of nn such that AA can always move a piece to the goal, regardless of BB's choice.