4. In a rectangular grid $20210 \times 1505$, two diagonals were drawn and all cells through which they passed were painted. How many cells were painted?

(O. A. Pyayve, A. A. Tessler)
Solution. This is a more complex version of problem 3 for 5th grade.
![](https://cdn.mathpix.com/cropped/2024_05_06_ada50bc4f8866d307083g-1.jpg?height=280&width=1692&top_left_y=2466&top_left_x=203)

First, let's determine how many cells one diagonal crosses. Note that $20210=215$. $94,1505=215 \cdot 7$. Therefore, the diagonal passes through 215 rectangles of size $94 \times 7$. In each of these rectangles, it crosses 93 vertical and 6 horizontal grid lines (at non-coincident points), and 99 intersection points divide it into 100 segments, meaning it crosses 100 cells. In total, this results in 21500 cells.

Two diagonals should cross 43000 cells, but among these cells, there are overlapping ones (near the center of the rectangle) that are counted twice. Let's find out how many there are. The larger coordinate of the center is an integer, and the smaller one is a half-integer. The ratio of the sides of the rectangle is $94: 7$, so $x=\frac{1}{2} \cdot \frac{94}{7} \in (6 ; 7)$ (see the diagram). Therefore, the number of common cells is 14.

Answer: 42986.

Criteria. If the number of cells each diagonal crosses is correctly calculated but the overlap is not considered, -3 points. If, in addition to this, the "center" is considered but incorrectly, -4 points. If the GCD of the numbers is found without further progress, 1 point.