# Painting cells on the diagonals of a grid rectangle

In a grid rectangle 20210 × 1505, two diagonals are drawn, and all the cells containing segments of diagonals are painted. How many cells are painted?

• Do you count cells or lines? I.e. 20210 x 1505 cells meaning 20211 horizontal lines and 1506 vertical lines or 20210 x 1505 grid intersection points meaning 20209 x 1504 cells? – loopy walt Apr 4 at 7:42

## 1 Answer

The answer is

42986 cells

That's because

in a $$94\times7$$ rectangle (1/46225th of the original one, since GCD of 20210 and 1505 is 215), a single diagonal will paint the following cells: a segment in row 1 (lowermost), then another segment in row 2, etc. up to row 7. The segments form a "ladder" (since the diagonal continuously rises when running left-to-right) and always overlap by 1 cell (since 94 and 7 are coprime, the diagonal does not run through the lattice points). The total length of the 7 segments is 94 (the entire width of the rectangle) plus 6 overlappings of 1 cell each, totaling to 100 (precisely, the columns 14, 27, 41, 54, 68 and 81 will be painted twice - the numbers are $$\mathrm{ceil}\left(\frac{94k}{7}\right), k=1,2,\dots,6$$).

In a large $$20210\times1505$$ rectangle, each of the diagonals runs through 215 such smaller $$94\times7$$ rectangles (if we divide the large rectangle into 46225 small ones). So, the two diagonals cover $$2\times215\times100=43000$$ squares, but 14 of them is covered by both (since $$1505$$ is an odd number, the diagonals intersect on the edge of a cell, not on a lattice point). So, we must subtract 14, and 42986 is the final answer.

• Small nitpick: The diagonals do not intersect inside a cell. They should intersect exactly in the middle which with parities of numbers of rows and columns unequal must fall on a grid line. – loopy walt Apr 4 at 8:03
• What is plus 6 ?? – MathR Apr 4 at 9:03
• Thanks for pointing it out! Of course, they will interest strictly inside of a cell only when both width and height are odd. – trolley813 Apr 4 at 9:04
• @Reza 7 segments will have 6 overlapping, namely those between segments #1 and #2, #2 and #3, etc. up to #6 and #7. – trolley813 Apr 4 at 9:05