Shapovalov A.V.

In the center of each cell of a rectangular grid $\$ M \$$ there is a point light bulb, initially all of them are 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) $\$ \mathrm{M} \$$ is a square $\$ 21 \backslash$ times $21 \$$;

b) $\$ \mathrm{M} \$$ is a rectangle $\$ 20 \backslash t$ times $21 \$$?
Instead of the original rectangle $\$ M$ b, we will consider the rectangle $\$ \mathrm{~N} \$$ with vertices at the corner lamps.

Estimates. Note that with each move, at least one of the four corner lamps is lit. Therefore, the number of moves is no more than 4. 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 figure 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_afad11de590b368f242eg-07.jpg?height=180&width=694&top_left_y=2397&top_left_x=682)

b) The rectangle $\$ \mathrm{~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, while 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 figure. (For the example, we took \$N\$ with dimensions \$4\times5\$ - smaller but also with coprime sides.) The remaining two corner lamps can be lit in two moves, by isolating

![](https://cdn.mathpix.com/cropped/2024_05_06_afad11de590b368f242eg-08.jpg?height=409&width=1281&top_left_y=1&top_left_x=0)

## Answer

a) 3 moves; b) 4 moves.