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?
Problem
Source: St. Petersburg 2021 9.2
Tags: combinatorics
Tintarn
12.01.2022 21:56
YES
It is convenient to use induction, although one could describe the construction explicitly.
So we replace 100 by n and 199 by 2n−1.
For n=1, it is trivial.
Now assume that we already have a construction for n−1.
By using our two additional rooks, we may always supply one rook on the cell B1 which serves as a substitute for the first move in the case n−1, applied to the lower right (n−1)×(n−1) subboard. So we apply this procedure until we have n−1 mutually non-attacking rooks on this board (indeed our construction will put them on the diagonal but this is irrelevant).
We are thus left with n rooks and the task of placing one rook on the upper left corner.
Again, this can be done by induction: If we can place one rook on the cell one lower using n−1 rooks, we can do this once, then use the remaining n−1 rooks to do it again and then move one of the two rooks on this cell one up. Done.
(A slightly more challenging problem would be to show that the number 2n−1 is optimal.)
QiushengJLi
04.03.2024 02:43
If we replace 199 by m, then the minimum possible value of m that Misha can achieve his goal would be 150. In general, for n by n chessboard, the answer is floor of 3n/2.