Problem

Source: St. Petersburg 2021 9.2

Tags: combinatorics



Misha has a 100x100 chessboard and a bag with 199 rooks. In one move he can either put one rook from the bag on the lower left cell of the grid, or remove two rooks which are on the same cell, put one of them on the adjacent square which is above it or right to it, and put the other in the bag. Misha wants to place exactly 100 rooks on the board, which don't beat each other. Will he be able to achieve such arrangement?