Browse · MathNet
PrintBelarus2022
Belarus 2022 counting and probability
Problem
Two players play the game on the board all cell of which are initially white. The players make their moves in turn, in one move a player paints black two not necessarily adjacent white cells located either in the same row or in the same column. The player who cannot make a move loses. Which of the players can win regardless of the opponent's game?
Solution
Answer: the first player has a winning strategy. Since two cells are repainted on each move and the total number of cells on the board is odd, at the end of the game there will be an odd number of white cells. Obviously there will remain not more than one white cell left in each row, so there will remain one or three white cells on the entire board. Hence if there is exactly one white cell left, then the total number of moves is which means that the first player made the last move and have won. And if there are three white cells left on the board, then the second player have won. But it's possible only there is one white cell left in each line. Thus to win the first player only needs to completely recolor one of the lines.
We will provide the winning strategy for the first player. The first player will try to paint over the first line of the board (the lines of the board are numbered from top to bottom).
On the first move, the first player paints one cell of the 1st row and one cell of the 2nd row, located in the same column. Further, he responds to the moves of the second player as follows:
1) If the second player paints two cells not from the 1st row, then the first player paints two cells of the 1st row, and in such a way that the cells painted by him are in the same columns as those painted by the second player (if it's possible, otherwise the first player paints an arbitrary cells of the 1st row).
2) If the second player paints one cell of the 1st row and one cell of a non-1st row, the first player paints one cell of the 1st row and one cell of a non-1st row.
3) If the second player paints two cells of the 1st row, then the first player paints two cells of the 1st row (if not all cells are painted over by the current moment).
Thus, if the first player adheres to the specified strategy, after each of his moves, an even number of white cells will remain in the first row, which means that at some turn all the cells of the 1st row will be painted over.
It remains to show that the strategy described above is feasible. Obviously, moves 1) and 3) are always possible (unless all the cells of the 1st row are already painted). Let us show that move 2) is also realizable. Indeed, due to the fact that on move 1) the first player paints the cells of the 1st row in the same columns in which the second player painted the cells before (if possible), then after each move of the first player, if there is a shaded cell in the column, then the cell from the 1st row is also painted in it (if the second player, while painting the cells in the column, did not paint over his cell in the 1st row, then the first player will do it on the next move 1). Therefore, if there is a white cell in the 1st row, then both cells of this column located in the 2nd and 3rd rows are also white. Therefore, move 2) can be done.
We will provide the winning strategy for the first player. The first player will try to paint over the first line of the board (the lines of the board are numbered from top to bottom).
On the first move, the first player paints one cell of the 1st row and one cell of the 2nd row, located in the same column. Further, he responds to the moves of the second player as follows:
1) If the second player paints two cells not from the 1st row, then the first player paints two cells of the 1st row, and in such a way that the cells painted by him are in the same columns as those painted by the second player (if it's possible, otherwise the first player paints an arbitrary cells of the 1st row).
2) If the second player paints one cell of the 1st row and one cell of a non-1st row, the first player paints one cell of the 1st row and one cell of a non-1st row.
3) If the second player paints two cells of the 1st row, then the first player paints two cells of the 1st row (if not all cells are painted over by the current moment).
Thus, if the first player adheres to the specified strategy, after each of his moves, an even number of white cells will remain in the first row, which means that at some turn all the cells of the 1st row will be painted over.
It remains to show that the strategy described above is feasible. Obviously, moves 1) and 3) are always possible (unless all the cells of the 1st row are already painted). Let us show that move 2) is also realizable. Indeed, due to the fact that on move 1) the first player paints the cells of the 1st row in the same columns in which the second player painted the cells before (if possible), then after each move of the first player, if there is a shaded cell in the column, then the cell from the 1st row is also painted in it (if the second player, while painting the cells in the column, did not paint over his cell in the 1st row, then the first player will do it on the next move 1). Therefore, if there is a white cell in the 1st row, then both cells of this column located in the 2nd and 3rd rows are also white. Therefore, move 2) can be done.
Final answer
the first player
Techniques
Games / greedy algorithmsInvariants / monovariants