5. In the center of each cell of a grid rectangle $M$, there is a point light bulb, all of which are initially turned off. In one move, it is allowed to draw any straight line that does not touch the light bulbs and turn on all the light bulbs on one side of this line, if all of them are off. Each move must turn on at least one light bulb. It is required to turn on all the light bulbs, making as many moves as possible. What is the maximum number of moves that can be made if

a) $[4] M-$ is a $21 \times 21$ square;

b) $[4] M-$ is a $20 \times 21$ rectangle?

Alexander Shapovalov

Answers: a) 3 moves; b) 4 moves.
Solution. Instead of the original rectangle $M$, we will consider rectangle $N$ with vertices at the corner lamps.

Estimates. Note that with each move, at least one of the four corner lamps is lit. Therefore, there are no more than 4 moves. In part a), note also that we must light the central lamp at some move. Together with it, on one side of the drawn line, there will be at least two corner lamps (since a line parallel to the drawn one and passing through the center divides the square $N$ into two parts symmetric relative to the center).

Examples. a) First, we light everything except the bottom row of lamps, then we light all of the remaining lamps except the corner one, and finally, we light the corner lamp. (The image shows the two bottom layers of lamps, the arrows indicate on which side of the line the lamps are lit.)
![](https://cdn.mathpix.com/cropped/2024_05_06_8659f0e4423e0aaf02f9g-3.jpg?height=163&width=697&top_left_y=2271&top_left_x=1278)
b) Rectangle $N$ has dimensions $19 \times 20$. There are no other lamps on its diagonal since 19 and 20 are coprime. We draw the first line parallel to the diagonal, slightly below, so that these two lamps are above it, and all other lamps remain on the same side as before; we light all lamps below this line. Similarly, we draw the second line parallel to the diagonal, but slightly above, and light all lamps above this line, as shown in the image. (For the example, we took $N$ with dimensions $4 \times 5$ - smaller but also with coprime sides.) The remaining two corner lamps can be lit in two moves, separating them with a line from the rest.
![](https://cdn.mathpix.com/cropped/2024_05_06_8659f0e4423e0aaf02f9g-4.jpg?height=420&width=499&top_left_y=207&top_left_x=1496)